UPGMA – схема алгоритма

• Укоренённое дерево строится «снизу вверх»

• Найдём в матрице расстояний наименьший элемент.

• Объединим два ближайших листа в кластер (это – узел дерева, соединённый ветвями с листьями, образовавшими его).

• Пересчитаем матрицу расстояний, рассматривая кластер как новый лист. Расстоянием до кластера будем считать среднее арифметическое расстояний до его элементов (отсюда название метода).

• Повторяем с начала, пока не останется всего два кластера.

• К этому прибавляется способ вычисления длин ветвей.

• Результат — укоренённое ультраметрическое дерево с длинами ветвей.