Метод присоединения соседей

Метод присоединения соседей (в лингвистике «метод ближайших соседей»^[2]) — алгоритм биоинформатики и лингвистики, разработанный Наруя Сайтоу и Масатоси Нэи в 1987 году^[3]. Это восходящий кластерный метод для создания филогенетических деревьев. Обычно используется для деревьев, основанных на ДНК или белковых последовательностях, в лингвистике — на данных лексикостатистики, реже фоно- или морфостатистики. Для его реализации необходимо вычислить расстояния между каждой парой таксонов (например, видов или последовательностей)^[4].

Алгоритм

Работа алгоритма начинается с полностью неразрешённого дерева с топологией «звезда»^[5].

Вычисляется матрица попарных расстояний между таксонами.
По текущей матрице расстояний считается $Q$ -матрица.
Ищется пара различных таксонов $i$ и $j$ (то есть $i\neq j$ ), для которых значение $Q(i,j)$ — наименьшее. Эти таксоны присоединяются к новому узлу, который, в свою очередь, соединяется с центральным узлом. На рисунке справа $f$ и $g$ присоединены к новому узлу $u$ .
Рассчитывается расстояние от каждого из присоединённых таксонов до нового узла.
Рассчитывается расстояние от каждого из оставшихся таксонов до нового узла.
Формируем новую матрицу попарных расстояний: из текущей матрицы удаляем строки и столбцы, соответствующие только что присоединённым таксонам и добавляем новую вершину и, вычисленные в 5 пункте, расстояния.
Повторяем шаги 2 — 5, пока дерево не станет полностью разрешённым и не станут известны длины всех ветвей.

Q-матрица

$Q$ -матрица рассчитывается по матрице расстояний между $n$ таксонами следующим образом^[5]:

$Q(i,j)=(n-2)d(i,j)-\sum _{k=1}^{n}d(i,k)-\sum _{k=1}^{n}d(j,k)$

$(1)$

где $d(i,j)$ − расстояние между таксонами $i$ и $j$ .

Расстояние между парой присоединённых соседей и новым узлом

Для каждого из присоединённых таксонов используется следующая формула для расчета расстояний до нового узла:

$\delta (f,u)={\frac {1}{2}}d(f,g)+{\frac {1}{2(n-2)}}\left[\sum _{k=1}^{n}d(f,k)-\sum _{k=1}^{n}d(g,k)\right]\quad$

$(2)$

и:

\delta (g,u)=d(f,g)-\delta (f,u)\quad

Таксоны $f$ и $g$ − пара присоединённых таксонов и $u$ − новый узел. Ветви $(f,u)$ и $(g,u)$ и их длины $\delta (f,u)$ и $\delta (g,u)$ − теперь фиксированная часть дерева; они не изменятся и ни на что не повлияют на следующих шагах алгоритма^[5].

Расстояние между оставшимися таксонами и новым узлом

Для каждого таксона, не участвовавшего в предыдущем шаге, рассчитывается расстояние до нового узла^[5]:

$d(u,k)={\frac {1}{2}}[d(f,k)+d(g,k)-d(f,g)]$

$(3)$

где $u$ — новый узел, $k$ — узел, до которого мы хотим рассчитать расстояние, $f$ и $g$ — таксоны только что присоединённой пары.

Сложность

Метод присоединения соседей для $n$ таксонов требует $n-3$ итерации^[5]. На каждой итерации требуется рассчитать $Q$ -матрицу. На первом шаге размер $Q$ -матрицы — $n\times n$ , на следующем шаге — $(n-1)\times (n-1)$ и так далее. Реализация алгоритма без оптимизации имеет сложность $O(n^{3})$ ; существуют реализации, использующие эвристический подход с меньшим временем выполнения в среднем.

Пример

Предположим, у нас есть пять таксонов $(a,b,c,d,e)$ со следующей матрицей расстояний:

	a	b	c	d	e
a	0	5	9	9	8
b	5	0	10	10	9
c	9	10	0	8	7
d	9	10	8	0	3
e	8	9	7	3	0

