Присоединение к соседу - Neighbor joining

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

Алгоритм

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

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

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

Q-матрица

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

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

(1)

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

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

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

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

и:

${\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 d(u,k)={\frac {1}{2}}[d(f,k)+d(g,k)-d(f,g)]}$

(3)

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

Сложность

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

Пример

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

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

	а	б	c	d	е
а	0	5	9	9	8
б	5	0	10	10	9
c	9	10	0	8	7
d	9	10	8	0	3
е	8	9	7	3	0

Первый шаг

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

Мы рассчитываем ${\displaystyle Q_{1}}$ значения по уравнению (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}}$ матрица (диагональные элементы матрицы здесь не используются и опускаются):

	а	б	c	d	е
а		−50	−38	−34	−34
б	−50		−38	−34	−34
c	−38	−38		−40	−40
d	−34	−34	−40		−48
е	−34	−34	−40	−48

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

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

Позволять ${\displaystyle u}$ обозначают новый узел. По уравнению (2), вверху ветви, соединяющиеся ${\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}$

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

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

	ты	c	d	е
ты	0	7	7	6
c	7	0	8	7
d	7	8	0	3
е	6	7	3	0

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

Второй шаг

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

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

	ты	c	d	е
ты		−28	−24	−24
c	−28		−24	−24
d	−24	−24		−28
е	−24	−24	−28

Мы можем выбрать присоединиться ${\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}}$ для остальных 3 узлов, ${\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}$

	v	d	е
v	0	4	3
d	4	0	3
е	3	3	0

Заключительный этап

На этом этапе топология дерева полностью решена. Однако для наглядности мы можем рассчитать ${\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}$

	v	d	е
v		−10	−10
d	−10		−10
е	−10	−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}$. Матрица расстояний, расстояния которой совпадают таким образом с некоторым деревом, называется «аддитивной», что редко встречается на практике. Тем не менее, важно отметить, что, учитывая аддитивную матрицу расстояний в качестве входных данных, соединение соседей гарантированно найдет дерево, расстояния между таксонами которого согласуются с ним.

Соседство как минимальная эволюция

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

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

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

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

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

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

Доступно множество программ, реализующих соединение соседей. RapidNJ иНИНДЗЯ являются быстрыми реализациями с типичным временем выполнения, приблизительно пропорциональным квадрату количества таксонов.BIONJ и Вес представляют собой варианты объединения соседей, которые повышают его точность за счет использования того факта, что более короткие расстояния в матрице расстояний обычно лучше известны, чем более длинные расстояния. FastME является реализацией тесно связанного метода сбалансированной минимальной эволюции.

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

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

Рекомендации

1. Saitou, N .; Ней, М. (1 июля 1987 г.). «Метод объединения соседей: новый метод реконструкции филогенетических деревьев». Молекулярная биология и эволюция. 4 (4): 406–425. Дои:10.1093 / oxfordjournals.molbev.a040454. PMID  3447015.
2. Ксавье Дидло (2010). «Последовательный анализ структур бактериальных популяций». В Д. Эшли Робинсон; Даниэль Фалуш; Эдвард Дж. Фейл (ред.). Бактериальная популяционная генетика при инфекционных заболеваниях. Джон Уайли и сыновья. С. 46–47. ISBN  978-0-470-42474-2.
3. Studier, J. A .; Кепплер, К. Дж. (Ноябрь 1988 г.). «Заметка об алгоритме объединения соседей Сайто и Нэя». Молекулярная биология и эволюция. 5 (6): 729–31. Дои:10.1093 / oxfordjournals.molbev.a040527. ISSN  1537-1719. PMID  3221794.
4. Майлунд, Томас; Brodal, GerthS; Фагерберг, Рольф; Педерсен, ChristianNS; Филлипс, Дерек (2006). «Переработка метода объединения соседей». BMC Bioinformatics. 7 (1): 29. Дои:10.1186/1471-2105-7-29. ЧВК  3271233. PMID  16423304.
5. Гаскуэль О, Сталь М (2006). "Соседство обнаружено". Мол Биол Эвол. 23 (11): 1997–2000. Дои:10.1093 / molbev / msl072. PMID  16877499.
6. Kuhner, M. K .; Фельзенштейн, Дж. (1994-05-01). «Моделирование сравнения алгоритмов филогении при равных и неравных темпах эволюции». Молекулярная биология и эволюция. 11 (3): 459–468. Дои:10.1093 / oxfordjournals.molbev.a040126. ISSN  0737-4038. PMID  8015439.
7. Аттесон К. (1997). «Производительность алгоритмов объединения соседей при реконструкции филогении», стр. 101–110. В Цзян, Т., и Ли, Д., ред., Конспект лекций по информатике, 1276 г., Springer-Verlag, Берлин. КОКОН '97.
8. Михаеску Р., Леви Д., Пахтер Л (2009). «Почему работает соседство». Алгоритмика. 54 (1): 1–24. arXiv:cs / 0602041. Дои:10.1007 / s00453-007-9116-4. S2CID  2462145.

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

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

внешняя ссылка

• Метод объединения соседей - учебник