Матричные алгоритмы построения деревьев

Алгоритмы матричного построения деревьев: UPGMA, WPGMA, NNM, FNM, UPGMC, WPGMC Работа перечисленных матричных методов построена по одному принципу, основанному на итеративной обработке матрицы расстояний между таксонами. На каждом шаге в матрице расстояний D ищется минимальный элемент Dij. Найденные таксоны i и j объединяются, образуя новый таксон k. Строки и столбцы, соответствующие таксонам i и j, выбрасываются из матрицы D и добавляется новая строка и новый столбец, соответствующие таксону k. В результате матрица сокращается на одну строку и один столбец. Эта процедура повторяется до тех пор, пока не будут объединены все таксоны.

Разные матричные методы отличаются лишь способом вычисления расстояний от вновь образуемого на каждом шаге таксона k до всех оставшихся таксонов. В общей форме расстояние между таксоном k и любым другим таксоном l для всех шести методов можно записать с помощью формулы:

D{lkl}l = a{li }lD{lil }l+ a{lj }lD{ljl }l+ b{lj }lD{lij }l+ g *D{lil }l- D{ljl}l* 

где коэффициенты ai , aj , b j, g различны для разных методов.

При расчете коэффициентов может использоваться информация о числе объединяемых в один более крупный таксон исходных таксонов самого нижнего ранга, т.н. OTU (Operational Taxonomic Units). Пусть таксоны i, j и k содержат ti , t jи tk OTU, соответственно. Если таксон k образуется путем объединения таксонов i и j, то

tk = t i+ tj

 Конкретные значения коэффициентов для разных методов определяются следующим образом: 

Метод ближайших соседей (Nearest Neighbor) 

ai = 0.5, aj = 0.5, b j= 0, g = -0.5;  

Метод удаленных соседей (Furthest Neighbor) 

a i= 0.5, aj = 0.5, bj = 0, g = 0.5;

 UPGMA (Arithmetic Average) 

ai = ti /tl , a j= tj /t l, b j= 0, g = 0;

 WPGMA (Weighted Average) 

ai = 0.5, aj = 0.5, b j= 0, g = 0

 UPGMC (Unweighted Centroid) 

a i= ti /tl , aj = tj /tl  , bj  = - (t it j)/(tl  t l ), g = 0; 

 WPGMC (Weighted Centroid) 

ai = 0.5, aj = 0.5, bj = -0.25, g = 0 

Более детальное изложение этих методов можно найти в книге: Peter H. A., Sneath R. S. , "Numerical Taxonomy. The principles and practice of numerical classification", 1973.

Ссылки: