DESS Bioinformatique, Université Blaise Pascal, Clermont-Ferrand, Février 2004

Reconstruction phylogénétiqueD'après Huson et al.

Édouard Barat

David Salgado

Vincent Zoonekynd

Introduction

• La plupart des algorithmes de reconstruction phylogénétique sont imprécis et instables.

• Généralement, pour corriger ces défauts, on prend plus de données.

• Mais on peut aussi essayer de “stabiliser” ces algorithmes.

Plan de la présentation

• Neighbor Joining et co.• Précision, stabilité, bipartitions, divergence• DCM (Disc Covering Method)• Conclusions et perspectives

Algorithmes de reconstruction phylogénétique

• Neighbor Joining (NJ)• BioNJ• Weighbor• Buneman (méthode Q*)• Single Pivot

Neighbor-Joining

• Idée 1 : minimiser la longueur de l'arbre• Idée 2 : minimiser la somme des carrés des

différences entre les distances observées et celles lues sur l'arbre.

•Méthode basée sur le principe d’évolution minimum.•Construction d’un arbre avec NJ.

1

2

3

…

j

i

1. On part d’un arbre étoile

Neighbor-Joining (1)

1

2

3

…

j

i

2. Choix de la meilleure paire ( i , j ).

1

2

3

…

j

i

3. Agglomération de cette paire et création d’un nouveau nœud u.

u

Neighbor-Joining (2)

4. Calcul des distances dans l’arbre entre u , i et j.

1

2

3

…

j

i

u

1

2

3

…

j

i

u

5. Calcul des distances dans la matrice entre u et les autres taxons (1, 2, 3, etc. …)

Neighbor-Joining (3)

6. « Oublie i et j » et recommence à l’étape 1. Terminequand il ne reste plus que 3 branches.

1

2

3

…

u

Remarques sur l’arbre obtenu :

• arbre non raciné.

• longueurs de branches = taux de mutation (et pas des temps !)

• évolution rapide, temps court = évolution lente, temps très long

Neighbor-Joining (4)

• C’est une amélioration de NJ : Différences entre NJ et BioNJ au niveau de

l’agglomération des 2 sous arbres traités :

NJ suppose implicitement que les deux estimations se

valent et leur accorde le même poids (1/2).

BioNJ choisit ces poids de manière à obtenir

l’estimateur de δu,x dont la variance est minimale. Les

agglomérations suivantes se font donc en s’ appuyant

sur de meilleures estimations des distances.

BioNJ (1)

BioNJ (2)

• BioNJ a une meilleure précision topologique que NJ .

• Efficace pour des taux d’évolutions importants et variables suivants les lignages.

• Même rapidité d’exécution que NJ.

Weighbor (weighted NJ)

• UPGMA : prendre les deux sommets les plus proches.

• NJ : prendre les deux sommets conduisant à l'arbre le plus parciminieux.

• Weighbor : prendre les deux sommets conduisant à l'arbre vraissemblablement le plus parcimonieux (maximum de vraissemblance). On tient compte de l'imprécision sur les distances : plus elles sont grandes, plus leur variance est grande.

Buneman (méthode Q*)

• Les algorithmes de reconstruction phylogénétique produisent des arbres binaires ; mais beaucoup de leurs arêtes sont des artefacts de la méthode utilisée.

• On peut préférer construire un arbre non binaire, mais dont on est sûr des arêtes.

• Avantage supplémentaire : la construction de l'arbre est alors polynomiale.

Buneman (méthode Q*)

• Calculer le score de Buneman de tous les quartets de taxa. β

wx,yz= min(wy+xz,wz+xy)−(wx+yz)

• Calculer le score de Buneman de toutes les bipartitions. β

U,V= min(β

wx,yz où x, w ∈ U, y, z ∈V)

• Reconstruire un arbre à l'aide des bipartitions de score positif, pondérées par leur score.

Plan de la présentation

• Neighbor Joining et co.

• Précision, stabilité, bipartitions, divergence

• DCM (Disc Covering Method)• Conclusions et perspectives

Stabilité

• Un algorithme de reconstruction phylogénétique est stable si, quand on modifie « un peu » les données, on obtient un arbre « proche ».

• Mais comment voir si deux arbres sont proches ?

Arêtes et bipartitions (1)

• Deux arbres sont proches s’ils ont beaucoup d’arêtes en commun. Mais comment comparer la présence d’arêtes ?

• Si on retire une arête à un arbre on obtient une partition des feuilles en deux ensembles : une bipartition.

