Описание алгоритма UPGMA (к занятию 14)

  
     

Входом алгоритма UPGMA является матрица расстояний между набором объектов. В нашем случае объекты — это последовательности белков. Выходом алгоритма является (ультраметрическое) филогенетическое дерево объектов. Иными словами, на выходе имеем филогенетическое дерево, листья которого соответствуют нашим последовательностям. При описании алгоритма будем сразу называть наши последовательности "листьями".

Первый шаг алгоритма состоит в следующем:

  • Выбираем наименьшее число в матрице расстояний. Если сразу несколько чисел имеют одинаковое (и меньшее остальных) значение, выбираем одно из них случайным образом. Запоминаем пару листьев, расстояние между которыми минимально (назовем их A и B).
  • Создаем новый узел дерева. Соединяем его ребрами с выбранными листьями A и B.
  • Приписываем вновь созданным ребрам одинаковые длины, равные половине значения расстояния между A и B (взятого из входной матрицы расстояний).
  • Создаем новую матрицу расстояний. Объекты, расстояния между которыми описаны матрицей, теперь двоякого рода: это, во первых, все листья, кроме A и B, а во-вторых, множество ("кластер") {A,B}. Расстояния между листьями остаются теми же, что были во входной матрице, а расстояние от произвольного листа X до кластера {A,B} считается по формуле: d(X,{A,B}) = (d(X,A)+d(X,B))/2, где расстояния d(X,A) и d(X,B) берутся из входной матрицы (то есть расстояние до кластера полагаем равным среднему арифметическому двух расстояний до его элементов).
В результате первого шага у нас есть "деревце" с двумя листьями A и B и матрица расстояний между остальными листьями и этим деревцем. На втором шаге мы выбираем наименьшее значение в этой новой матрице расстояний. Возможны два варианта: наименьшее из расстояний в новой матрице будет расстоянием между двумя листьями, отличными от A и B, или же оно будет расстоянием от какого-либо листа C до кластера {A,B}. В первом случае поступаем точно так же, как на шаге 1, и получаем два "деревца"-кластера и матрицу расстояний между кластерами и оставшимися листьями. Во втором случае новый узел дерева следует соединить ребрами с листом C и с узлом, отвечающим кластеру {A,B}. Будем говорить, что этот новый узел отвечает кластеру {A,B,C}; он является корнем дерева с листьями {A,B,C}. Ребру, ведущему из нового узла в лист C, приписывается длина, равная половине расстояния d(C,{A,B}). Другому ребру приписывается длина d(C,{A,B}) – ρ, где ρ — длина ребра, ведущего из узла {A,B} в лист A (или в лист B — эти длины равны между собой). Заметим, что расстояние по дереву от нового узла до всех трех листьев A, B, C одинаково.

Теперь опишем единым образом все шаги алгоритма.

Будем считать, что перед очередным шагом мы имеем: а) набор кластеров, то есть подмножеств множества листьев; б) матрицу расстояний между кластерами; в) для каждого кластера — дерево, у которого множество листьев есть данный кластер. При этом:

  • В матрице расстояний расстояние между кластерами есть среднее арифметическое входных расстояний между всеми парами (X,Y), где X — из первого кластера, а Y — из второго.
  • Расстояние по дереву от корня каждого из имеющихся деревьев до любого из его листьев одинаково (будем называть это число "высотой" соответствующего кластера).
  • Листья, пока не попавшие в кластеры, считаем кластерами из одного элемента (дерево кластера при этом состоит из одного узла, он же корень и единственный лист).
Тем самым описанная ситуация имеет место, в частности, и перед самым первым шагом.

Очередной шаг состоит в следующем:

  • Выбираем наименьшее число в матрице расстояний и запоминаем соответствующую пару кластеров. Если сразу несколько чисел имеют одинаковое (и меньшее остальных) значение, выбираем случайным образом пару кластеров, расстояние между которыми минимально. Создаем новый узел и соединяем его ребрами с узлами, соответвующими выбранным кластерам.
  • Приписываем каждому из вновь созданных ребер длины по формуле: L = d – ρ, где d — расстояние между кластерами, а ρ — высота кластера.
  • Объединяем выбранные кластеры в один.
  • Если новое число кластеров больше двух, создаем новую матрицу расстояний. Расстояние между кластерами полагаем равным среднему арифметическому всех расстояний между листьями этих кластеров.
  • Если число кластеров равно двум, то создаем корень выходного дерева, соединяем его ребрами с узлами, соответствующими двум имеющимся кластерам, приписываем этим ребрам длины в соответствии с вышеприведенной формулой и завершаем работу.
В результате очередного шага мы либо имеем уже построенное дерево, либо имеем ситуацию, позволяющую перейти к следующему аналогичному шагу.

Примечания

  1. UPGMA расшифровывается как Unweighted Pair Group Method with Arithmetic Mean. Выражение "Pair Group Method" отвечает общей схеме алгоритма, а "Unweighted" и "Arithmetic Mean" — способу вычисления расстояний между кластерами.
  2. Если на входе было три последовательности, то алгоритм заканчивается после первого шага. Если же на входе было две последовательности, то алгоритм (как и любой другой алгоритм построения деревьев) теряет смысл — дерево с двумя листьями может быть только одно.