Войти
Перестановка дерева используется в эвристике алгоритмы, предназначенные для поиска оптимальной древовидной структуры. Они могут применяться к любому набору данных, которые естественным образом организованы в дерево, но имеют большинство приложений в вычислительная филогенетика, особенно в поисках максимальной экономичности и максимальной вероятности филогенетических деревьев, которые стремятся идентифицировать одно из множества возможных деревьев, которое лучше всего объясняет эволюционная история конкретного гена или виды.
Обмен ближайшего соседа (NNI)
Отсечение и повторная прививка поддерева (SPR)
Деление дерева пополам и повторное соединение (TBR)
Простейшая перегруппировка дерева, известная как обмен ближайшего соседа, меняет возможность подключения четырех поддеревьев в основном дереве. Поскольку существует три возможных способа соединения четырех поддеревьев, и один из них - исходное соединение, каждый обмен создает два новых дерева. Исчерпывающий поиск возможных ближайших соседей для каждого возможного набора поддеревьев - самый медленный, но наиболее оптимизирующий способ выполнения этого поиска. Альтернативный, более широкий поиск, обрезка и пересадка поддерева (SPR), выбирает и удаляет поддерево из основного дерева и повторно вставляет его в другое место в основном дереве для создания нового узла. Наконец, разделение дерева пополам и повторное соединение (TBR) отделяет поддерево от главного дерева во внутреннем узле, а затем пытается все возможные соединения между ребрами двух созданных таким образом деревьев. Возрастающая сложность метода перестройки дерева коррелирует с увеличением вычислительного времени, необходимого для поиска, хотя не обязательно с их производительностью.
SPR можно далее разделить на uSPR: некорневой SPR, rSPR: корневой SPR. uSPR применяется к некорневым деревьям и выглядит так: сломайте любой край. Присоедините один конец ребра (выбранный произвольно) к любому другому ребру в дереве. rSPR применяется к корневым деревьям * и идет: ломает любое ребро, кроме ребра, ведущего к корневому узлу. Присоединитесь к одному концу ребра (а именно: к самому дальнему от корня концу ребра) и прикрепите его к любому другому ребру дерева.
* В этом примере корень дерева отмечен узел первой степени, что означает, что все узлы в дереве имеют степень 1 или степень 3. Альтернативный подход, используемый в Bordewich и Semple, состоит в том, чтобы рассматривать корневой узел как имеющий степень 2 и иметь специальное правило для rSPR.
Количество перемещений SPR или TBR, необходимых для перехода от одного дерева к другому, может быть рассчитано путем создания леса максимального согласования, включающего (соответственно) корневые или неукорененные деревья. Эта проблема является сложной NP, но с фиксированными параметрами.
Простейший тип слияния деревьев начинается с двух деревьев, которые уже определены как почти оптимальные; таким образом, они, скорее всего, имеют правильное большинство своих узлов, но могут не правильно разрешить отдельные «листья» дерева; например, разделение ((A, B), (C, D)) на конце ответвления по сравнению с ((A, C), (B, D)) может быть неразрешенным. Слияние деревьев меняет местами эти два решения между двумя деревьями, которые в остальном почти оптимальны. В вариантах метода используются стандартные генетические алгоритмы с определенной целевой функцией для замены поддеревьев с высокими показателями в основные деревья, которые в целом имеют наибольший результат.
Альтернативная стратегия состоит в том, чтобы отделить часть дерева (которую можно выбрать случайным образом или с использованием более стратегического подхода) и выполнить TBR / SPR / NNI для этого поддерева. Это оптимизированное поддерево затем можно заменить в основном дереве, что, как мы надеемся, улучшит p-оценку.
Чтобы избежать попадания в локальные оптимумы, можно применить подход «имитационного отжига». используется, при этом алгоритму иногда разрешается использовать неоптимальные деревья кандидатов с вероятностью, связанной с тем, насколько они далеки от оптимума.
Один раз диапазон одинаково оптимальных деревья были собраны, часто можно найти лучшее дерево, объединив «хорошие части» отдельных деревьев. Подгруппы с идентичным составом, но разной топологией могут быть переключены и полученные деревья оцениваются.
