filogenética molecular (i)webdiis.unizar.es/asignaturas/bio/wp-content/uploads/2015/05/2003… ·...

Filogenéticamolecular (I)

Bioinformática, 18-3-20Parcialmente basado enKevin Yip-CSE-CUHK (Universidad china de Hong-Kong)

HOY …

• Árboles: Las estructuras jerárquicasrelacionando diferentes objetos biológicos1. Formatos de archivo2. Reconstrucción de árboles filogenéticos3. Métodos basados   en distancia

• UPGMA• Unión de vecinos

4. Métodos basados en secuencias• máxima parsimonia• Máxima verosimilitud

– Distancia evolutiva y modelos de mutación

Clasificación de las especies

Crédito de la imagen: Wikipedia, http://ridge.icu.ac.jp/gen‐ed/classif‐gifs/animal‐class‐example.gif

Dominios y reinos

El Reino animal

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

taxonomía

Crédito de la imagen: Wikipedia, http://www2.estrellamountain.edu/faculty/farabee/biobk/BioBookDivers_class.html

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

escalas más finas

• La misma idea se puede aplicar a clasificar diferentes cepas de un tipo de bacteria

• O incluso o a las relaciones familiares

Crédito de la imagen: Hershberg et al, Genome Biology. 8: R164 (2007), http://www.accessexcellence.org/RC/VL/GG/images/pedigree.gif, http://www.jdrf.ca/

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Relacionar objetos biológicos• ¿Cómo se han determinado

las jerarquías?– Especie: tradicionalmente por las similitudes morfológicas y de comportamiento, o evidencias paleontológicas

– Las cepas bacterianas: por propiedades biológicas físicas, químicas y

• Pregunta: ¿Qué característicasdeben ser usadas antes?

– Miembros de la familia: por pedigrí / genealogía

Crédito de la imagen: http://www2.estrellamountain.edu/faculty/farabee/biobk/BioBookDivers_class.html

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Filogenia

• Una manera sistemática y objetiva para construir estos árboles es mediante la comparación de las secuencias de DNA / proteínas

• Estudiamos aquí los árboles que relacionan los objetos suficientemente diferentes– Especies diferentes– Las diferentes cepas / poblaciones de una especie

• Nuestro objetivo es reconstruir las relaciones evolutivas reales en base a secuencias observables

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

suposiciones• supuestos básicos detrás de los árboles filogenéticos:

1. Las secuencias actuales comparten un ancestro común2. Todas mutaron a partir del ancestro común3. Las mutaciones son raras. Por tanto, si los DNA de A y B 

son más similares que los de A y C, y que los de B y C, probablemente C se separó de A y B antes de su separación

A B C

ancestro común de A y B

ancestro común de A, B y C

tiempo

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Terminología• Un árbol es un grafo acíclico con 

nodos conectados por aristas• Un árbol filogenético es un árbol 

binario con secuencias (nodos) conectados por ramas (aristas)– Los nodos hoja son las secuencias 

observadas– Los nodos internos son las 

secuencias ancestrales no observadas

– El nodo raíz es el ancestro común de todas las secuencias observadas

– Las longitudes de las ramaspueden representar distancias evolutivas

Raíz

Una rama

Crédito de la imagen: Hershberg et al, Genome Biology. 8: R164 (2007), http://www.jdrf.ca/

Un nodo internoUn nodo hoja

longitud de la rama

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Árboles con y sin raíz

• A veces no está muy claro dónde incluir el ancestro común– Podemos tener un árbol sin raíz

Crédito de la imagen: Lowery et al,. oncogén 24 (2): 248‐259, (2005)

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

HOY …

• Árboles: Las estructuras jerárquicas relacionandodiferentes objetos biológicos1. Formatos de archivo2. Reconstrucción de árboles filogenéticos3. Métodos basados   en distancia

• UPGMA• Unión de vecinos

4. Métodos basados en secuencias• máxima parsimonia• Máxima verosimilitud

– Distancia evolutiva y modelos de mutación

