В биоинформатики , сосед присоединения снизу вверх (агломерационного) кластеризация метод для создания филогенетических деревьев , созданного Naruya Saitou и Masatoshi Nei в 1987 году [1] Обычно используется для деревьев , основанных на ДНК или белковых последовательностей данных, алгоритм требует знание расстояния между каждой парой таксонов (например, видами или последовательностями) для формирования дерева. [2]
Алгоритм
Соединение соседей принимает в качестве входных данных матрицу расстояний, определяющую расстояние между каждой парой таксонов. Алгоритм начинается с полностью неразрешенного дерева, топология которого соответствует топологии звездообразной сети , и повторяется по следующим шагам, пока дерево не будет полностью разрешено и все длины ветвей не будут известны:
- На основе текущей матрицы расстояний вычисляем матрицу (определено ниже).
- Найдите пару различных таксонов i и j (т. Е. С ) для которого имеет самое низкое значение. Эти таксоны присоединяются к вновь созданному узлу, который связан с центральным узлом. На рисунке справа f и g присоединены к новому узлу u.
- Рассчитайте расстояние от каждого таксона в паре до этого нового узла.
- Рассчитайте расстояние от каждого таксона за пределами этой пары до нового узла.
- Запустите алгоритм снова, заменив пару объединенных соседей новым узлом и используя расстояния, вычисленные на предыдущем шаге.
Q-матрица
На основе матрицы расстояний, связывающей таксоны, вычислить следующим образом:
( 1 )
где расстояние между таксонами а также .
Расстояние от членов пары до нового узла
Для каждого таксона в соединяемой паре используйте следующую формулу, чтобы вычислить расстояние до нового узла:
( 2 )
а также:
Таксоны а также парные таксоны и это вновь созданный узел. Соединение ветвей а также а также а также , и их длина, а также являются частью дерева, которое постепенно создается; они не влияют и не затрагиваются последующими этапами присоединения соседей.
Расстояние других таксонов от нового узла
Для каждого таксона, не рассмотренного на предыдущем шаге, мы вычисляем расстояние до нового узла следующим образом:
( 3 )
где это новый узел, это узел, расстояние до которого мы хотим вычислить, и а также члены пары только что присоединились.
Сложность
Сосед присоединяется к набору таксоны требует итераций. На каждом этапе нужно строить и искатьматрица. Первоначально матрица размер , то следующим шагом будет и т.д. Прямая реализация этого приводит к алгоритму с временной сложностью ; [3] существуют реализации, которые в среднем используют эвристику гораздо лучше, чем эта. [4]
Пример
Допустим, у нас есть пять таксонов и следующая матрица расстояний :
а | б | 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 |
Первый шаг
Первое присоединение
Рассчитываем значения по уравнению ( 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 |
В приведенном выше примере . Это наименьшее значение, поэтому мы соединяем элементы а также .
Оценка длины первой ветви
Позволять обозначают новый узел. По уравнению ( 2 ), приведенному выше, ветви, соединяющие а также к тогда имейте длины:
Первое обновление матрицы расстояний
Затем мы приступаем к обновлению исходной матрицы расстояний. в новую матрицу расстояний (см. ниже), уменьшенного в размере на одну строку и один столбец из-за объединения с участием в своего соседа . Используя уравнение ( 3 ) выше, мы вычисляем расстояние от к каждому из других узлов, кроме а также . В этом случае получаем:
Результирующая матрица расстояний является:
ты | c | d | е | |
---|---|---|---|---|
ты | 0 | 7 | 7 | 6 |
c | 7 | 0 | 8 | 7 |
d | 7 | 8 | 0 | 3 |
е | 6 | 7 | 3 | 0 |
Значения, выделенные жирным шрифтом соответствуют вновь рассчитанным расстояниям, тогда как значения, выделенные курсивом, не затрагиваются обновлением матрицы, поскольку они соответствуют расстояниям между элементами, не участвующими в первом соединении таксонов.
Второй шаг
Второе присоединение
Соответствующие матрица:
ты | c | d | е | |
---|---|---|---|---|
ты | −28 | −24 | −24 | |
c | −28 | −24 | −24 | |
d | −24 | −24 | −28 | |
е | −24 | −24 | −28 |
Мы можем выбрать присоединиться а также , или присоединиться а также ; обе пары имеют минимальный значение , и любой выбор приводит к одному и тому же результату. Для конкретности присоединяемся а также и назовите новый узел .
Оценка длины второй ветви
Длина стыковки ветвей а также к можно рассчитать:
Соединение элементов и расчет длины ответвления помогают нарисовать дерево соединения соседей, как показано на рисунке .
Обновление второй матрицы расстояний
Обновленная матрица расстояний для остальных 3 узлов, , , а также , теперь вычисляется:
v | d | е | |
---|---|---|---|
v | 0 | 4 | 3 |
d | 4 | 0 | 3 |
е | 3 | 3 | 0 |
Заключительный этап
На этом этапе топология дерева полностью решена. Однако для наглядности мы можем рассчитатьматрица. Например:
v | d | е | |
---|---|---|---|
v | −10 | −10 | |
d | −10 | −10 | |
е | −10 | −10 |
Для конкретности присоединяемся а также и вызовем последний узел . Длину трех оставшихся ветвей можно рассчитать:
Теперь дерево присоединения соседей завершено, как показано на рисунке .
Вывод: аддитивные расстояния
Этот пример представляет собой идеализированный случай: обратите внимание, что если мы перейдем от любого таксона к любому другому по ветвям дерева и просуммируем длины пройденных ветвей, результат будет равен расстоянию между этими таксонами во входной матрице расстояний. Например, переход от к у нас есть . Матрица расстояний, расстояния которой совпадают таким образом с некоторым деревом, называется «аддитивной», что редко встречается на практике. Тем не менее, важно отметить, что, учитывая аддитивную матрицу расстояний в качестве входных данных, соединение соседей гарантированно найдет дерево, расстояния между таксонами которого согласуются с ним.
Соседство как минимальная эволюция
Объединение соседей можно рассматривать как жадную эвристику для критерия сбалансированного минимального развития [5] (BME). Для каждой топологии BME определяет длину дерева (сумму длин ветвей) как конкретную взвешенную сумму расстояний в матрице расстояний, причем веса зависят от топологии. Оптимальная топология BME - это та, которая минимизирует длину этого дерева. Присоединение соседей на каждом шаге жадно присоединяется к той паре таксонов, которая дает наибольшее уменьшение предполагаемой длины дерева. Эта процедура не гарантирует нахождения оптимума по критерию BME, хотя часто дает и обычно довольно близка.
Преимущества и недостатки
Главное достоинство NJ в том, что он быстр [6] : 466 по сравнению с методами наименьших квадратов , максимальной экономии и максимального правдоподобия . [6] Это делает его практичным для анализа больших наборов данных (сотни или тысячи таксонов) и для самонастройки , для чего другие средства анализа (например, максимальная экономия , максимальная вероятность ) могут быть недоступны с вычислительной точки зрения .
Соединение соседей имеет свойство, заключающееся в том, что если входная матрица расстояний верна, то и выходное дерево будет правильным. Более того, правильность топологии выходного дерева гарантируется, пока матрица расстояний является «почти аддитивной», в частности, если каждая запись в матрице расстояний отличается от истинного расстояния менее чем на половину самой короткой длины ветви в дереве. [7] На практике матрица расстояний редко удовлетворяет этому условию, но соединение соседей часто в любом случае создает правильную топологию дерева. [8] Правильность объединения соседей для почти аддитивных матриц расстояний подразумевает, что оно статистически согласовано во многих моделях эволюции; учитывая данные достаточной длины, соединение соседей с большой вероятностью восстановит истинное дерево. По сравнению с UPGMA и WPGMA , сосед объединение имеет то преимущество , что она не принимает на себя все родословные развиваться с той же скоростью ( гипотеза молекулярных часов ).
Тем не менее, соединение соседей было в значительной степени вытеснено филогенетическими методами, которые не полагаются на измерения расстояния и обеспечивают превосходную точность в большинстве условий. [ необходима цитата ] Соединение соседей имеет нежелательную особенность, заключающуюся в том, что оно часто присваивает отрицательную длину некоторым ветвям.
Реализации и варианты
Доступно множество программ, реализующих объединение соседей. RapidNJ и NINJA - это быстрые реализации с типичным временем выполнения, пропорциональным приблизительно квадрату количества таксонов. BIONJ и Weighbor - это варианты объединения соседей, которые повышают его точность за счет использования того факта, что более короткие расстояния в матрице расстояний обычно лучше известны, чем более длинные расстояния. FastME - это реализация тесно связанного метода сбалансированной минимальной эволюции.
Смотрите также
Рекомендации
- ^ Saitou, N .; Ней, М. (1 июля 1987 г.). «Метод объединения соседей: новый метод реконструкции филогенетических деревьев» . Молекулярная биология и эволюция . 4 (4): 406–425. DOI : 10.1093 / oxfordjournals.molbev.a040454 . PMID 3447015 .
- ^ Ксавье Дидло (2010). «Последовательный анализ бактериальных популяционных структур» . В Д. Эшли Робинсон; Даниэль Фалуш; Эдвард Дж. Фейл (ред.). Бактериальная популяционная генетика при инфекционных заболеваниях . Джон Уайли и сыновья. С. 46–47. ISBN 978-0-470-42474-2.
- ^ Studier, JA; Кепплер, KJ (ноябрь 1988 г.). «Замечание об алгоритме объединения соседей Сайто и Нэя» . Молекулярная биология и эволюция . 5 (6): 729–31. DOI : 10.1093 / oxfordjournals.molbev.a040527 . ISSN 1537-1719 . PMID 3221794 .
- ^ Майлунд, Томас; Brodal, GerthS; Фагерберг, Рольф; Педерсен, ChristianNS; Филлипс, Дерек (2006). «Переработка метода объединения соседей» . BMC Bioinformatics . 7 (1): 29. DOI : 10,1186 / 1471-2105-7-29 . PMC 3271233 . PMID 16423304 .
- ^ Гаскуэл О., Сталь М (2006). «Соседство выявлено» . Mol Biol Evol . 23 (11): 1997–2000. DOI : 10.1093 / molbev / msl072 . PMID 16877499 .
- ^ а б Kuhner, MK; Фельзенштейн, Дж. (1994-05-01). «Моделирование сравнения алгоритмов филогении при равных и неравных темпах эволюции» . Молекулярная биология и эволюция . 11 (3): 459–468. DOI : 10.1093 / oxfordjournals.molbev.a040126 . ISSN 0737-4038 . PMID 8015439 .
- ^ Atteson K (1997). «Производительность алгоритмов объединения соседей при реконструкции филогении», стр. 101–110. В Jiang, T. и Lee, D., eds., Lecture Notes in Computer Science, 1276 , Springer-Verlag, Berlin. КОКОН '97.
- ^ Михаеску Р., Леви Д., Пахтер Л. (2009). «Почему работает соседство». Алгоритмика . 54 (1): 1–24. arXiv : cs / 0602041 . DOI : 10.1007 / s00453-007-9116-4 . S2CID 2462145 .CS1 maint: несколько имен: список авторов ( ссылка )
Другие источники
- Studier JA, Keppler KJ (1988). «Заметка об алгоритме объединения соседей Сайто и Нэя» . Mol Biol Evol . 5 (6): 729–731. DOI : 10.1093 / oxfordjournals.molbev.a040527 . PMID 3221794 .
- Мартин Симонсен; Томас Майлунд; Кристиан Н.С. Педерсен (2008). Быстрое присоединение соседей (PDF) . Труды WABI . Конспект лекций по информатике. 5251 . С. 113–122. CiteSeerX 10.1.1.218.2078 . DOI : 10.1007 / 978-3-540-87361-7_10 . ISBN 978-3-540-87360-0.[ постоянная мертвая ссылка ]
Внешние ссылки
- Метод объединения соседей - учебное пособие