¿Qué es un modelo? Es una abstracción de la realidad que nos facilita el estudio de un fenómeno o problema. Un modelo no es un algoritmo Como veremos más adelante, para un mismo modelo pueden plantearse varios algoritmos.
Modelos para el ensamblamiento de ADN Plantearemos tres modelos teóricos. Shortest Common Superstring Reconstruction Multicontig Cada uno plantea distintas restricción sobre los fragmentos. Se asume que las muestras están libres de contaminación.
Primer Modelo:Shortest Common Superstring Tiene principalmente interés teórico pues no es muy útil en la realidad. Plantea muchas restricciones: Los fragmentos no deben tener errores Deben estar orientados correctamente La secuencia buscada no debe tener repeticiones
SCS: Definición Dado un conjunto de strings F, hallar un string S de longitud mínima tal que para todo string f en F, f es substring de S. Notar que S debe ser un superstring perfecto, por lo que no permites errores experimentales. Se debe conocer la orientacíon de cada string f.
SCS: Ejemplo F = {ACT, CTA, AGT} S = ACTAGT
SCS: Repeticiones Supongamos que secuenciamos la siguiente cadena de nucleótidos S = ACTTGTAAGGTTGTTAAG de la cual obtenemos los siguientes fragmentos F = {ACTT, TTGTAA, AAGGT, TTGT, GTT, TTAG}
SCS: Repeticiones (Cont.) Según este modelo, el resultado de hallar el SCS de F sería:
SCS: Resumen No admite repeticiones No admite errores experimentales Se debe conocer la orientación de los fragmentos. Es un problema NP-Hard. No resulta práctico para aplicaciones reales debido a la gran cantidad de restricciones y limitaciones.
¿Qué significa NP-Hard? NP-Completo se refiere a una familia de problemas de decisión para los cuales no se conoce una solución polinomial. Los problemas de decisión son aquellos para los que se espera una respuesta del tipo “sí” o “no”.
¿Qué significa NP-Hard? En el caso del TSP, el problema sería:¿Existe un camino que pase por todas las ciudades exactamente una vez recorriendo una distancia menor a 500 Km.? La respuesta esperada es simplemente “sí” o “no”.
¿Qué significa NP-Hard? Un problema HP-Hard es el problema de optimización asociado a un problema NP-Completo. En nuestro caso:¿Cuál es el camino más corto que pasa exactamente una vez por cada ciudad?
Segundo Modelo:Reconstruction Este modelo tiene en cuenta: Errores. Orientación desconocida Pero no modela: Repeticiones Falta de cubrimiento
Reconstruction: Definiciones Para entender como este modelo considera los errores debemos contar con algunas definiciones previas. Distancia de edición (o edit distance) Distancia de edición de substrings (o substring edit distance) Substring aproximado
Distancia de Edición Dadas dos cadenas a y b, llamaremos distancia de edición, y lo notaremos d(a, b), a la cantidad de inserciones, deleciones y/o substituciones que deben realizarse sobre las cadenas para que valga a = b. Ejemplo: d(ACTGT, AGGT) = 2 pues ACTGT = ACTGT Substitución Inserción
Distancia de Edición de Substrings Dadas dos cadenas a y b, llamaremos distancia de edición de substrings a: donde S(b) es el conjunto de los substrings de b. Ejemplo: ds(ACT, GATTACA) = 1 Pues d(ACT, ACA) = 1 y ACT ? S(b)
Substring Aproximado Sea ? un número real entre 0 y 1. Un string f es un substring aproximado de S con error ? cuando donde |f| es la longitud del string f. Por ejemplo: si ? = 0.05, permitiremos que f difiera en a lo sumo un 5% con el substring màs cercano en S.
| Página siguiente |