Русская Википедия:Перестановка дерева
Перестановка дерева — детерминированный алгоритм для поиска оптимальной древовидной структуры. Перестановки деревьев могут быть применены к любому набору данных, которые естественным образом организованы в виде дерева, но в первую очередь применяются в вычислительной филогенетике. Особое место такие алгоритмы занимают в поиске филогенетических деревьев с использованием методов максимальной экономии и максимального правдоподобия, где основной задачей является нахождение одного дерева из многих возможных, которое лучше всего объясняет эволюционную историю конкретного гена или вида.
Базовые перестановки деревьев
Простейшая перестановка дерева, известная как обмен ближайшими соседями (NNI, Шаблон:Lang-en), меняет связность четырёх поддеревьев в основном дереве. Поскольку существует три возможных способа соединения четырёх поддеревьев[1] и один из них является исходным соединением, каждый обмен создает два новых дерева. Исчерпывающий поиск возможных ближайших соседей для каждого возможного набора поддеревьев является самым медленным, но наиболее оптимальным способом выполнения этого поиска.
Альтернативный, более широкий поиск — обрезка и пересадка поддерева (SPR, Шаблон:Lang-en) — выбирает и удаляет поддерево из основного дерева, а затем повторно вставляет его в другое место основного дерева для создания нового узла. SPR-алгоритмы можно дополнительно разделить на uSPR (SPR без укоренения), rSPR (SPR с укоренением). uSPR применяется к неукоренённым деревьям и работает следующим образом: ломается одно из рёбер (выбранное произвольно), а затем конец этого ребра соединяется с любым другим ребром в дереве. rSPR применяется к укорененным деревьям и заключается в следующем: ломается одно из рёбер (выбранное произвольно, за исключением ребра, ведущего к корневому узлу), а затем один конец этого ребра (в частности: конец ребра, который НАИБОЛЕЕ ДАЛЕКО от корня) присоединяется к любому другому краю дерева[2].
Бисекция и повторное соединение дерева (TBR, Шаблон:Lang-en) отделяет поддерево от основного дерева во внутреннем узле, а затем пытается установить все возможные соединения между ребрами двух созданных таким образом деревьев. Возрастающая сложность метода перестановки дерева коррелирует с увеличением времени вычислений, требуемого для поиска, хотя и не обязательно с их производительностью[3].
Количество перемещений SPR[4] или TBR[5], необходимых для перехода от одного дерева к другому, можно рассчитать, создав максимально Шаблон:Нп2, включающий (соответственно) укоренённые или неукоренённые деревья. Эта проблема является NP-полной, но решается с фиксированным параметром.
-
Обмен ближайшими соседями (NNI)
-
Обрезка и пересадка поддерева (SPR)
-
Бисекция и повторное соединение дерева (TBR)
Примечания