formatos de archivo comunes para los árboles filogenéticos

• Newick (paréntesis anidados, con distancias)• NEXUS (dando identificaciones cortas para secuencias, con más metadatos)

• PhyloXML (utilizando la estructura de XML)

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

formatos de archivo comunes• Ejemplo

((((Homo:0,21, Pongo:0,21):0,28, Macaca: 0,49):0,13, Ateles:0,62):0,38, Galago:1,00);

newick:

NEXUS:

Crédito de la imagen: http://www.zoology.ubc.ca/~schluter/zoo502stats/Rtips.phylogeny.html

Representación grafica:

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

BEGIN TAXA;DIMENSIONS NTAX = 5;TAXLABELS

HomoPongoMacacaAtelesGalago

;END;BEGIN TREES;

TRANSLATE1 Homo,2 Pongo,3 Macaca,4 Ateles,5 Galago

;TREE * UNTITLED = [&R]

((((1:0.21,2:0.21):0.28,3:0.49):0.13,4:0.62):0.38,5:1);END;

formatos de archivo comunes• PhyloXML

Fuente de información: http://www.phyloxml.org/examples_syntax/phyloxml_syntax_example_1.htmlBMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

<phyloxml xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.phyloxml.org" xsi:schemaLocation="http://www.phyloxml.org http://www.phyloxml.org/1.10/phyloxml.xsd">

<phylogeny rooted="true"><name>Alcohol dehydrogenases</name><description>contains examples of commonly used elements</description><clade>

<events><speciations>1</speciations>

</events><clade>

<taxonomy><id provider="ncbi">6645</id><scientific_name>Octopus vulgaris</scientific_name>

</taxonomy><sequence>

<accession source="UniProtKB">P81431</accession><name>Alcohol dehydrogenase class-3</name>

</sequence></clade>...

</clade></phylogeny>

</phyloxml>

El formato Newick• Utiliza paréntesis y coma para agrupar dos subárboles• Usa dos puntos para indicar la distancia a los padres, si está disponible• Termina con un punto y coma

((((Homo: 0,21, Pongo: 0,21): 0,28, Macaca: 0,49): 0,13, Ateles: 0,62): 0,38, Galago: 1,00);

newick:

Crédito de la imagen: http://www.zoology.ubc.ca/~schluter/zoo502stats/Rtips.phylogeny.html

Representación grafica:

0.21

0.210.28

0.49

0.13

0.62

0.38

1.00

observaciones:• Para un árbol sin raíz, de una manera sencilla para representarlo utilizando el formato Newick es poniendo una raíz de manera arbitraria

