¿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  |