Ядро для задачи поиска максимального согласия в лесу на нескольких бинарных филогенетических деревьях

arXiv:2602.22281v2 Тип объявления: replace-cross Аннотация: Задача о максимально согласованном лесу (MAF) в филогенетике принимает на вход множество t >= 2 бинарных филогенетических деревьев T на одном и том же множестве таксонов X. Она требует разбиения X на наименьшее число блоков таким образом, чтобы поддеревья, образованные этими блоками, были непересекающимися и имели общую топологию для всех деревьев в T. Мы предлагаем модифицированную версию известного правила редукции цепей, чтобы доказать, что после исчерпывающего применения правил редукции каждое дерево имеет O(t * r * k) листьев, где k — естественный параметр (число блоков), а r = min{max{k,3},t+1}}. Мы доказываем эту оценку как для некорневой, так и для корневой версии задачи и демонстрируем, что оценка r, длина, до которой усекаются общие цепи, является точной. Наши результаты представляют собой первые ядра для MAF в режиме t>2.

Источник: arxiv.org