Перестановка дерева

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

Основные перестановки деревьев

Ближайшая соседняя развязка (NNI)
Обрезка и перепрививка поддеревьев (SPR)
Разделение дерева пополам и пересоединение (TBR)

Простейшая перестановка дерева, известная как обмен ближайшими соседями , меняет связность четырех поддеревьев внутри основного дерева. Поскольку существует три возможных способа соединения четырех поддеревьев, ^[1] и один из них — исходная связность, каждый обмен создает два новых дерева. Полный поиск возможных ближайших соседей для каждого возможного набора поддеревьев — самый медленный, но наиболее оптимизирующий способ выполнения этого поиска. Альтернативный, более широкий поиск, обрезка и пересадка поддерева (SPR), выбирает и удаляет поддерево из основного дерева и повторно вставляет его в другое место основного дерева для создания нового узла. Наконец, разделение дерева пополам и повторное соединение (TBR) отделяет поддерево от основного дерева во внутреннем узле, а затем пытается использовать все возможные соединения между ребрами двух созданных таким образом деревьев. Возрастающая сложность метода перестановки дерева коррелирует с увеличением вычислительного времени, необходимого для поиска, хотя и не обязательно с их производительностью. ^[2]

SPR можно разделить на uSPR: некорневой SPR, rSPR: корневой SPR. uSPR применяется к деревьям без корней и действует следующим образом: сломайте любой край. Присоедините один конец ребра (выбранного произвольно) к любому другому ребру в дереве. rSPR применяется к корневым деревьям* и заключается в следующем: сломать любое ребро, кроме ребра, ведущего к корневому узлу. Соедините один конец ребра (точнее: конец ребра, находящийся САМЫМ ДАЛЕЕ от корня) и прикрепите его к любому другому краю дерева. ^[3]

* В этом примере корень дерева отмечен узлом первой степени, что означает, что все узлы в дереве имеют степень 1 или степень 3. Альтернативный подход, используемый в Бордевиче и Семпле, состоит в том, чтобы рассматривать корневой узел как иметь степень 2 и иметь специальное правило для rSPR.

Количество СПР ^[4] или ТБР ^[5] Ходы, необходимые для перехода от одного дерева к другому, можно рассчитать, создав лес максимального согласия, включающий (соответственно) укорененные или неукорененные деревья. Эта проблема NP сложна, но решаема с фиксированным параметром.

Слияние деревьев

Самый простой тип слияния деревьев начинается с двух деревьев, которые уже определены как почти оптимальные; таким образом, они, скорее всего, имеют правильное большинство своих узлов, но могут не суметь правильно разрешить отдельные «листья» дерева; например, разделение ((A,B),(C,D)) на кончике ветки по сравнению с ((A,C),(B,D)) может быть неразрешенным. ^[1] Слияние деревьев меняет местами эти два решения между двумя в остальном почти оптимальными деревьями. Варианты метода используют стандартные генетические алгоритмы с определенной целевой функцией для замены поддеревьев с высокими показателями на основные деревья, которые в целом имеют высокие показатели. ^[6]

Секторальный поиск

Альтернативная стратегия — отделить часть дерева (которую можно выбрать случайным образом или использовать более стратегический подход) и выполнить TBR/SPR/NNI на этом поддереве. Это оптимизированное поддерево затем можно заменить в главном дереве, что, как мы надеемся, улучшит показатель p. ^[7]

Дерево дрейфует

Чтобы избежать попадания в локальные оптимумы, можно использовать подход «имитированного отжига», при котором алгоритму иногда разрешается использовать неоптимальные деревья-кандидаты с вероятностью, связанной с тем, насколько они далеки от оптимума. ^[7]

Слияние деревьев

