Присоединение соседа

Метод кластеризации снизу вверх для создания филогенетических деревьев

В биоинформатике метод объединения соседей представляет собой метод кластеризации снизу вверх (агломеративный) для создания филогенетических деревьев , созданный Наруей Сайто и Масатоши Неем в 1987 году. ^[1] Обычно основанный на данных о последовательностях ДНК или белков , алгоритм требует знания расстояния между каждой парой таксонов (например, видов или последовательностей) для создания филогенетического дерева. ^[2]

Алгоритм

Начиная со звездного дерева (A), матрица Q вычисляется и используется для выбора пары узлов для объединения, в данном случае f и g. Они объединяются с новым созданным узлом u, как показано на (B). Часть дерева, показанная сплошными линиями, теперь фиксирована и не будет изменена на последующих этапах объединения. Расстояния от узла u до узлов ae вычисляются из уравнения ( 3 ). Затем этот процесс повторяется, используя матрицу только расстояний между узлами a, b, c, d, e и u, и матрицу Q, полученную из нее. В этом случае u и e объединяются с новым созданным v, как показано на (C). Еще две итерации приводят сначала к (D), а затем к (E), и в этот момент алгоритм завершается, поскольку дерево полностью решено.

Neighbor joining принимает матрицу расстояний , которая определяет расстояние между каждой парой таксонов , в качестве входных данных. Алгоритм начинается с полностью неразрешенного дерева, топология которого соответствует топологии звездной сети , и повторяет следующие шаги, пока дерево не будет полностью разрешено, и все длины ветвей не будут известны:

1. На основе текущей матрицы расстояний вычислите матрицу (определенную ниже). ${\displaystyle Q}$
2. Найдите пару различных таксонов i и j (т.е. с ), для которой наименьшее значение. Создайте новый узел, который соединяет таксоны i и j, и соедините новый узел с центральным узлом. Например, в части (B) рисунка справа узел u создается для соединения f и g. ${\displaystyle i\neq j}$ ${\displaystyle Q(i,j)}$
3. Рассчитайте расстояние от каждого таксона в паре до этого нового узла.
4. Рассчитайте расстояние от каждого таксона за пределами этой пары до нового узла.
5. Запустите алгоритм снова, заменив пару присоединенных соседей новым узлом и используя расстояния, рассчитанные на предыдущем шаге.

Q-матрица

На основе матрицы расстояний, связывающих таксоны, вычислите матрицу x следующим образом: ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle Q}$

где — расстояние между таксонами и . ${\displaystyle d(i,j)}$ ${\displaystyle i}$ ${\displaystyle j}$

Расстояние от членов пары до нового узла

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

и:

${\displaystyle \delta (g,u)=d(f,g)-\delta (f,u)\quad }$

Таксоны и являются парными таксонами и является вновь созданным узлом. Ветви, соединяющие и и и , и их длины, и являются частью дерева, которое постепенно создается; они не влияют и не подвергаются влиянию последующих шагов по присоединению соседей. ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle u}$ ${\displaystyle f}$ ${\displaystyle u}$ ${\displaystyle g}$ ${\displaystyle u}$ ${\displaystyle \delta (f,u)}$ ${\displaystyle \delta (g,u)}$

Расстояние других таксонов от нового узла

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

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

Сложность

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

Пример

Объединение соседей с 5 таксонами. В этом случае 2 шага объединения соседей дают дерево с полностью разрешенной топологией. Ветви полученного дерева помечены их длинами.

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

Первый шаг

Первое присоединение

Рассчитываем значения по уравнению ( 1 ). Например: ${\displaystyle Q_{1}}$

${\displaystyle Q_{1}(a,b)=(n-2)d(a,b)-\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)}$

${\displaystyle =(5-2)\times 5-(5+9+9+8)-(5+10+10+9)=15-31-34=-50}$

Получаем следующие значения матрицы (диагональные элементы матрицы здесь не используются и опущены): ${\displaystyle Q_{1}}$

