Ensamblamiento de fragmentos de ADN (página 2)

Partes: 1, 2

Bibliotecas genómicas
Como no es posible secuenciar un genoma en una sola reacción de secuenciación se lo divide en fragmentos, los cuales se almacenan en clones bibliotecas genómicas.
Una biblioteca genómica es un conjunto de clones, cada uno de los cuales contiene un fragmento de un genoma de un organismo dado.
Las bibliotecas genómicas se consiguen clonando los fragmentos en vectores.

Clonado de fragmentos

Vectores de clonado utilizados para secuenciación de genomas
Fago ?
Cósmido
YAC

Vectores de Clonado
Problema de los YACs

Vectores de Clonado
Otros vectores que incluyen insertos de gran tamaño:
Bacteriógafos P1
BACs
PACs
Fósmidos

Sizes of human genomic libraries prepared in different types of cloning vector
Number of clones*
Type of vector
Insert size (kb)
P = 95%
P = 99%
l replacement
18
532 500
820 000
Cosmid, fosmid
40
240 000
370 000
P1
125
77 000
118 000
BAC, PAC
300
32 000
50 000
YAC
600
16 000
24 500
Mega-YAC
1400
6850
10 500
(Gp:) * Calculated from the equation:where N is the number of clones required, P is the probability that any given segment of the genome is present in the library, a is the average size of the DNA fragments inserted into the vector, and b is the size of the genome.

Ensamblado:Shotgun approach
Consiste en ensamblar directamente los fragmentos de ADN secuenciados por superposición.

Haemophilus influenzae
1995
1830 kb, biblioteca genómica
18.638 clones,
insertos de 1,6-2 kb.

Resolución de gaps

Los contigs se pueden construir por chromosome walking

Ensamblado:Clone Contig Approach
Se clonan fragmentos de hasta 1,5 Mb en YACs o BACs.
Se construye un contig identificando los clones que contienen fragmentos superpuestos, los cuales se secuencian por el método de shotgun.

Whole genome shotgun sequencing
La experiencia con el método de shotgun en genomas chicos mostró que si el largo total de la secuencia que se genera es 6,5-8 veces el largo de la secuencia total del genoma estudiado, entonces los contigs resultantes ocuparan el 99,8% de la secuencia del genoma, con unos gaps tales que se pueden resolver facilmente.
70 millones de fragmentos de 500pb resolverían el genoma humano en 3 anos con 75 secuenciadores, cada uno de los cuales puede secuenciar 1000 secuencias de esas por días.

(Gp:) Ejemplo de genomas de los cuales se ha publicado la secuencia en versión completa o borrador

(Gp:) Especie

(Gp:) Tamaño del genoma (Mb)

(Gp:) Nro de genes estimados

(Gp:) Eukarya

(Gp:) Arabidopsis thaliana (plant)

(Gp:) 125

(Gp:) 25 500

(Gp:) Caenorhabditis elegans (nematode)
(Gp:) 97

(Gp:) 19 000

(Gp:) Drosophila melanogaster (fruit fly)

(Gp:) 180

(Gp:) 13 600

(Gp:) Homo sapiens (human)

(Gp:) 3200

(Gp:) 30 000 – 40 000

(Gp:) Saccharomyces cerevisiae (yeast)

(Gp:) 12.1

(Gp:) 5800

(Gp:) Eubacteria

(Gp:) Escherichia coli K12

(Gp:) 4.64

(Gp:) 4400

(Gp:) Mycobacterium tuberculosis H37Rv

(Gp:) 4.41

(Gp:) 4000

(Gp:) Mycoplasma genitalium

(Gp:) 0.58

(Gp:) 500

(Gp:) Pseudomonas aeruginosa PA01

(Gp:) 6.26

(Gp:) 5700

(Gp:) Streptococcus pneumoniae

(Gp:) 2.16

(Gp:) 2300

(Gp:) Vibrio cholerae El Tor N16961

(Gp:) 4.03

(Gp:) 4000

(Gp:) Yersinia pestis CO92

(Gp:) 4.65

(Gp:) 4100

(Gp:) Archeae

(Gp:) Archaeoglobus fulgidus

(Gp:) 2.18

