Qu'est ce qu'une phylogénie Mesures de distances entre arbres

Qu’est ce qu’une phylogénie ?
Mesures de distances entre arbres
Construction de consensus d’arbres
Comparaison d’arbres
Application à la reconstruction de phylogénies
1Vincent Berry
Equipe Méthodes et Algorithmes pour la Bioinformatique
L.I.R.M.M. (Université Montpellier II - C.N.R.S.)
http://www.lirmm.fr/~vberry
Merci à l’ ACI IMP Bioet au prog. BIO STIC UM2.
Vincent Berry Comparaison d’arbres - EJC’05Qu’est ce qu’une phylogénie ?
Mesures de distances entre arbres
Construction de consensus d’arbres
1 Qu’est ce qu’une phylogénie ?
Définition par l’exemple
Pourquoi comparer des phylogénies
Formalismes de description d’arbres
2 Mesures de distances entre arbres
Ensembles de bipartitions (RF) et de quadruplets
Distance d’élagage
Echanges de plus proches voisins (NNI)
Transferts de sous arbre (SPR)
Complexité du calcul des distances
3 Construction de consensus d’arbres
Consensus Strict
Sous arbre d’Accord Maximum (MAST)
Vincent Berry Comparaison d’arbres - EJC’05Qu’est ce qu’une phylogénie ? Définition par l’exemple
Mesures de distances entre arbres Pourquoi comparer des phylogénies
Construction de consensus d’arbres Formalismes de description d’arbres
Vincent Berry Comparaison d’arbres - EJC’05Qu’est ce qu’une phylogénie ? Définition par l’exemple
Mesures de distances entre arbres Pourquoi comparer des phylogénies
Construction de consensus d’arbres Formalismes de description d’arbres
Pourquoi comparer des phylogénies ?
Pour reconstruire l’histoire d’un groupe d’espèces, on
dispose de plusieurs jeux de données.
Il existe de nombreuses méthodes pour inférer une
phylogénie depuis un jeu de données.
Certaines méthodes produisent plusieurs arbres optimaux.
=⇒ nécessité de comparer les phylogénies inférées
Concrêtement
DISTANCES ENTRE ARBRESmesurer leur degré d’hétérogénéité :
ARBRES CONSENSUSdéterminer leurs points communs :
Vincent Berry Comparaison d’arbres - EJC’05Qu’est ce qu’une phylogénie ? Définition par l’exemple
Mesures de distances entre arbres Pourquoi comparer des phylogénies
Construction de consensus d’arbres Formalismes de description d’arbres
Pourquoi comparer des phylogénies ?
Pour reconstruire l’histoire d’un groupe d’espèces, on
dispose de plusieurs jeux de données.
Il existe de nombreuses méthodes pour inférer une
phylogénie depuis un jeu de données.
Certaines méthodes produisent plusieurs arbres optimaux.
=⇒ nécessité de comparer les phylogénies inférées
Concrêtement
DISTANCES ENTRE ARBRESmesurer leur degré d’hétérogénéité :
ARBRES CONSENSUSdéterminer leurs points communs :
Vincent Berry Comparaison d’arbres - EJC’05Qu’est ce qu’une phylogénie ? Définition par l’exemple
Mesures de distances entre arbres Pourquoi comparer des phylogénies
Construction de consensus d’arbres Formalismes de description d’arbres
Pourquoi comparer des phylogénies ?
Réponse à plusieurs questions du biologiste par comparaison
de phylogénies
présence d’artefacts de construction (attraction de longues
branches)
données partiellement erronées (paralogie)
détection de transferts horinzontaux (événements
recombinants)
construction de super arbres
Vincent Berry Comparaison d’arbres - EJC’05Qu’est ce qu’une phylogénie ? Définition par l’exemple
Mesures de distances entre arbres Pourquoi comparer des phylogénies
Construction de consensus d’arbres Formalismes de description d’arbres
Formalismes pour décrire des arbres enracinés
Définition
Une classe (ou clade) est l’ensemble des
feuilles se trouvant sous un même noeud
u
de l’arbre.
d e
Exemplea c
b La classe{a, b, c} est induite par le
noeud interne u.
Vincent Berry Comparaison d’arbres - EJC’05Qu’est ce qu’une phylogénie ? Définition par l’exemple
Mesures de distances entre arbres Pourquoi comparer des phylogénies
Construction de consensus d’arbres Formalismes de description d’arbres
Formalismes pour décrire des arbres enracinés
Définition
Une classe (ou clade) est l’ensemble des
feuilles se trouvant sous un même noeud
u de l’arbre.
d e
Propriétéa c
b Un arbre enraciné est défini de façon
unique par son ensemble de classes.
Vincent Berry Comparaison d’arbres - EJC’05Qu’est ce qu’une phylogénie ? Définition par l’exemple
Mesures de distances entre arbres Pourquoi comparer des phylogénies
Construction de consensus d’arbres Formalismes de description d’arbres
Formalismes pour décrire des arbres enracinés
Remarque
Un ensemble de classes n’est pas
forcément compatible, i.e., ne définit pas
f un arbre.
Exemplea b c d
{{a, b, c} ,{b, c, d} , ...}
Vincent Berry Comparaison d’arbres - EJC’05Qu’est ce qu’une phylogénie ? Définition par l’exemple
Mesures de distances entre arbres Pourquoi comparer des phylogénies
Construction de consensus d’arbres Formalismes de description d’arbres
Formalismes pour décrire des arbres enracinés
Définition
Un triplet est le sous arbre minimal
reliant trois feuilles.
d e
Example
a c L’arbre de la figure induit l’ensemble de
b
triplets{ab|c, ab|d, ac|d,..., cd|e}.
Vincent Berry Comparaison d’arbres - EJC’05