В приведенном выше примере . Это наименьшее значение , поэтому мы объединяем элементы и . ${\displaystyle Q_{1}(a,b)=-50}$ ${\displaystyle Q_{1}}$ ${\displaystyle a}$ ${\displaystyle b}$

Оценка длины первой ветви

Пусть обозначает новый узел. Согласно уравнению ( 2 ), выше, ветви, соединяющие и , тогда имеют длины: ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$

${\displaystyle \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}$

${\displaystyle \delta (b,u)=d(a,b)-\delta (a,u)\quad =5-2=3}$

Первое обновление матрицы расстояний

Затем мы переходим к обновлению исходной матрицы расстояний в новую матрицу расстояний (см. ниже), уменьшенную в размере на одну строку и один столбец из-за объединения с их соседом . Используя уравнение ( 3 ) выше, мы вычисляем расстояние от до каждого из других узлов, кроме и . В этом случае мы получаем: ${\displaystyle D}$ ${\displaystyle D_{1}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$

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

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

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

Результирующая матрица расстояний имеет вид: ${\displaystyle D_{1}}$

Выделенные жирным шрифтом значения соответствуют вновь рассчитанным расстояниям, тогда как выделенные курсивом значения не затронуты обновлением матрицы, поскольку они соответствуют расстояниям между элементами, не участвующими в первом объединении таксонов. ${\displaystyle D_{1}}$

Второй шаг

Второе присоединение

Соответствующая матрица: ${\displaystyle Q_{2}}$

Мы можем выбрать либо присоединение и , либо присоединение и ; обе пары имеют минимальное значение , и любой выбор приводит к одному и тому же результату. Для конкретности давайте присоединим и и назовем новый узел . ${\displaystyle u}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle Q_{2}}$ ${\displaystyle -28}$ ${\displaystyle u}$ ${\displaystyle c}$ ${\displaystyle v}$

Оценка длины второй ветви

Длины ветвей, соединяющих и можно рассчитать: ${\displaystyle u}$ ${\displaystyle c}$ ${\displaystyle v}$

${\displaystyle \delta (u,v)={\frac {1}{2}}d(u,c)+{\frac {1}{2(4-2)}}\left[\sum _{k=1}^{4}d(u,k)-\sum _{k=1}^{4}d(c,k)\right]\quad ={\frac {7}{2}}+{\frac {20-22}{4}}=3}$

${\displaystyle \delta (c,v)=d(u,c)-\delta (u,v)\quad =7-3=4}$

Объединение элементов и расчет длины ветвей помогают нарисовать дерево объединения соседей, как показано на рисунке.

Второе обновление матрицы расстояний

Теперь вычисляется обновленная матрица расстояний для оставшихся трех узлов, , и : ${\displaystyle D_{2}}$ ${\displaystyle v}$ ${\displaystyle d}$ ${\displaystyle e}$

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

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

Последний шаг

Топология дерева на этом этапе полностью решена. Однако для ясности мы можем вычислить матрицу . Например: ${\displaystyle Q_{3}}$

${\displaystyle 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}$

Для конкретности соединим и и назовем последний узел . Длины трех оставшихся ветвей можно вычислить: ${\displaystyle v}$ ${\displaystyle d}$ ${\displaystyle w}$

${\displaystyle \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}$

${\displaystyle \delta (w,d)=d(v,d)-\delta (v,w)=4-2=2}$

${\displaystyle \delta (w,e)=d(v,e)-\delta (v,w)=3-2=1}$

Дерево объединения соседей теперь готово, как показано на рисунке.

Вывод: аддитивные расстояния