• Se pueden nombrar a los nodos internos, dando la etiqueta después del paréntesisde cierre (por ejemplo, (Homo: 0,21, Pongo: 0,21) HP: 0,28

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

HOY …

• Árboles: Las estructuras jerárquicas relacionandodiferentes objetos biológicos1. Formatos de archivo2. Reconstrucción de árboles filogenéticos3. Métodos basados   en distancia

• UPGMA• Unión de vecinos

4. Métodos basados en secuencias• máxima parsimonia• Máxima verosimilitud

– Distancia evolutiva y modelos de mutación

reconstrucción de árboles filogenéticos

• problema general:– Dado un conjunto de secuencias / proteínas de DNA, encontrar un árbol filogenético de tal manera que probablemente corresponde a los eventos evolutivos históricos reales, describiendo:

• Cómo se conectan los nodos: Orden de eventos de separación

• Lo secuencias en los nodos internos: secuencias ancestrales• Cuánto tiempo ha pasado desde que la separación: longitudde rama

Hay varias formas de evaluar la probabilidad de que un árbolsea correcto. Vamos a estudiarlas

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

reconstrucción de árboles filogenéticos

– "Re" ‐Construcción: El árbol fue definido por la historia. Nosotros sólo tratamos de reconstruirlo desde las secuencias observadas

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

¿Qué secuencias usar?

• Si estamos estudiando un gen– secuencia de DNA / proteína del gen

• Si queremos conocer la relación entre las diferentes especies– el genoma completo (puede no ser factible)– Algunos genes que evolucionan lentamente

• RNA ribosomal

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

La complejidad del problema• Encontrar el "mejor" árbol es un problema difícil

– ¿Cuántas (es decir, ignorando longitudes de rama y el orden de izquierda a derecha) son las topologías de árboles para un conjunto de k secuencias?

– Para los árboles enraizados:• k = 2: 1 posible topología de árbol• k = 3: 3 ramas posibles para añadir # 3• k = 4: 5 posibles para añadir # 4, y así sucesivamente• Por lo tanto el número de topologías de árboles es

1 3  5  ... (2k‐3) ‐ Exponencial

– Una vez más, la enumeración de todas las topologíaspara encontrar la mejor opción es imposible

1 2 1 3 2 1 3 21 2 3

k Num. of rooted tree topologies

2 1

3 3

4 15

5 105

6 945

7 10,395

8 135,135

9 2,027,025

10 34,459,425

11 654,729,075

12 13,749,310,575

13 316,234,143,225

14 7,905,853,580,625

15 213,458,046,676,875

16 6,190,283,353,629,370

17 191,898,783,962,511,000

18 6,332,659,870,762,850,000

19 221,643,095,476,700,000,000

20 8,200,794,532,637,890,000,000

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

La complejidad del problema

• Del mismo modo, para los árboles sin raíces,– k = 2: 1 topología – k = 3: 1 forma de añadir # 3– k = 4: 3 formas de agregar # 4– k = 5: 5 formas de añadir # 5– El número de topologías es

1 3  5  ...  (2k‐5)

1

2

1

2

3

1

2

3

1

2

3

1

2

3

4

4

4

k Num. of rooted tree topologies Num. of unrooted tree topologies

2 1 1

3 3 1

4 15 3

5 105 15

6 945 105

7 10,395 945

8 135,135 10,395

9 2,027,025 135,135

10 34,459,425 2,027,025

11 654,729,075 34,459,425

12 13,749,310,575 654,729,075

13 316,234,143,225 13,749,310,575

14 7,905,853,580,625 316,234,143,225

15 213,458,046,676,875 7,905,853,580,625

16 6,190,283,353,629,370 213,458,046,676,875

17 191,898,783,962,511,000 6,190,283,353,629,370

18 6,332,659,870,762,850,000 191,898,783,962,511,000

19 221,643,095,476,700,000,000 6,332,659,870,762,850,000

20 8,200,794,532,637,890,000,000 221,643,095,476,700,000,000

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

La solución del problema: Ideas

• ¿Qué se hace cuando se encuentra un problema difícil computacionalmente?– Definir una versión más fácil del problema

• hacer ciertos supuestos

– Diseñar algoritmos / estructuras de datos inteligentes para evitar cálculos redundantes

– Usar heurísticas para resolverlo, no obteniendo necesariamente la solución óptima

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

métodos de reconstrucción de árboles filogenéticos

• Existen dos tipos principales de métodos:– basados en secuencias: necesitan las secuencias

• métodos de parsimonia (problemas más fáciles, algoritmos inteligentes)

• métodos probabilísticos (problemas más fáciles, algoritmos inteligentes)

– Máxima verosimilitud– bayesiano

• ...– basados en la distancia: sólo dependen de las distancias entre 

las secuencias• UPGMA (heurística)• vecino más próximo (heurística)• ...

– Vamos a estudiar algunos de estos algoritmos

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

HOY …

• Árboles: Las estructuras jerárquicas relacionandodiferentes objetos biológicos1. Formatos de archivo2. Reconstrucción de árboles filogenéticos3. Métodos basados   en distancia

• UPGMA• Unión de vecinos

4. Métodos basados en secuencias• máxima parsimonia• Máxima verosimilitud

– Distancia evolutiva y modelos de mutación

Motivación• En los anteriores algoritmos basados   en secuencias, las secuencias exactas se utilizan en la reconstrucción de los árboles filogenéticos

• En un método basado en distancia, sólo se consideran las distancias entre pares de secuencias – Es bueno si las secuencias son largas, y sólo nos preocupa la estructura de árbol, pero no las secuencias ancestrales

– Las distancias se pueden calcular por métodos basados   en la alineación de secuencias (pero hay distancias calculables sin alineamiento)

– Una vez que las distancias por pares se han calculado, no se utilizarán las secuencias originales

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Distancias basadas en compresión

• Tenemos un algoritmo de compresión, sea |compresión(x)| la longitud del output con entrada x

• El ratio de compresión es  C(x)=

• ¿Para saber la distancia de un string x a un string y?– Comparamos C(xy) con C(x) y C(y)

|compresión(x)||x|

0 ≤ C(x) ≤ 1

Distancias basadas en compresión

• Hay varias opciones

• NCD(x,y)=

• CBD(x,y)=

• Cálculo de la distancia tan eficiente como el algoritmo de compresión 

C(xy)-min{C(x), C(y)}

max{C(x), C(y)}

2 C(xy)

C(x) + C(y)-1

Construcción de árboles filogenéticos

• Dos métodos basados en distancias:– UPGMA– Unión de vecinos

UPGMA• Unweighted Pair Group Method with Arithmetic Mean

• Algoritmo:1.Calcular la distancia entre cada par de secuencias2. Tratar a cada secuencia como un grupo por sí mismo3.Combinar los dos grupos más cercanos. La distancia entre dos grupos es la distancia media entre todas sus secuencias (excepto que d (Ci, Ci) = 0):

(Nótese que d (r,s) es la distancia entre r y s en la matriz de distancia de entrada)

4. Repetir 2 y 3 hasta que sólo quede un cluster

d Ci, Cj1

|Ci| Cjd 𝑟, 𝑠

𝑟∈Ci ,𝑠∈Cj

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

EjemploA B C D E

A 0 8 4 6 8

B 8 0 8 8 4

C 4 8 0 6 8

D 6 8 6 0 8

E 8 4 8 8 0

A B C D E

{A},{C}

A,C B D E

A,C 0 8 6 8

B 8 0 8 4

D 6 8 0 8

E 8 4 8 0

A C B D E

2 2

A,C B,E D

A,C 0 8 6

B,E 8 0 8

D 6 8 0

A C B E D

2 2 2 2

{A,C}, {D}

{B},{E}

A,C,D B,E

A,C,D 0 8

B,E 8 0

A C B ED

2 2 2 2

13

{A,C,D}, {B,E} A,B,C,D,E

A,B,C,D,E 0

A C B ED

2 2 2 2

13

12

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Empates, hojas no alineadas• No siempre es posible poner todas las hojas en una línea:

A B C

A 0 4 6

B 4 0 4

C 6 4 0

A B C

{B},{C} A B,C

A 0 5

B,C 5 0

A B C2 2

{A},{B,C} A,B,C

A,B,C 0

BC

A1

3

12

{A},{B}

A,B C

A,B 0 5

C 5 0

A B C2 2

{A,B},{C}A,B,C

A,B,C 0

AB C31

12

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Longitudes de rama• No siempre es posible asignar longitudes de rama de acuerdo a las distancias:

A B C

A 0 4 8

B 4 0 2

C 8 2 0

A B C

{B},{C}

A B,C

A 0 6

B,C 6 0

A B C1 1

{A},{B,C} A,B,C

A,B,C 0

B CA 1 1

33

Aquí las brach lengths sólo reflejan las distancias de clúster, no las distancias de secuencia

HOY …

• Árboles: Las estructuras jerárquicas relacionandodiferentes objetos biológicos1. Formatos de archivo2. Reconstrucción de árboles filogenéticos3. Métodos basados   en distancia

• UPGMA• Unión de vecinos

4. Métodos basados en secuencias• máxima parsimonia• Máxima verosimilitud

– Distancia evolutiva y modelos de mutación

Unión de vecinos• En UPGMA, cada vez que se fusionan los dos grupos más cercanos según su distancia (criterio nº 1):

• Sería bueno elegir el grupo que también está muy lejos de otros grupos (criterio nº 2), medidos por:

u Ci d Ci, Cjj

d Ci, Cj1

|Ci| Cjd 𝑟, 𝑠

𝑟∈Ci ,𝑠∈Cj

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Unión de vecinos

• En el algoritmo unión de vecinos, los dos grupos que fusionar es el par que minimiza

,donde r es el número actual de grupos(y Q (i, i)  0 para todo i)

– La fórmula considera ambos criterios, mientras que el factor (r‐2) es para equilibrar sus pesos relativos

Q i, j r 2 d Ci, Cj u Ci u Cj

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Unión de vecinos

• El algoritmo:1. Comienza con cada secuencia como un clúster. 

Todos ellos están conectados a un centro, formando una estrella.

2. Encontrar grupos i y j conectados al centro donde Q (i, j) es mínimo entre todos los pares de cluster

3. Insertar un nuevo nodo interno Ck (que minimiza Q desde k a (i,j))

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Unión de vecinos

2. Encontrar grupos i y j conectados al centro donde Q (i, j) es mínimo entre todos los pares de cluster

3. Insertar un nuevo nodo interno Ck(que minimiza Q)• Conectarlo a Ci, Cj y el centro• Asignar la longitud a CiCk

• Asignar la longitud a CjCk

• Para cada nodo Cl, d(Ck, Cl) = [d(Ci, Cl) + d(Cj, Cl) ‐ d(Ci, Cj)] / 2(todos los d (Cx, Cy) son valores ya calculados).

4. Repetir 2 y 3 hasta que todas las longitudes de rama se asignen• El resultado final será un árbol sin raíces

d Ci, Cj2

u Cj u Ci2 r 2

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

d Ci, Cj2

u Ci u Cj2 r 2  

Ejemplod A B C D

A 0 8 4 6

B 8 0 8 8

C 4 8 0 6

D 6 8 6 0

{A}, {C}

u

A 18

B 24

C 18

D 20

Q A B C D

A 0 ‐26 ‐28 ‐26

B ‐26 0 ‐26 ‐28

C ‐28 ‐26 0 ‐26

D ‐26 ‐28 ‐26 0

A B

CD

A C

BD

2 2d A,C B D

A,C 0 6 4

B 6 0 8

D 4 8 0

u

A,C 10

B 14

D 12

Q A,C B D

A,C 0 ‐18 ‐18

B ‐18 0 ‐18

D ‐18 ‐18 0

{A,C}, {B}

d A,B,C D

A,B,C 0 3

D 3 0

u

A,B,C 3

B 3

A C

BD

2 21

53

Q(i,j) = (r-2)d(Ci,Cj) – u(Ci) – u(C

Distancia entre A y el nuevo nodo: d(A,C)/2 + [u(A) –u(C)] / [2(r-2)] = 4/2 + (18-18) / [2(2)] = 2

En el último paso, quitamos el centro y escribimos la 

distancia

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Comparando los resultados• UPGMA: (con un nodo más, E)

• Neighbor Joining:

A C B ED

2 2 2 2

13

12

A C

BD

2 21

53

BMEG3102 Bioinformatics | Kevin Yip-cse-cuhk | Spring 2016

Más sencillo

Mayor posibilidad de distancias significativas

Resumen de distancias

• A partir de una matriz de distancias se construye el árbol

• No es necesario conocer la topología• Tampoco está claro que necesite bootstraps• La distancia puede ser con o sin alineamiento

BMEG3102 Bioinformatics |  Kevin Yip‐cse‐cuhk | Spring 2016

PRÓXIMO DÍA …

• Árboles: Las estructuras jerárquicas relacionandodiferentes objetos biológicos1. Formatos de archivo2. Reconstrucción de árboles filogenéticos3. Métodos basados   en distancia

• UPGMA• Unión de vecinos

4. Métodos basados en secuencias• máxima parsimonia• Máxima verosimilitud

– Distancia evolutiva y modelos de mutación