4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→См. также) |
||
(не показано 6 промежуточных версий этого же участника) | |||
Строка 34: | Строка 34: | ||
Примечание 1. Если <math>mast(\overrightarrow{v}) > 0 \;</math>, то <math>\overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \;</math> для некоторых меток листьев a, b, где <math>lca^{T^i} (a, b) \;</math> – самый низкий общий предок листьев с метками a и b в дереве V. | '''Примечание 1.''' Если <math>mast(\overrightarrow{v}) > 0 \;</math>, то <math>\overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \;</math> для некоторых меток листьев a, b, где <math>lca^{T^i} (a, b) \;</math> – самый низкий общий предок листьев с метками a и b в дереве V. | ||
Кортеж <math>\overrightarrow{v} \;</math>, такой, что <math>\overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \;</math> для некоторых <math>a, b \in A \;</math>, называется lca-кортежем. Согласно примечанию 1, достаточно вычислить значения mast только для lca-кортежей. Как и при использовании наивного подхода, <math>mast(\overrightarrow{v}) \;</math> вычисляется из значений mast других lca-кортежей, доминируемых <math>\overrightarrow{v} \;</math>. Еще одно важное наблюдение заключается в том, что для вычисления <math>mast(\overrightarrow{v}) \;</math> необходимы только некоторые lca-кортежи, доминируемые <math>\overrightarrow{v} \;</math>. Чтобы реализовать его, Фарах и коллеги определяют так называемое отношение истинного доминирования и показывают, что значение mast для любого lca-кортежа <math>\overrightarrow{v} \;</math> может быть вычислено из значений mast lca-кортежей, истинно доминируемых <math>\overrightarrow{v} \;</math>, и что отношение истинного доминирования имеет размер <math>O(n^3) \;</math>. | Кортеж <math>\overrightarrow{v} \;</math>, такой, что <math>\overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \;</math> для некоторых <math>a, b \in A \;</math>, называется lca-кортежем. Согласно примечанию 1, достаточно вычислить значения mast только для lca-кортежей. Как и при использовании наивного подхода, <math>mast(\overrightarrow{v}) \;</math> вычисляется из значений mast других lca-кортежей, доминируемых <math>\overrightarrow{v} \;</math>. Еще одно важное наблюдение заключается в том, что для вычисления <math>mast(\overrightarrow{v}) \;</math> необходимы только некоторые lca-кортежи, доминируемые <math>\overrightarrow{v} \;</math>. Чтобы реализовать его, Фарах и коллеги определяют так называемое отношение истинного доминирования и показывают, что значение mast для любого lca-кортежа <math>\overrightarrow{v} \;</math> может быть вычислено из значений mast lca-кортежей, истинно доминируемых <math>\overrightarrow{v} \;</math>, и что отношение истинного доминирования имеет размер <math>O(n^3) \;</math>. | ||
Отношение истинного доминирования | ''Отношение истинного доминирования'' | ||
Проиндексируем потомков каждой внутренней вершины любого дерева на произвольном пути. Пусть имеется пара <math>\overrightarrow{v}, \overrightarrow{w}</math> lca-кортежей, такая, что <math>\overrightarrow{w} \prec \overrightarrow{v} \;</math>. Соответствующее отношение доминирования ассоциирует ее с направлением <math>\overrightarrow{\delta}_{\overrightarrow{w} \prec \overrightarrow{v}} = (\delta_1, ..., \delta_k)</math>, по которому <math>\overrightarrow{w_i} \;</math> спускается от потомка <math>v_i \;</math>, индексированного с <math>\delta_i \;</math>. Пусть <math>v_i(j) \;</math> – потомок <math>v_i \;</math> с индексом <math>j \;</math>. Доминирование по направлению считается активным, если поддеревья с | Проиндексируем потомков каждой внутренней вершины любого дерева на произвольном пути. Пусть имеется пара <math>\overrightarrow{v}, \overrightarrow{w}</math> lca-кортежей, такая, что <math>\overrightarrow{w} \prec \overrightarrow{v} \;</math>. Соответствующее отношение доминирования ассоциирует ее с направлением <math>\overrightarrow{\delta}_{\overrightarrow{w} \prec \overrightarrow{v}} = (\delta_1, ..., \delta_k)</math>, по которому <math>\overrightarrow{w_i} \;</math> спускается от потомка <math>v_i \;</math>, индексированного с <math>\delta_i \;</math>. Пусть <math>v_i(j) \;</math> – потомок <math>v_i \;</math> с индексом <math>j \;</math>. Доминирование по направлению считается активным, если поддеревья с корнями в <math>v_1(\delta_1),..., v_к(\delta+k) \;</math> имеют по меньшей мере одну общую метку листа. Заметим, что каждая метка листа может обозначать только одно активное направление и, следовательно, каждый lca-кортеж может иметь не более и активных направлений доминирования. Два направления <math>\overrightarrow{\delta}_{\overrightarrow{w} \prec \overrightarrow{v}}</math> и <math>\overrightarrow{\delta}_{\overrightarrow{u} \prec \overrightarrow{v}}</math> называются совместимыми в том и только том случае, если векторы направлений различаются по всем координатам. | ||
Определение 1. v истинно доминирует | '''Определение 1.''' <math>\overrightarrow{v} \;</math> истинно доминирует <math>\overrightarrow{u} \;</math> (обозначается <math>\overrightarrow{u} < \overrightarrow{v} \;</math>), если <math>\overrightarrow{v} \;</math> доминирует <math>\overrightarrow{u} \;</math> по активному направлению <math>\overrightarrow{ \delta }</math> и существует другой кортеж, <math>\overrightarrow{w} \;</math>, также доминируемый <math>\overrightarrow{v} \;</math> по активному направлению <math>\overrightarrow{ \delta_{\bot}}</math>, совместимому с <math>\delta \;</math>. | ||
Строка 50: | Строка 50: | ||
Примечание 2. Отношение строгого доминирования < на lca-кортежах имеет размер O( | '''Примечание 2'''. Отношение строгого доминирования <math>< \;</math> на lca-кортежах имеет размер <math>O(n^3) \;</math>. Кроме того, оно может быть вычислено за время <math>O(kn^3) \;</math>. | ||
Примечание 3. Для любого lca-кортежа | '''Примечание 3.''' Для любого lca-кортежа <math>\overrightarrow{v} \;</math>, в случае, если <math>mast(\overrightarrow{v}) > 0 \;</math>, имеет место одна из двух ситуаций: (1) <math>\overrightarrow{v} \;</math> представляет собой lca-кортеж, состоящий из листьев с одной и той же меткой; (2) <math>\overrightarrow{v} \;</math> истинно доминирует некоторый lca-кортеж. | ||
Остается показать, как можно вычислить значения mast( | Остается показать, как можно вычислить значения <math>mast(\overrightarrow{v}) \;</math>. Для каждого lca-кортежа <math>\overrightarrow{v} \;</math> строится так называемый граф совместимости <math>G(\overrightarrow{v}) \;</math>. Вершинами <math>G(\overrightarrow{v}) \;</math> являются активные направления из <math>\overrightarrow{v} \;</math>; между двумя вершинами имеется ребро в том и только том случае, если соответствующие направления совместимы. Вершины <math>G(\overrightarrow{v}) \;</math> имеют веса; вес вершины, соответствующей активному направлению <math>\overrightarrow{ \delta } \;</math>, равен максимальному значению mast lca-кортежа, доминируемого v по этому направлению. Пусть <math>MWC(G(\overrightarrow{v})) \;</math> – клика с максимальным весом в <math>G(\overrightarrow{v}) \;</math>. | ||
Восходящий алгоритм вычисления ненулевых значений mast основан на следующей рекурсивной зависимости, корректность которой непосредственно задают соответствующие определения и | Восходящий алгоритм вычисления ненулевых значений mast основан на следующей рекурсивной зависимости, корректность которой непосредственно задают соответствующие определения и Примечание 3. | ||
Лемма 2. Для любого lca-кортежа v | '''Лемма 2.''' Для любого lca-кортежа <math>\overrightarrow{v} \;</math> | ||
\ 1, если все элементы v являются листьями | <math>mast(\overrightarrow{v}) = max \{ 1, </math> если все элементы <math>\overrightarrow{v} \;</math> являются листьями; <math>MWC(G(\overrightarrow{v})) \;</math> в противном случае<math>\} \;</math> | ||
MWC(G( | |||
Наконец, остается продемонстрировать, что после того, как lca-кортежи и отношение строгого доминирования предварительно вычислены, вычисление всех ненулевых значений mast может быть выполнено за время O( | Наконец, остается продемонстрировать, что после того, как lca-кортежи и отношение строгого доминирования предварительно вычислены, вычисление всех ненулевых значений mast может быть выполнено за время <math>O(n^d) \;</math>. Это производится при помощи генерации всех возможных клик для всех значений <math>G(\overrightarrow{v}) \;</math>. Используя тот факт, что степень по меньшей мере одного дерева ограничена <math>d \;</math>, можно показать, что все клики могут быть сгенерированы за время <math>O \bigg( \sum_{l \le d} \binom{n}{l}) = O(d^3(ne/d)^d \bigg) \;</math> и что их имеется <math>O(d(ne/d)^d) \;</math> штук [6]. | ||
== Применение == | == Применение == | ||
Актуальность задачи k-MAST связана с необходимостью сравнения эволюционных деревьев. Недавние достижения в разработке экспериментальных техник в молекулярной биологии дали много разных данных, которые могут быть использованы для построения эволюционных деревьев. Разнообразие данных в сочетании с разнообразием методов построения эволюционных деревьев нередко приводит к ситуации, когда эволюция одного и того же множества видов объясняется различными эволюционными деревьями. Задача нахождения поддерева максимального соответствия возникла как способ нахождения соответствия между подобными деревьями и как метод определения общего для таких деревьев поддерева. Эта задача впервые была определена Финденом и Гордоном в контексте двух бинарных деревьев [7]. Авторы также предложили эвристический алгоритм решения задачи. Динамический алгоритм вычисления значений MAST для двух бинарных деревьев за время O( | Актуальность задачи k-MAST связана с необходимостью сравнения эволюционных деревьев. Недавние достижения в разработке экспериментальных техник в молекулярной биологии дали много разных данных, которые могут быть использованы для построения эволюционных деревьев. Разнообразие данных в сочетании с разнообразием методов построения эволюционных деревьев нередко приводит к ситуации, когда эволюция одного и того же множества видов объясняется различными эволюционными деревьями. Задача нахождения поддерева максимального соответствия возникла как способ нахождения соответствия между подобными деревьями и как метод определения общего для таких деревьев поддерева. Эта задача впервые была определена Финденом и Гордоном в контексте двух бинарных деревьев [7]. Авторы также предложили эвристический алгоритм решения задачи. Динамический алгоритм вычисления значений MAST для двух бинарных деревьев за время <math>O(n^2) \;</math> был изложен в [11]. Впоследствии было предложено несколько усовершенствований для повышения скорости работы алгоритмов вычисления значений MAST для двух деревьев в свете различных предположений о корнях и о степенях деревьев [5, 10, 8 и список литературы в них]. | ||
Задача нахождения MAST для трех и более деревьев с неограниченными степенями является NP-полной [ ]. Амир и Кеселман предложили алгоритм для k деревьев с ограниченными степенями сложности O( | Задача нахождения MAST для трех и более деревьев с неограниченными степенями является NP-полной [1]. Амир и Кеселман предложили алгоритм для k деревьев с ограниченными степенями сложности <math>O(kn^{d+1} + n^2d) =;</math>. Описанный здесь алгоритм обеспечивает время <math>O(kn^3 + n^d) \;</math> для случая, когда число деревьев равно k и степень хотя бы одного дерева ограничена <math>d \;</math>. Для <math>d = 2 \;</math> сложность алгоритма зависит от первого терма. Алгоритм сложности <math>O(kn^3) \;</math> для данного случая был предложен Брайантом [4], реализация этого алгоритма со сложностью <math>O(n^2 \; log^{k-1} \; n)</math> изложена в [9]. | ||
Задача k-MAST является разрешимой при помощи алгоритмов с фиксированным параметром p, где p – наименьшее количество меток листьев, таких, что удаление соответствующих листьев приводит к возникновению соответствия (см. [3] и список литературы). Возможность аппроксимации MAST и соответствующая задача изучались в [ ] и литературе по списку. | Задача k-MAST является разрешимой при помощи алгоритмов с фиксированным параметром p, где p – наименьшее количество меток листьев, таких, что удаление соответствующих листьев приводит к возникновению соответствия (см. [3] и список литературы). Возможность аппроксимации MAST и соответствующая задача изучались в [2] и литературе по списку. | ||
== См. также == | == См. также == | ||
* ''[[Поддерево максимального соответствия (для двух бинарных деревьев)]] | |||
* ''[[Супердерево максимального соответствия]] | |||
* ''[[Дерево максимальной совместимости]] | |||
== Литература == | == Литература == |
правок