Этот пример представляет собой идеализированный случай: обратите внимание, что если мы перейдем от любого таксона к любому другому вдоль ветвей дерева и просуммируем длины пройденных ветвей, результат будет равен расстоянию между этими таксонами во входной матрице расстояний. Например, переходя от к мы имеем . Матрица расстояний, расстояния которой согласуются таким образом с некоторым деревом, называется «аддитивной», что редко встречается на практике. Тем не менее, важно отметить, что при наличии аддитивной матрицы расстояний в качестве входных данных, присоединение соседей гарантированно найдет дерево, расстояния между таксонами которого согласуются с ней. ${\displaystyle d}$ ${\displaystyle b}$ ${\displaystyle 2+2+3+3=10}$

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

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

Преимущества и недостатки

Главное достоинство NJ заключается в том, что он быстрый ^{[6] : 466} по сравнению с методами наименьших квадратов , максимальной экономии и максимального правдоподобия . ^[6] Это делает его практичным для анализа больших наборов данных (сотни или тысячи таксонов) и для бутстреппинга , для которых другие средства анализа (например, максимальная экономия , максимальное правдоподобие ) могут быть вычислительно непомерно обременительными.

Соединение соседей имеет свойство, что если входная матрица расстояний верна, то выходное дерево будет верным. Более того, правильность топологии выходного дерева гарантируется, пока матрица расстояний является «почти аддитивной», в частности, если каждая запись в матрице расстояний отличается от истинного расстояния менее чем на половину длины самой короткой ветви в дереве. ^[7] На практике матрица расстояний редко удовлетворяет этому условию, но соединение соседей часто в любом случае создает правильную топологию дерева. ^[8] Правильность соединения соседей для почти аддитивных матриц расстояний подразумевает, что оно статистически последовательно во многих моделях эволюции; при наличии данных достаточной длины соединение соседей восстановит истинное дерево с высокой вероятностью. По сравнению с UPGMA и WPGMA , соединение соседей имеет то преимущество, что оно не предполагает, что все родословные развиваются с одинаковой скоростью ( гипотеза молекулярных часов ).

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

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

Существует множество программ, реализующих присоединение соседей. Среди реализаций канонического NJ (т. е. использующих классические критерии оптимизации NJ, поэтому дающих те же результаты) RapidNJ (запущен в 2003 г., крупное обновление в 2011 г., все еще обновляется в 2023 г.) ^[9] и NINJA (запущен в 2009 г., последнее обновление в 2013 г.) ^[10] считаются передовыми. Их типичное время выполнения примерно пропорционально квадрату числа таксонов.

Варианты, отклоняющиеся от канонических, включают в себя:

• BIONJ (1997) ^[11] и Weighbor (2000), ^[12] улучшают точность, используя тот факт, что более короткие расстояния в матрице расстояний, как правило, лучше известны, чем более длинные. Оба метода были расширены для работы на неполных матрицах расстояний. ^[13]
• «Fast NJ» запоминает лучший узел и всегда имеет O(n^2); «relax NJ» выполняет поиск с восхождением на вершину и сохраняет наихудшую сложность O(n^3). Rapid NJ быстрее, чем простой relax NJ. ^[14]
• FastME — это реализация тесно связанного метода сбалансированной минимальной эволюции (BME) (см. § Присоединение соседей как минимальная эволюция). Он примерно такой же быстрый и более точный, как NJ. Он начинается с грубого дерева, а затем улучшает его с помощью набора топологических ходов, таких как обмены ближайшими соседями (NNI). ^[15] FastTree — это связанный метод. Он работает с «профилями» последовательностей вместо матрицы. Он начинается с приблизительного дерева NJ, перестраивает его в BME, а затем перестраивает в приблизительное максимальное правдоподобие. ^[16]

Смотрите также

• Поиск ближайшего соседа
• UPGMA и WPGMA
• Минимальная эволюция

Ссылки