По формуле (1) вычислим $Q$ -матрицу (диагональные элементы матрицы не используются и здесь опущены):

	a	b	c	d	e
a		−50	−38	−34	−34
b	−50		−38	−34	−34
c	−38	−38		−40	−40
d	−34	−34	−40		−48
e	−34	−34	−40	−48

Наименьшее значение матрицы $Q(a,b)=-50$ , значит к новому узлу $u$ присоединяем таксоны $a$ и $b$ . Вычислим расстояния от $a$ и $b$ до $u$ по формуле (2):

\delta (a,u)={\frac {1}{2}}d(a,b)+{\frac {1}{2(5-2)}}\left[\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)\right]\quad ={\frac {5}{2}}+{\frac {31-34}{6}}=2

\delta (b,u)=d(a,b)-\delta (a,u)\quad =5-2=3

По формуле (3) вычисляем расстояния от новой вершины до оставшихся вершин:

d(u,c)={\frac {1}{2}}[d(a,c)+d(b,c)-d(a,b)]={\frac {9+10-5}{2}}=7

d(u,d)={\frac {1}{2}}[d(a,d)+d(b,d)-d(a,b)]={\frac {9+10-5}{2}}=7

d(u,e)={\frac {1}{2}}[d(a,e)+d(b,e)-d(a,b)]={\frac {8+9-5}{2}}=6

Таким образом, новая матрица попарных расстояний имеет вид:

	u	c	d	e
u	0	7	7	6
c	7	0	8	7
d	7	8	0	3
e	6	7	3	0

Соответствующая ей $Q$ -матрица:

	u	c	d	e
u		−28	−24	−24
c	−28		−24	−24
d	−24	−24		−28
e	−24	−24	−28

Теперь наша матрица принимает минимальное значение на двух парах: $u$ , $c$ и $d$ , $e$ . Конечное филогенетическое дерево не зависит от того, какую пару мы выберем. Для определённости, выберем $u$ и $c$ , присоединим их к новому узлу $v$ . Как и в первой итерации вычислим расстояния от $u$ и $c$ до $v$ . Они равны $\delta (u,v)=3$ и $\delta (c,v)=4$ . Расстояния от новой вершины $v$ до оставшихся узлов $d$ и $e$ равны:

d(v,d)={\frac {1}{2}}[d(u,d)+d(c,d)-d(u,c)]={\frac {7+8-7}{2}}=4

d(v,e)={\frac {1}{2}}[d(u,e)+d(c,e)-d(u,c)]={\frac {6+7-7}{2}}=3

Теперь матрица попарных расстояний имеет вид:

	v	d	e
v	0	4	3
d	4	0	3
e	3	3	0

Таким образом, мы получили полностью разрешённое дерево. Однако, для полноты стоит провести ещё одну итерацию:

Q_{3}(v,e)=(3-2)d(v,e)-\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(e,k)=3-7-6=-10

Матрица попарных расстояний:

	v	d	e
v		−10	−10
d	−10		−10
e	−10	−10

Выберем пару $v$ и $d$ и создадим новую вершину $w$ . Расстояния до этой вершины от вершин $v$ , $d$ , $e$ равны соответственно:

\delta (v,w)={\frac {1}{2}}d(v,d)+{\frac {1}{2(3-2)}}\left[\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(d,k)\right]\quad ={\frac {4}{2}}+{\frac {7-7}{2}}=2

\delta (w,d)=d(v,d)-\delta (v,w)=4-2=2

\delta (w,e)=d(v,e)-\delta (v,w)=3-2=1

Матрица смежности:

	w	v	d	e
w	0	2	2	1
v	2	0	4	3
d	2	4	0	3
e	1	3	3	0

