Modelos para el estudio de ADN (página 2)

Partes: 1, 2

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