1. Сайто, Н.; Ней, М. (1 июля 1987 г.). «Метод объединения соседей: новый метод реконструкции филогенетических деревьев». Молекулярная биология и эволюция . 4 (4): 406–425. doi : 10.1093/oxfordjournals.molbev.a040454 . PMID  3447015.
2. Ксавье Дидело (2010). «Анализ структур бактериальной популяции на основе последовательностей». В D. Ashley Robinson; Daniel Falush; Edward J. Feil (ред.). Генетика бактериальной популяции при инфекционных заболеваниях . John Wiley and Sons. стр. 46–47. ISBN 978-0-470-42474-2.
3. Studier, JA; Keppler, KJ (ноябрь 1988 г.). «Заметка об алгоритме присоединения соседей Сайто и Нея». Молекулярная биология и эволюция . 5 (6): 729–31. doi : 10.1093/oxfordjournals.molbev.a040527 . ISSN  1537-1719. PMID  3221794.
4. Mailund, Thomas; Brodal, GerthS; Fagerberg, Rolf; Pedersen, ChristianNS; Phillips, Derek (2006). «Переделка метода присоединения соседей». BMC Bioinformatics . 7 (1): 29. doi : 10.1186/1471-2105-7-29 . PMC 3271233. PMID  16423304 . 
5. Gascuel O, Steel M (2006). «Раскрыто присоединение соседей». Mol Biol Evol . 23 (11): 1997–2000. doi : 10.1093/molbev/msl072 . PMID  16877499.
6. Kuhner, MK; Felsenstein, J. (1994-05-01). "Сравнение моделирования алгоритмов филогении при равных и неравных скоростях эволюции". Молекулярная биология и эволюция . 11 (3): 459–468. doi : 10.1093/oxfordjournals.molbev.a040126 . ISSN  0737-4038. PMID  8015439.
7. Atteson K (1997). «Производительность алгоритмов объединения соседей при реконструкции филогении», стр. 101–110. В Jiang, T., и Lee, D., ред., Lecture Notes in Computer Science, 1276 , Springer-Verlag, Берлин. COCOON '97.
8. Михаеску Р., Леви Д., Пачтер Л. (2009). «Почему работает метод присоединения соседей». Algorithmica . 54 (1): 1–24. arXiv : cs/0602041 . doi :10.1007/s00453-007-9116-4. S2CID  2462145.{{cite journal}}: CS1 maint: multiple names: authors list (link)
9. "RapidNJ". birc.au.dk .
10. "NINJA: инструмент для крупномасштабного вывода филогении методом присоединения соседей - Главная". wheelerlab.org .
11. "ATGC: BioNJ". www.atgc-montpellier.fr .
12. "WEIGHBOR Homepage". 5 марта 2015 г. Архивировано из оригинала 2015-03-05.
13. Крискуоло, Алексис; Гаскуэль, Оливье (декабрь 2008 г.). «Быстрые алгоритмы типа NJ для работы с неполными матрицами расстояний». BMC Bioinformatics . 9 (1): 166. doi : 10.1186/1471-2105-9-166 . PMC 2335114 . PMID  18366787. 
14. Симонсен, Мартин; Майлунд, Томас; Педерсен, Кристиан NS (2008). "Быстрое присоединение соседей" (PDF) . Алгоритмы в биоинформатике . Конспект лекций по информатике. Том 5251. С. 113–122. doi :10.1007/978-3-540-87361-7_10. ISBN 978-3-540-87360-0.
15. "ATGC: FastME" . www.atgc-montpellier.fr .
16. "FastTree 2.1: Деревья приблизительно максимального правдоподобия для больших выравниваний". www.microbesonline.org .

Другие источники

• Studier JA, Keppler KJ (1988). "Заметка об алгоритме присоединения соседей Сайто и Нея". Mol Biol Evol . 5 (6): 729–731. doi : 10.1093/oxfordjournals.molbev.a040527 . PMID  3221794.
• Мартин Симонсен; Томас Майлунд; Кристиан НС Педерсен (2008). "Быстрое присоединение соседей". Алгоритмы в биоинформатике . Конспект лекций по информатике. Том 5251. С. 113–122. CiteSeerX  10.1.1.218.2078 . doi :10.1007/978-3-540-87361-7_10. ISBN 978-3-540-87360-0.

Внешние ссылки

• Метод присоединения соседей — учебное пособие