Таким образом, мы узнали длины всех ветвей и получили полное филогенетическое дерево, показанное на рисунке. Приведённый пример представляет собой идеальный случай: заметим, что если двигаться от одного таксона к другому по ветвям дерева и суммировать длины пройденных ветвей, результат будет равен расстоянию между таксонами в первоначальной матрице расстояний. Например, пройдя от узла $d$ к узлу $b$ , мы получим $2+2+3+3=10$ . Про матрицу, в которой расстояния согласованы таким образом с каким-либо деревом, говорят, что она аддитивна — свойство, редко встречающееся на практике. Однако важно заметить: если на вход методу присоединения соседей подать аддитивную матрицу расстояний, гарантируется, что в результате работы метода будет построено дерево, согласованное с этой матрицей^[3].

Метод присоединения соседей как минимальная эволюция

Метод присоединения соседей можно рассматривать как жадный алгоритм для оптимизации дерева в соответствии с критерием «сбалансированной минимальной эволюции»^[6] (БМЭ). Для каждой топологии БМЭ определяет длину дерева (сумму длин ветвей) как взвешенную сумму расстояний из матрицы расстояний, с весами, зависящими от топологии дерева. Оптимальная топология БМЭ — та, при которой длина дерева минимальна. Метод присоединения соседей на каждой итерации соединяет пару таксонов, которые дадут наименьший вклад в длину строящегося дерева. Эта процедура не гарантирует нахождение дерева с топологией, оптимальной по критерию БМЭ, тем не менее, она часто находит оптимальное или близкое к оптимальному дерево.

Достоинства и недостатки

Главное достоинство метода в том, что он быстрый — в частности, из-за того, что алгоритм работает за полиномиальное время^[5]. Это делает его приемлемым для анализа больших объёмов данных (сотни или тысячи таксонов)^[5] и для бутстрэпа^[7] , для которых использование других методов анализа (например, максимальная экономия, метод максимального правдоподобия) затруднительно с точки зрения количества вычислений^[8].

Метод присоединения соседей имеет свойство выдавать правильное дерево на выходе, если на вход подается правильная матрица расстояний. Более того, правильная топология дерева гарантирована, если матрица расстояний «примерно аддитивна», то есть если каждое значение в матрице расстояний отличается от настоящего расстояния менее, чем на половину длины кратчайшей ветви дерева^[9].

На практике матрица расстояний редко удовлетворяет этому условию, но метод присоединения соседей часто выдает дерево с правильной топологией в любом случае^[10]. Метод присоединения соседей корректно работает с примерно аддитивной матрицей расстояний, потому что она статистически состоятельна для многих эволюционных моделей; имея входные данные подходящей длины, метод с высокой вероятностью восстановит настоящее дерево. По сравнению с UPGMA метод присоединения соседей имеет преимущество: он не предполагает, что все поколения эволюционируют с одинаковой скоростью (гипотеза молекулярных часов).

Тем не менее, вместо метода присоединения соседей часто применяют другие филогенетические методы, не полагающиеся на матрицу расстояний и обеспечивающие бо́льшую точность в большинстве случаев^[8].

Реализации и варианты

Существует много программ, реализующих метод присоединения соседей.

RapidNJ и NINJA — быстрые реализации, время работы которых обычно примерно пропорционально квадрату числа таксонов^[11]^[12].

BIONJ и Weighbor — варианты метода присоединения, повышающие его точность путём использования факта, что меньшие расстояния в матрице расстояний обычно лучше изучены, чем большие^[13]^[14].

FastME — реализация близкого метода сбалансированной минимальной эволюции^[15].

См. также

Примечания

