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 :