После того, как собран ряд одинаково оптимальных деревьев, часто можно найти лучшее дерево, объединив «хорошие части» отдельных деревьев. Подгруппы с одинаковым составом, но разной топологией можно переключать и оценивать полученные деревья. ^[7]

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Фельзенштейн, Джозеф (2004). Выводы о филогениях . Sinauer Associates: Сандерленд, Массачусетс. ISBN 9780878931774 .
^ Такахаши, Кей; Ней, Масатоши (август 2000 г.). «Эффективность быстрых алгоритмов филогенетического вывода по критериям максимальной экономии, минимальной эволюции и максимального правдоподобия при использовании большого количества последовательностей» . Молекулярная биология и эволюция . 17 (8): 1251–1258. doi : 10.1093/oxfordjournals.molbev.a026408 . ПМИД 10908645 .
^ Бордевич, Магнус; Семпл, Чарльз (2005). «О вычислительной сложности корневого поддерева при обрезке и перепрививке расстояния» . Анналы комбинаторики . 8 (4): 409–423. дои : 10.1007/s00026-004-0229-z . S2CID 13002129 .
^ Уидден, Крис; Бейко, Роберт Г.; Зех, Норберт (2016). «Алгоритмы с фиксированными параметрами и аппроксимации для лесов максимального согласия разветвленных деревьев». Алгоритмика . 74 (3): 1019–1054. arXiv : 1305.0512 . дои : 10.1007/s00453-015-9983-z . S2CID 14297537 .
^ Чен, Цзянер; Фань, Цзя-Хао; Сзе, Синг-Хой (2015). «Алгоритмы параметризации и аппроксимации леса максимального согласия в разветвленных деревьях» . Теоретическая информатика . 562 : 496–512. дои : 10.1016/j.tcs.2014.10.031 .
^ Мацуда, Х. (1996). «Филогенетический вывод белка с использованием максимального правдоподобия с помощью генетического алгоритма» (PDF) . Тихоокеанский симпозиум по биокомпьютингу, 1996 г. стр. 512–523.
^ Jump up to: Перейти обратно: ^а ^б ^с Голобов, Пабло А. (1999). «Анализ больших наборов данных в разумные сроки: решения для составной оптимизации» . Кладистика . 15 (4): 415–428. дои : 10.1006/клад.1999.0122 . ПМИД 34902941 .

[felsenstein-1] Jump up to: Перейти обратно: ^а ^б Фельзенштейн, Джозеф (2004). Выводы о филогениях . Sinauer Associates: Сандерленд, Массачусетс. ISBN 9780878931774 .

[takahashi-2] Такахаши, Кей; Ней, Масатоши (август 2000 г.). «Эффективность быстрых алгоритмов филогенетического вывода по критериям максимальной экономии, минимальной эволюции и максимального правдоподобия при использовании большого количества последовательностей» . Молекулярная биология и эволюция . 17 (8): 1251–1258. doi : 10.1093/oxfordjournals.molbev.a026408 . ПМИД 10908645 .

[bs05-3] Бордевич, Магнус; Семпл, Чарльз (2005). «О вычислительной сложности корневого поддерева при обрезке и перепрививке расстояния» . Анналы комбинаторики . 8 (4): 409–423. дои : 10.1007/s00026-004-0229-z . S2CID 13002129 .

[4] Уидден, Крис; Бейко, Роберт Г.; Зех, Норберт (2016). «Алгоритмы с фиксированными параметрами и аппроксимации для лесов максимального согласия разветвленных деревьев». Алгоритмика . 74 (3): 1019–1054. arXiv : 1305.0512 . дои : 10.1007/s00453-015-9983-z . S2CID 14297537 .

[5] Чен, Цзянер; Фань, Цзя-Хао; Сзе, Синг-Хой (2015). «Алгоритмы параметризации и аппроксимации леса максимального согласия в разветвленных деревьях» . Теоретическая информатика . 562 : 496–512. дои : 10.1016/j.tcs.2014.10.031 .

[matsuda-6] Мацуда, Х. (1996). «Филогенетический вывод белка с использованием максимального правдоподобия с помощью генетического алгоритма» (PDF) . Тихоокеанский симпозиум по биокомпьютингу, 1996 г. стр. 512–523.

[Goloboff1999-7] Jump up to: Перейти обратно: ^а ^б ^с Голобов, Пабло А. (1999). «Анализ больших наборов данных в разумные сроки: решения для составной оптимизации» . Кладистика . 15 (4): 415–428. дои : 10.1006/клад.1999.0122 . ПМИД 34902941 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]