Поддерево максимального соответствия (для трех или более деревьев): различия между версиями

Актуальность задачи k-MAST связана с необходимостью сравнения эволюционных деревьев. Недавние достижения в разработке экспериментальных техник в молекулярной биологии дали много разных данных, которые могут быть использованы для построения эволюционных деревьев. Разнообразие данных в сочетании с разнообразием методов построения эволюционных деревьев нередко приводит к ситуации, когда эволюция одного и того же множества видов объясняется различными эволюционными деревьями. Задача нахождения поддерева максимального соответствия возникла как способ нахождения соответствия между подобными деревьями и как метод определения общего для таких деревьев поддерева. Эта задача впервые была определена Финденом и Гордоном в контексте двух бинарных деревьев [7]. Авторы также предложили эвристический алгоритм решения задачи. Динамический алгоритм вычисления значений MAST для двух бинарных деревьев за время O(n2) был изложен в [ ]. Впоследствии было предложено несколько усовершенствований для повышения скорости работы алгоритмов вычисления значений MAST для двух деревьев в свете различных предположений о корнях и о степенях деревьев [5, 10, 8 и список литературы в них].

Задача нахождения MAST для трех и более деревьев с неограниченными степенями является NP-полной [ ]. Амир и Кеселман предложили алгоритм для k деревьев с ограниченными степенями сложности O(knd+1 + n2d). Описанный здесь алгоритм обеспечивает время O(kn3 + nd) для случая, когда число деревьев равно k и степень хотя бы одного дерева ограничена d. Для d = 2 сложность алгоритма зависит от первого терма. Алгоритм сложности O(kn3) для данного случая был предложен Брайантом [ ], реализация этого алгоритма со сложностью O(n2log -1 n) изложена в [9].

Задача k-MAST является разрешимой при помощи алгоритмов с фиксированным параметром p, где p – наименьшее количество меток листьев, таких, что удаление соответствующих листьев приводит к возникновению соответствия (см. [3] и список литературы). Возможность аппроксимации MAST и соответствующая задача изучались в [ ] и литературе по списку.