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

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

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

Простейшая перестановка дерева, известная как обмен ближайшими соседями (NNI, англ. nearest-neighbor interchange]]), меняет связность четырёх поддеревьев в основном дереве. Поскольку существует три возможных способа соединения четырёх поддеревьев^[1] и один из них является исходным соединением, каждый обмен создает два новых дерева. Исчерпывающий поиск возможных ближайших соседей для каждого возможного набора поддеревьев является самым медленным, но наиболее оптимальным способом выполнения этого поиска.

Альтернативный, более широкий поиск — обрезка и пересадка поддерева (SPR, англ. subtree pruning and regrafting) — выбирает и удаляет поддерево из основного дерева, а затем повторно вставляет его в другое место основного дерева для создания нового узла. SPR-алгоритмы можно дополнительно разделить на uSPR (SPR без укоренения), rSPR (SPR с укоренением). uSPR применяется к неукоренённым деревьям и работает следующим образом: ломается одно из рёбер (выбранное произвольно), а затем конец этого ребра соединяется с любым другим ребром в дереве. rSPR применяется к укорененным деревьям и заключается в следующем: ломается одно из рёбер (выбранное произвольно, за исключением ребра, ведущего к корневому узлу), а затем один конец этого ребра (в частности: конец ребра, который НАИБОЛЕЕ ДАЛЕКО от корня) присоединяется к любому другому краю дерева^[2].

Бисекция и повторное соединение дерева (TBR, англ. tree bisection and reconnection) отделяет поддерево от основного дерева во внутреннем узле, а затем пытается установить все возможные соединения между ребрами двух созданных таким образом деревьев. Возрастающая сложность метода перестановки дерева коррелирует с увеличением времени вычислений, требуемого для поиска, хотя и не обязательно с их производительностью^[3].

Количество перемещений SPR^[4] или TBR^[5], необходимых для перехода от одного дерева к другому, можно рассчитать, создав максимально согласованный лес (англ. agreement forest), включающий (соответственно) укоренённые или неукоренённые деревья. Эта проблема является NP-полной, но решается с фиксированным параметром.

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

Примечания

1. David Penny. Inferring Phylogenies.—Joseph Felsenstein. 2003. Sinauer Associates, Sunderland, Massachusetts. (англ.) // Systematic Biology. — 2004-08-01. — Vol. 53, iss. 4. — P. 669–670. — ISSN 1063-5157 1076-836X, 1063-5157. — doi:10.1080/10635150490468530. Архивировано 3 октября 2022 года.
2. Magnus Bordewich, Charles Semple. On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance (англ.) // Annals of Combinatorics. — 2005-01. — Vol. 8, iss. 4. — P. 409–423. — ISSN 0219-3094 0218-0006, 0219-3094. — doi:10.1007/s00026-004-0229-z.
3. Kei Takahashi, Masatoshi Nei. Efficiencies of Fast Algorithms of Phylogenetic Inference Under the Criteria of Maximum Parsimony, Minimum Evolution, and Maximum Likelihood When a Large Number of Sequences Are Used (англ.) // Molecular Biology and Evolution. — 2000-08-01. — Vol. 17, iss. 8. — P. 1251–1258. — ISSN 0737-4038 1537-1719, 0737-4038. — doi:10.1093/oxfordjournals.molbev.a026408. Архивировано 7 октября 2022 года.
4. Chris Whidden, Robert G. Beiko, Norbert Zeh. Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests of Multifurcating Trees. — 2013. — doi:10.48550/ARXIV.1305.0512. Архивировано 3 октября 2022 года.
5. Jianer Chen, Jia-Hao Fan, Sing-Hoi Sze. Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees (англ.) // Theoretical Computer Science. — 2015-01. — Vol. 562. — P. 496–512. — doi:10.1016/j.tcs.2014.10.031. Архивировано 2 марта 2022 года.