↑ Saitou. Kyushu Museum. 2002. February 2, 2007 Архивировано 6 сентября 2013 года.
↑ Бурлак С. А., Старостин С. А. Сравнительно-историческое языкознание. — 2-е изд.. — Москва, 2005. — С. 270—271.
↑ ¹ ² Saitou N., Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees (англ.) // Molecular Biology and Evolution^[англ.] : journal. — Oxford University Press, 1987. — Vol. 4, no. 4. — P. 406—425. — PMID 447015. Архивировано 25 декабря 2014 года.
↑ Xavier Didelot. Sequence-Based Analysis of Bacterial Population Structures // Bacterial Population Genetics in Infectious Disease (англ.) / Robinson D. Ashley, Falush Daniel, Feil Edward J.. — John Wiley and Sons, 2010. — P. 46—47. — ISBN 978-0-470-42474-2.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Studier J. A., Keppler K. J. A note on the Neighbor-Joining algorithm of Saitou and Nei (англ.) // Molecular Biology and Evolution^[англ.] : journal. — Oxford University Press, 1988. — Vol. 5, no. 6. — P. 729—731. — PMID 3221794. Архивировано 16 декабря 2008 года.
↑ Gascuel O., Steel M. Neighbor-joining revealed (англ.) // Molecular Biology and Evolution^[англ.] : journal. — Oxford University Press, 2006. — Vol. 23, no. 11. — P. 1997—2000. — doi:10.1093/molbev/msl072. — PMID 16877499.
↑ Holmes S. Bootstrapping Phylogenetic Trees:Theory and Methods (англ.) // Statistical Science^[англ.] : journal. — 2003. — Vol. 18, no. 2. — P. 241—255.
↑ ¹ ² Penny D., Hendy M.D., Steel M. Progress with methods for constructing evolutionary trees (англ.) // Trends in Ecology and Evolution^[англ.] : journal. — 1992. — Vol. 7, no. 3. — P. 73—79. — doi:10.1016/0169-5347(92)90244-6. — PMID 21235960.
↑ Atteson K. (1997). "The performance of neighbor-joining algorithms of phylogeny reconstruction", pp. 101–110. In Jiang, T., and Lee, D., eds., Lecture Notes in Computer Science, 1276, Springer-Verlag, Berlin. COCOON '97.
↑ Mihaescu R., Levy D., Pachter L. Why neighbor-joining works (англ.) // Algorithmica^[англ.] : journal. — 2009. — Vol. 54, no. 1. — P. 1—24. — doi:10.1007/s00453-007-9116-4.
↑ Martin Simonsen, Thomas Mailund, Christian N., S. Pedersen. Rapid Neighbour Joining (неопр.) // Proceedings of the 8th WABI. — 2008. — Т. 5251. — С. 113—122. — doi:10.1007/978-3-540-87361-7_10. (недоступная ссылка)
↑ Martin Simonsen, Thomas Mailund, Christian N. S. Pedersen. Proceedings of the 8th Workshop in Algorithms in Bioinformatics (англ.). — Springer Verlag, 2008. — P. 113—122. — doi:10.1007/978-3-540-87361-7_10. Архивировано 10 июня 2016 года.
↑ Gascuel O. BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data (англ.) // Molecular Biology and Evolution^[англ.] : journal. — Oxford University Press, 1997. — Vol. 14, no. 7. — P. 685—695. — doi:10.1007/978-3-540-87361-7_10. Архивировано 25 апреля 2021 года.
↑ William J. Bruno, Nicholas D. Socci, Aaron L. Halpern. Weighted Neighbor Joining: A Likelihood-Based Approach to Distance-Based Phylogeny Reconstruction (англ.) // Molecular Biology and Evolution^[англ.] : journal. — Oxford University Press, 2000. — Vol. 17, no. 1. — P. 189—197.
↑ Desper R., Gascuel O. Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle (англ.) // Journal of Computational Biology^[англ.] : journal. — 2002. — Vol. 9, no. 5. — P. 687—705. Архивировано 25 апреля 2021 года.

Ссылки

The Neighbor-Joining Method — руководство (англ.)

[1] Saitou. Kyushu Museum. 2002. February 2, 2007 Архивировано 6 сентября 2013 года.

[2] Бурлак С. А., Старостин С. А. Сравнительно-историческое языкознание. — 2-е изд.. — Москва, 2005. — С. 270—271.

[saitou-3] ¹ ² Saitou N., Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees (англ.) // Molecular Biology and Evolution^[англ.] : journal. — Oxford University Press, 1987. — Vol. 4, no. 4. — P. 406—425. — PMID 447015. Архивировано 25 декабря 2014 года.

[4] Xavier Didelot. Sequence-Based Analysis of Bacterial Population Structures // Bacterial Population Genetics in Infectious Disease (англ.) / Robinson D. Ashley, Falush Daniel, Feil Edward J.. — John Wiley and Sons, 2010. — P. 46—47. — ISBN 978-0-470-42474-2.