• Deux arbres sont proches s'ils ont beaucoup de bipartitions communes.

Arêtes et bipartitions (2)

A

B

C

D

EF

AB | CDEF

ABC | DEF

ABCD | EF

Précision (1)

• Un faux positif est une arête présente dans l'arbre reconstruit pas mais pas dans l'arbre réel.

• Un faux négatif est une arête présente dans l'arbre réel mais pas dans l'arbre reconstruit.

Précision (2)

• On peut mesurer la précision à l'aide de deux nombres : le taux de faux positifs et le taux de faux négatifs.

• Si on veut un seul nombre, on peut faire la moyenne de ces deux taux.

• Si les arbres sont binaires, ces taux sont égaux.

Divergence

• C'est à cause de la présence de longues branches que les algorithmes de reconstruction sont imprécis.

• La divergence d'un arbre, c'est la longueur de sa plus grande branche.

Divergence

• Nous allons voir trois raisons pour lesquelles les arbres divergents donnent des reconstructions phylogénétiques imprécises :

• Le phénomène d'attraction des longues branches

• La parcimonie• La distribution de Poisson

Phénomène d'attraction des longues branches

A B

D

Arbre reconstruit

A B

DCC

Arbre réel

Parcimonie (1)

• Beaucoup d'algorithmes sont basés sur le principe de parcimonie : ils essayent de trouver l'arbre qui comporte le moins de mutations.

• C'est le cas, nous l'avons vu, du Neighbor Joining.

Parcimonie (2)

• Ces algorithmes vont plier, contorsionner les longues branches pour qu'elles apparaissent moins longues.

Distribution de Poisson

• On suppose généralement que les mutations forment un processus de Poisson : la longueur des branches suit donc une loi de Poisson.

• La variance d'une variable de Poisson, c'est aussi sa moyenne.

• Les longues branches ont une variance élevée, i.e., elles sont imprécises.

Simulations

