UPGMA
Un article de Wikipédia, l'encyclopédie libre.
UPGMA (Unweighted Pair Group Method with Arithmetic mean) est un algorithme qui prend en entrée une matrice de distances entre plusieurs séquences (par exemple de nucléotides), et renvoie un arbre phylogénétique enraciné.
La matrice de distance contient pour chaque paire de séquences une distance entre les deux, obtenue après un alignement. On effectue alors la boucle suivante, tant que la matrice a plus d'un élément :
- on trouve dans la matrice la paire de séquences de distance minimale.
- on les rejoint dans l'arbre phylogénétique, et on supprime de la matrice les lignes et colonnes de ces deux séquences.
- on insère dans la matrice une ligne et une colonne correspondant au consensus des deux séquences supprimées, en prenant simplement pour valeurs de la ligne (resp: colonne) la moyenne arithmétique des deux lignes (resp. colonnes) dont elle est le consensus.
Cette méthode, rapide, présente toutefois un point faible : elle suppose que tous les temps d'évolution de toutes les séquences ont été les mêmes. En effet, supposons qu'après une spéciation, la séquence considérée évolue beaucoup dans une espèce et pas dans l'autre : elles seront alors très différentes, et le critère de distance minimale dans la matrice ne permettra pas de les relier. Ainsi, cette espèce qui a évolué le plus, très différente de toutes les autres, pourrait être accrochée en toute fin d'algorithme à la racine de l'arbre.
La technique du Neighbour Joining permet d'éviter cette limitation.