[studier-5] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Studier J. A., Keppler K. J. A note on the Neighbor-Joining algorithm of Saitou and Nei (англ.) // Molecular Biology and Evolution^[англ.] : journal. — Oxford University Press, 1988. — Vol. 5, no. 6. — P. 729—731. — PMID 3221794. Архивировано 16 декабря 2008 года.

[gascuel-6] Gascuel O., Steel M. Neighbor-joining revealed (англ.) // Molecular Biology and Evolution^[англ.] : journal. — Oxford University Press, 2006. — Vol. 23, no. 11. — P. 1997—2000. — doi:10.1093/molbev/msl072. — PMID 16877499.

[7] Holmes S. Bootstrapping Phylogenetic Trees:Theory and Methods (англ.) // Statistical Science^[англ.] : journal. — 2003. — Vol. 18, no. 2. — P. 241—255.

[all_methods-8] ¹ ² Penny D., Hendy M.D., Steel M. Progress with methods for constructing evolutionary trees (англ.) // Trends in Ecology and Evolution^[англ.] : journal. — 1992. — Vol. 7, no. 3. — P. 73—79. — doi:10.1016/0169-5347(92)90244-6. — PMID 21235960.

[9] Atteson K. (1997). "The performance of neighbor-joining algorithms of phylogeny reconstruction", pp. 101–110. In Jiang, T., and Lee, D., eds., Lecture Notes in Computer Science, 1276, Springer-Verlag, Berlin. COCOON '97.

[levy-10] Mihaescu R., Levy D., Pachter L. Why neighbor-joining works (англ.) // Algorithmica^[англ.] : journal. — 2009. — Vol. 54, no. 1. — P. 1—24. — doi:10.1007/s00453-007-9116-4.

[11] Martin Simonsen, Thomas Mailund, Christian N., S. Pedersen. Rapid Neighbour Joining (неопр.) // Proceedings of the 8th WABI. — 2008. — Т. 5251. — С. 113—122. — doi:10.1007/978-3-540-87361-7_10. (недоступная ссылка)

[12] Martin Simonsen, Thomas Mailund, Christian N. S. Pedersen. Proceedings of the 8th Workshop in Algorithms in Bioinformatics (англ.). — Springer Verlag, 2008. — P. 113—122. — doi:10.1007/978-3-540-87361-7_10. Архивировано 10 июня 2016 года.

[13] Gascuel O. BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data (англ.) // Molecular Biology and Evolution^[англ.] : journal. — Oxford University Press, 1997. — Vol. 14, no. 7. — P. 685—695. — doi:10.1007/978-3-540-87361-7_10. Архивировано 25 апреля 2021 года.

[14] William J. Bruno, Nicholas D. Socci, Aaron L. Halpern. Weighted Neighbor Joining: A Likelihood-Based Approach to Distance-Based Phylogeny Reconstruction (англ.) // Molecular Biology and Evolution^[англ.] : journal. — Oxford University Press, 2000. — Vol. 17, no. 1. — P. 189—197.

[15] Desper R., Gascuel O. Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle (англ.) // Journal of Computational Biology^[англ.] : journal. — 2002. — Vol. 9, no. 5. — P. 687—705. Архивировано 25 апреля 2021 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Метод присоединения соседей

Содержание

Алгоритм

Q-матрица

Расстояние между парой присоединённых соседей и новым узлом

Расстояние между оставшимися таксонами и новым узлом

Сложность

Пример

Метод присоединения соседей как минимальная эволюция

Достоинства и недостатки

Реализации и варианты

См. также

Примечания

Ссылки

Навигация

Метод присоединения соседей

Алгоритм

Q-матрица

Расстояние между парой присоединённых соседей и новым узлом

Расстояние между оставшимися таксонами и новым узлом

Сложность

Пример

Метод присоединения соседей как минимальная эволюция

Достоинства и недостатки

Реализации и варианты

См. также

Примечания

Ссылки

Навигация

Поиск