Матричные алгоритмы построения деревьев
Алгоритмы матричного построения деревьев: 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.
