Reconstruction: Definición Dado un conjunto de strings F y una cota de error ? entre 0 y 1, hallar un string S de longitud mínima tal que para todo string f en F donde f es el string reverso y complementario a f.
Reconstruction: Resumen No admite repeticiones ni espacios no cubiertos Admite errores experimentales Modela la orientación desconocida Es un problema NP-Hard. SCS es un caso particular de este modelo.
Tercer Modelo:Multicontig: Introduce la noción de buen enlace. Este modelo tiene en cuenta: Errores. Orientación reconocida Falta de cubrimiento En algunos casos, repeticiones
Multicontig: Definiciones Llamaremos layout a un alineamiento múltiple de un conjunto de secuencias. El siguiente layout será utilizado como ejemplo en varias definiciones:
Multicontig: Definiciones (cont.) Diremos que dos fragmentos f y g se solapan (y lo llamaremos overlap) si comparten una o más columnas en el layout. Es decir, si ambos string se intersecan.
Multicontig: Definiciones (cont.) Podemos separar los overlaps en dos categorías: Los que producen un enlace. (f3 – f4) y los que no lo producen. (f2 – f5)
Multicontig: Definiciones (cont.) El enlace más débil (weakest link) es aquél overlap con menor longitud que produce un enlace. Diremos que un layout es un t-contig si el enlace más débil que posee tiene longitud t. Si es posible obtener un t-contig de un conjunto de fragmentos F, diremos que F admite un t-contig.
Multicontig: Definición ILibre de Errores Dado un conjunto de strings F y un entero t, particionar F en el mínimo número de subconjuntos Ci, 1 = i = k, tal que cada Ci admita un t-contig.
Multicontig: Ejemplos Dado F = {GTAC, TAAG, TGTAA}
Multicontig: Contemplando errores Si se admiten errores en el acoplamiento, se debe obtener una cadena por consenso que será el resultado del ensamblamiento. Diremos que S es una cadena ?-consensuada de F si, para cada cadena f en F, la distancia de edición entre f y su imagen en S es = | f |.
Multicontig: Contemplando errores Por ejemplo: S es una cadena 0.20 – consensuada con respecto a F.
Multicontig: Definición IIAdmitiendo de Errores Dado un conjunto de strings F, un entero t = 0 y una tolerancia de error ? entre 0 y 1, particionar F en el mínimo número de subconjuntos Ci, 1 = i = k, tal que cada Ci admita un t-contig con un consenso ?.
Multicoting: Resumen Admite repeticiones en algunos casos. Admite errores experimentales Modela la orientación desconocida Es un problema NP-Hard.
Repaso de Grafos Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole.
Repaso de Grafos Un grafo simple está formado por dos conjuntos: Un conjunto V de puntos llamados vértices o nodos. Un conjunto E de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. Notación: G(V,E) x x y
Repaso de Grafos A los ejes se les puede asignar un peso. Notación: w(x,y) Si hay más de un arco hablamos de un multigrafo Si los arcos se recorren en una en una dirección concreta pero no en la contraria lo llamamos grafo dirigido o dígrafo y los arcos son aristas x y 8 x y x y x y
Repaso de Grafos Un Camino es una secuencia de vértices V1, V2, V3, … , Vn, tal que cada para uno de estos V1->V2, V2->V3, V1->V3 Un Camino Simple es cuando todos sus vértices, excepto tal vez el primero y el último son distintos. Un Ciclo Simple es un camino simple de longitud por lo menos de uno que empieza y termina en el mismo vértice. Se dice que un grafo es aciclíco cuando no contiene ciclos. v1 v2 v3 v4 v1 v2 v3 v4 v1 v2 v3 v1 v2 v3
Representado el problema como un grafo Se representa con un grafo ya que resulta mas amigable para verlo visualmente, y se le esta aportando al problema, todo un conjunto de herramientas matemáticas para resolverlo.
Representado el problema como un grafo Datos del problema: Un conjunto de fragmentos F F = {ACTT, TTGTAA, AAGGT, TTGT, GTT, TTAG} Un string S S = ACTTGTAAGGTTGTTAAG El overlap de los fragmentos ACTT TTGTAA
Representado el problema como un grafo Datos del problema: El orden en que se hace el overlap ACTT TTGTAA TTGTAA ACTT La cantidad de nucleotidos que están en el overlap ACTT TTGTAA 2 nucleótidos
Representado el problema como un grafo Fragmentos son representados por los nodos o vértices. Los overlap’s son representados por los ejes que unen a los nodos. El orden del overlap de dos fragmentos, esta dado por la dirección del eje o arista. La cantidad de nucleótidos que estan en el overlap de dos fragmentos, esta representado por el peso de los ejes. El string s se representa como un camino en el grafo.
Representado el problema como un grafo Ejemplo: F={TACGA, ACCC, CTAAAG, GACA} a b c d a d c b 2 0 0 0 0 0 0 0 1 1 1 1
Representado el problema como un grafo Ejemplo: F={TACGA, ACCC, CTAAAG, GACA} a b c d a d c b 2 1 1 1 1
Representado el problema como un grafo Ejemplo: F={TACGA, ACCC, CTAAAG, GACA} a b c d
S1= TACGACCCCTAAAGACA S2= TACGACACCCTAAAG a d c b 2 1 1 1 1 a d c b 2 1 1 1 1
Representado el problema como un grafo Problema: Encontrar el superstring mas corto. Esto es equivalente a encontrar un camino hamiltoniano máximo dentro del grafo. Este problema es NP-Completo
| Página siguiente |