• Choisir un arbre au hasard (soit simulé, soit à l'aide de données réelles) : c'est l'arbre vrai.

• Calculer la matrice de distances correspondante.

• Lui ajouter du bruit (loi de Poisson)• Calculer l'arbre• Calculer le nombre de faux positifs/négatifs.• Recommencer quelques milliers de fois.

Plan de la présentation

• Neighbor Joining et co.• Précision, stabilité, bipartitions, divergence

• DCM (Disc Covering Method)• Conclusions et perspectives

DCM (Disc Covering Method)

• Idée : comme les arêtes longues posent problème, on les enlève.

Élagage de la matrice de distances

• On ne peut pas retirer directement les « arêtes les plus longues », parce qu'on n'a pas encore d'arbre, on a juste une matrice de distances.

• Donc, on choisit une « distance seuil » et on retire les cases de la matrice de distances qui sont supérieures à ce seuil.

• On obtient une « matrice à trous ».

Exemple

Matrice de distances :

A B C D E FA 7 6 8 9 10B 5 15 11 12C 4 14 2D 1 13E 3F

Exemple

On garde les distances inférieures ou égales à 7 :

A B C D E FA 7 6 8 9 10B 5 15 11 12C 4 14 2D 1 13E 3F

Graphe de la matrice à trous

• On associe un graphe à notre matrice à trous, de la manière suivante.

• Les sommets sont les feuilles de l'arbre à construire, i.e., les lignes de la matrice, i.e., les colonnes de la matrice.

• Il y a une arête entre les sommets i et j si la case (i,j) de la matrice est toujours là.

Exemple

A

B C

F

D

E

Triangulation

• Si la matrice de distance est additive, le graphe ainsi obtenu est triangulé.

• Notre matrice est « proche » d'une matrice additive, le graphe est donc « proche » d'un graphe triangulé. S'il n'est pas triangulé, on le triangule, en utilisant une heuristique quelconque.

Triangulation (2)

Répéter : Choisir un sepmin non complet Le saturerJusqu'à ce qu'il n'y ait plus de sepmin non

complet.

Rappel : Un sepmin est un ensemble S de sommets dont le

complémentaire, non connexe, contient au moins deux

composantes connexes C1 et C2 telles que

Voisinage(C1)=Voisinage(C2)=S.

Exemple

B C

F

D

E

ATriangulation

Cliques maximales

• On ne peut pas donner directement notre matrice à trous aux algorithmes de reconstruction phylogénétique.

• On cherche les sous-matrices de distances sans trous les plus grandes possibles.

• En termes de graphes, on cherche les cliques maximales.

Cliques maximales (2)

• C'est principalement pour ça qu'on voulait un graphe triangulé : pour un graphe quelconque, trouver les cliques maximales est un problème NP complet, pour un graphe triangulé, c'est polynomial.

Cliques maximales : Algorithme

Calculer un ordre d'élimination des sommets

Tant qu'il reste des sommets : Prendre le premier sommet dans l'ordre,

x Le maxmod auquel il appartient et son

voisinage extérieur forment une clique maximale.

Retirer x et son maxmod.

Exemple

B C

F

D

E

ACliques Max

Recollement de la forêt

• On se retrouve avec une forêt; i.e., un ensemble d'arbres.

• Certains taxa apparaissent comme feuille de plusieurs arbres.

• On recolle ces arbres par consensus strict.

Consensus

• Exemple sur 3 arbres :

A

B

C D

EF

A

B

C

D

EF

A

B

C

D

EF

A

B

C D

E

F

AB | CDEF

ABC | DEF

ABCD | EF

AB | CDEF

ABEF | CD

ABCD | EF

AB | CDEF

ABF | CDE

ABCF | DE

Construction de l’arbre consensus

• Construction avec les bipartitions AB | CDEF et ABCD | EF

F

E

A

B

CD

1. On part d’un arbre en étoile

A B

CD E

F

A

B

C

D

E F

2. Séparation entre AB et CDEF

3. Séparation entre CD et EF

Déroulement de l’algorithme

1 2

5

4

3

6

1 2

3

47

1 2

5

4

3

6

1 2

3

47

1 2

53

1 2

3 4

Les 2 arbres Les nœuds en commun L’intersection

Déroulement de l’algorithme(2)

1 2

43

1 2

5

4

3

6

1 2

3

47

Consensus Arêtes à contracter

1 2

43

1 2

43

1 2

4

3

5

6

7

Arêtes à « recoller »

Déroulement de l’algorithme(3)

1

2

4

3

5

6

7

1

2

4

3

5

6

7

OU

CollisionOn ne sait pas dans quel ordre

mettre 6 et 7

1

2

4

3

5

6

7

Collisions

• Si le graphe triangulé est « suffisemment gros », i.e., si le seuil est suffisemment élevé, il n'y a pas de collisions.

Consensus et consensus strict

• Consensus : utilisation des bipartitions (arêtes) présentes dans au moins la moitié des arbres.

• Consensus strict : utilisation des bipartitions présentes dans tous les arbres.

Consensus

• Attention : les méthodes de consensus (strict, majoritaire ou glouton) font n'importe quoi quand les arbres à réunir sont trop différents.

Seuil

• Souvenez-vous : quand nous avons retiré les distances les plus élevées de la matrice de distances, nous avons du choisir un seuil : comment le choisir ?

• On ne le choisit pas : on prend tous les seuils possibles ; pour chaque seuil, on a un arbre ; on prend le consensus de ces arbres.

Données : une matrice de distances DA := tableau videPour chaque seuil : G := graphe_seuil(D, seuil) G := trianguler(G) T := forêt vide Pour H parmi les cliques maximales de G : ajouter NJ(D restreint à H) à T A[seuil] := consensus_strict(T) renvoyer consensus(A)

Algorithme

Plan de la présentation

• Neighbor Joining et co.• Précision, stabilité, bipartitions, divergence• DCM (Disc Covering Method)

• Conclusions et perspectives

Autres applications

• Amélioration d'algorithmes qui construisent à la fois un alignement multiple et un arbre.

• Amélioration d'algorithmes de reconstruction phylogénétique qui tiennent compte du transfert horizontal de gènes et qui produisent donc des graphes et non plus simplement des arbres.

Conclusions

• Cet algorithme permet de calculer des arbres phylogénétiques plus précis, plus rapidement, avec des données moins nombreuses.

• Le calcul est aussi plus rapide : on peut envisager de calculer des phylogénies sur plusieurs milliers de taxa.

Ce qu'il faut retenir

• Neighbor Joining• Divergence• arêtes et bipartitions• Consensus, strict ou non

Bibliographie

• D. Huson, S. Nettles, T. Warnow, Obtaining highly accurate estimates

of evolutionary trees from very short sequences, RECOMB 99

• V. Berry, D. Bryant, Faster reliable phylogenetic analysis, 1998

• J. Kim, T. Warnow, Tutorial on phylogenetic tree estimation, 2000

• M. Steel, A. Dress, S. Böcker, Simple but fundamental limitations on

supertree and consensus methods,