WikiDer > Присоединение к соседу

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. На основе текущей матрицы расстояний вычисляем матрицу (определено ниже).
  2. Найдите пару различных таксонов i и j (т.е. с ) для которого имеет самое низкое значение. Эти таксоны присоединяются к вновь созданному узлу, который соединен с центральным узлом. На рисунке справа f и g присоединены к новому узлу u.
  3. Рассчитайте расстояние от каждого из таксоны в паре с этим новым узлом.
  4. Рассчитайте расстояние от каждого таксона за пределами этой пары до нового узла.
  5. Запустите алгоритм снова, заменив пару объединенных соседей новым узлом и используя расстояния, вычисленные на предыдущем шаге.

Q-матрица

На основе матрицы расстояний, связывающей таксоны, вычислить следующее:

 

 

 

 

(1)

куда расстояние между таксонами и .

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

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

 

 

 

 

(2)

и:

Таксоны и парные таксоны и - вновь созданный узел. Соединение ветвей и и и , и их длина, и являются частью дерева, которое постепенно создается; они не влияют и не влияют на последующие шаги присоединения соседей.

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

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

 

 

 

 

(3)

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

Сложность

Сосед присоединяется к набору таксоны требует итераций. На каждом этапе нужно строить и искать матрица. Первоначально матрица размер , то следующим шагом будет и т. д. Прямая реализация этого приводит к алгоритму с временной сложностью ;[3] Существуют реализации, которые используют эвристику, чтобы добиться в среднем гораздо лучших результатов.[4]

Пример

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

Допустим, у нас пять таксонов и следующая матрица расстояний :

абcdе
а05998
б5010109
c910087
d910803
е89730

Первый шаг

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

Мы рассчитываем значения по уравнению (1). Например:

Получаем следующие значения для матрица (диагональные элементы матрицы здесь не используются и опускаются):

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

В приведенном выше примере . Это наименьшее значение , поэтому мы соединяем элементы и .

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

Позволять обозначают новый узел. По уравнению (2), вверху ветви, соединяющиеся и к тогда имейте длины:

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

Затем мы приступаем к обновлению исходной матрицы расстояний в новую матрицу расстояний (см. ниже), уменьшенного в размере на одну строку и один столбец из-за объединения с в своего соседа . Используя уравнение (3) выше, мы вычисляем расстояние от к каждому из других узлов, кроме и . В этом случае получаем:

Результирующая матрица расстояний является:

тыcdе
ты0776
c7087
d7803
е6730

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

Второй шаг

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

Соответствующие матрица:

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

Мы можем выбрать присоединиться и , или присоединиться и ; обе пары имеют минимальный значение , и любой выбор приводит к одному и тому же результату. Для конкретности присоединимся и и вызовите новый узел .

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

Длины стыковки ветвей и к можно рассчитать:

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

Обновление матрицы второго расстояния

Обновленная матрица расстояний для остальных 3 узлов, , , и , теперь вычисляется:

vdе
v043
d403
е330

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

На этом этапе топология дерева полностью решена. Однако для наглядности мы можем рассчитать матрица. Например:

vdе
v−10−10
d−10−10
е−10−10

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

Дерево присоединения соседей завершено, как показано на рисунке.

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

Этот пример представляет собой идеализированный случай: обратите внимание, что если мы перейдем от одного таксона к любому другому по ветвям дерева и просуммируем длины пройденных ветвей, результат будет равен расстоянию между этими таксонами во входной матрице расстояний. Например, переход от к у нас есть . Матрица расстояний, расстояния которой совпадают таким образом с некоторым деревом, называется «аддитивной», что редко встречается на практике. Тем не менее, важно отметить, что, учитывая аддитивную матрицу расстояний в качестве входных данных, соединение соседей гарантированно найдет дерево, расстояния между таксонами которого согласуются с ним.

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

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

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

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

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

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

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

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

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

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

  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.CS1 maint: несколько имен: список авторов (связь)

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

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