(Gp:) 2500

(Gp:) Methanococcus jannaschii

(Gp:) 1.66

(Gp:) 1750

Complicaciones
Instancias reales del problema muy largas
Errores
Inserciones
Deleciones
sustituciones
Fragmentos quiméricos
Orientación desconocida
Regiones repetidas
Pérdida de cobertura (gaps)

Segunda Parte
SubModelos

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

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.

Tercera Parte
SubAlgoritmos

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

Algoritmos
GreedyAplica al modelo SCS y Reconstruction

Subgrafo AcíclicoAplica al modelo Multiconting

Algoritmo Greedy
En cada paso intenta maximizar la solución del subproblema analizad. No retrocede una vez tomada cada decisión.

Algoritmo Greedy
Construimos un grafo dirigido a partir del multigrafo formado por los fragmentos de F, dejando entre cada par de nodos únicamente las aristas mas pesadas, ya que estamos buscando el camino mas pesado

Algoritmo Greedy
Entrada: Grafo orientado con n vértices.
Salida: Camino hamiltoniano en el grafo de entrada
//Inicio
Para i< -1 hasta n
in[i] < -0 //cuantos ejes entran en i
out[i] < -0 // cuantos ejes salen de i
MakeSet(i)
//Proceso
Ordenar los ejes de acuerdo a a su peso, con el mas pesado primero
Para cada eje (f,g) en ese orden
Si in[g] = 0 y out[f] = 0 y FindSet(f) =/= FindSet(g)
seleccionamos el eje (f,g)
in[g] < – 1
out[f] < – 1
Union(FindSet(f), FindSet(g))
Si queda una sola componente
terminar
Retornar los ejes seleccionados

Algoritmo Greedy
La solución encontrada es a lo sumo 2,75 veces peor que la optima, y se conjetura que lo es 2 veces.
Este algoritmo, no siempre encuentra una solución.
TGCAT
ATGC
GCC
3
2
2

Algoritmo Subgrafo Acíclico
Este algoritmo restringe la hipótesis, asumiendo que los fragmentos están libres de errores, que se conoce la orientación y que fueron obtenidos de un buen secuenciamiento.
Se entiende por buen secuenciamiento, básicamente, a que los fragmentos cubren a la molécula en su totalidad y que se garantiza el overlap.

Algoritmo Subgrafo Acíclico
Dado un multigrafo con los fragmentos en los nodos, obtenemos un grafo dirigido, quedándonos con las aristas de mayor peso entre los nodos, ya que queremos encontrar el camino mas pesado.
Luego quitamos todas las aristas que tengan un peso menor al t-contig deseado. De forma tal que quede un subgrafo acíclico
Luego se busca un camino hamiltoniano máximo en el subgrafo acíclico. Esto es polinomial y se puede resolver con un algoritmo greedy.

Algoritmo Subgrafo Acíclico
Ejemplo:Consideremos que queremos llegar al string S y tenemos los fragmentos w, z, u, x e yS = AGTATTGGCAATCGATGCAAACCTTTTGGCAATCACTw = AGTATTGGCAATC z = AATCGATGu = ATGCAAACCTx = CCTTTTGGy = TTGGCAATCACTY se pide un t-contig de 3

Algoritmo Subgrafo Aciclico
El subgrafo acíclico de de los overlap’s quedaría de la siguiente forma:
4
9
3
3
4

Heurística
Buscar overlap
Para cada par de fragmentos, calcular el match prefijo-sufijo.
Usar el algoritmo de programación dinámica de alineamiento semiglobal sin penalidad.
Ordenar los fragmentos
Construir el camino con un algoritmo greedy o heurística
Cada camino tiene su correspondiente camino complementario
No es necesario incluir fragmentos incluidos en otros
Los ciclo y cubrimientos abundantes pueden indicar repeticiones.
Alineamiento y consenso

Bibliografía
Brown, T. A., Genomes, 2002, 2nd. Edition, BIOS Scienfic Publishers, Ltd.
Griffiths A., Miller J., Suzuki D. & Lewontin R, An Introduction to Genetic Analysis, 2000, 7th ed. Freeman & Company
Meidanes
Prevner
Baxevanis