Методы ближайших соседей построения деревьев
Метод ближайших соседей (Neighbor-Joining) был разработан Неи и Сатои ( Saitou N.,Nei M., 1987 ). Метод основан на принципе поиска пар таксонов "соседей" таких, что суммарная длина всех ветвей будет минимальной на каждом этапе кластеризации таксонов.
Данный подход был усовершенствован Стадиром и Кепплером ( Studier J., Keppler K.J.,1988 ), которые предложили более экономную процедуру расчетов. Для каждой пары таксонов (i,j) рассчитывается текущая сумма длин ветвей:
Sij = (N-2)Dij - Ri - R j,
где Ri сумма всех Dij по k, а N - текущее число таксонов в матрице.
Среди всех полученных значений выбирается такая пара (i,j), для которой Sij будет наименьшим. Таксоны i и j заменяются на их предковый таксон u, для которого рассчитываются расстояния до остальных таксонов:
Duk = - (Dik + Djk - Dij ) (k не равно i,j).
Эта формула строго соблюдается для аддитивного дерева и является приближенной для неаддитивного. После объединения таксонов i и j в таксон u матрица расстояний сокращается на один таксон, и поиск пары с минимальным значением S повторяется до тех пор, пока не останется 3 таксона. ij
Смотрите также:
