CHAPITRE 3. ÉTAT DE L' ART
démontrer que pour n gènes, il existe
C(n) = (2n-3)!
22n-2(n-2)!
topologies d'arbre binaire
possibles.
Cette méthode a le mérite de
générer tous les arbres possibles pour un ensemble de
gènes donné. Néanmoins, son utilisation demeure
limitée à cause de sa complexité qui croit à un
rythme exponentiel en fonction du nombre de feuilles
(C(30)estsuprieur1038). Conséquemment, la
recherche exhaustive ne peut se faire sur des données de grandes
tailles.
3.1.2 Construction d'arbres à partir des distances
entre feuilles
Cette approche prend en entrée une matrice de distance
donnant les distances entre les gènes deux à deux, puis construit
progressivement l'arbre phylogénétique des feuilles de l'arbre
vers la racine. Nous décrivons ci-après deux méthodes
basées sur cette approche [11] : la méthode Unweighted Pair Group
Method with Arithmetic Mean (UPGMA) et la méthode Neighbour Joining
(NJ).
3.1.2.1 UPGMA
UPGMA est un algorithme permettant, à partir d'une
matrice de distance de construire un arbre enraciné en un sommet qui est
le plus distant des feuilles. Cette méthode est simple et intuitive.
Les principales étapes de UPGMA
sont:
1. Initialiser l'ensemble des noeuds (groupes
1) de l'arbre à l'ensemble des
gènes
2. De façon itérative, jusqu'à ce qu'il ne
reste plus qu'un groupe :
~ Créer un nouveau groupe regroupant deux groupes les
plus proches et retirer ces deux groupes de la liste des groupes.
~ Ajouter dans l'arbre un nouveau noeud correspondant au
nouveau groupe, comme parent des deux noeuds correspondant aux groupes
retirés.
L'arbre est construit des feuilles vers la racine, en ajoutant un
noeud à chaque itération. À chaque étape, on
définit la distance entre deux groupes Ci et Cj comme
>
suit : dij = 1
pECi,qECj dpq. Si Ck
= Ci ? Cj la distance entre Ck et un autre
|Ci||Cj|
groupe Cl est donnée par la formule récursive
suivante : dklj =
dil|Ci|+djl|Cj|
|Ci|+|Cj|
.
La figure 3.1 montre un exemple d'application de UPGMA
3.1.2.2 Neighbour Joining
Neighbour Joining est un autre algorithme dédié
à la construction des d'arbres phylogénétiques tenant
compte des différences de vitesse d'évolution sur les branches
1. Un groupe est un ensemble de données partageant des
caractéristiques communes.
| 
