Unweighted pair group method with arithmetic mean

UPGMA (Unweighted pair group method with arithmetic mean) est le nom d'un algorithme destiné à la construction d'un arbre phylogénétique. Cette méthode permet la transformation d'une matrice de distances (entre différents organismes, populations, ou séquences de nucléotides) en un arbre enraciné.

Description

La matrice fournit l'ensemble des distances entre toutes les paires d'éléments. L'algorithme fonctionne par itérations successives, qui réduisent progressivement la taille de la matrice. Chaque itération voit le regroupement des deux éléments restants séparés par la plus faible distance: ces éléments sont associés dans l'arbre, et sont remplacés par un élément « consensus ». Les nouvelles distances entre cet élément consensus et les éléments restants dans la matrice sont recalculées par la moyenne arithmétique des deux éléments regroupés, soit :

${1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y)$

Critique et historique

Cette méthode simple et rapide présente toutefois de nombreux biais. En particulier, elle suppose que la vitesse d'évolution est constante dans toutes les branches. Par conséquent, si une branche « interne » évolue beaucoup plus vite que toutes les autres, elle ne sera rattachée au reste de l'arbre qu'à la dernière étape et sera à l'extérieur de l'arbre (le phénomène est similaire à l'attraction des longues branches).

Les défauts de l'UPGMA sont tels que l'algorithme n'a plus qu'un intérêt historique dans le cadre de l'inférence d'un arbre phylogénétique. Il a en effet été remplacé depuis lors par des méthodes plus avancées (comme le Neighbour Joining ou la parcimonie dans un premier temps, puis les techniques de maximum de vraisemblance ou algorithmes bayesiens utilisés aujourd'hui en phylogénie). Cet algorithme reste cependant utilisé dans le cadre de l'alignement de séquences, où il permet de déterminer l'ordre dans lequel les séquences vont être alignées. En effet l'objectif de cet arbre guide est de regrouper les séquences les plus similaires, indépendamment de leur vitesse d'évolution ou de leurs parentés phylogénétique et c'est précisément ce que fait UPGMA.

La méthode est généralement attribuée à Sokal et Michener. Fionn Murtagh propose lui un algorithme s'exécutant en $O(n^{2})$.