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

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

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

Простейшая перестановка дерева, известная как обмен ближайшими соседями (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-полной, но решается с фиксированным параметром.