1294
правки
Супердерево максимального соответствия: различия между версиями
Материал из WEGA
Супердерево максимального соответствия (посмотреть исходный код)
Версия от 04:32, 22 ноября 2024
, 22 ноября 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 7 промежуточных версий 1 участника) | |||
| Строка 44: | Строка 44: | ||
Хотя задача MASP является NP-полной, существует алгоритм | Хотя задача MASP является NP-полной, существует аппроксимационный алгоритм для ее приближенного решения. | ||
Теорема 6 ([8]). Задача MASP может быть приближенно решена с множителем | '''Теорема 6 ([8])'''. Задача MASP может быть приближенно решена с множителем <math>\frac{n}{log \; n}</math> за время <math>O(n^2) \cdot min \{ O(k \cdot (log \; log \; n)^2), O(k + log \; n \cdot log \; log \; n) \} </math>. MASP, ограниченная корневыми триплетами, может быть приближенно решена с множителем <math>\frac{n}{log \; n}</math> за время <math>O(k + n^2 log^2 \; n)</math>. | ||
Также существуют алгоритмы вычисления MASP с фиксированными параметрами и полиномиальным временем решения. Случай с множеством k бинарных деревьев T с n различных меток листьев рассматривался множеством исследователей. Дженссон и коллеги [ ] первыми предложили алгоритм вычисления MAST на T с временем | Также существуют алгоритмы вычисления MASP с фиксированными параметрами и полиномиальным временем решения. Случай с множеством k бинарных деревьев T с n различных меток листьев рассматривался множеством исследователей. Дженссон и коллеги [8] первыми предложили алгоритм вычисления MAST на T с временем выполнения <math>O(k(2n^2)^{3k^2}) \;</math>. Недавно Гийемо и Берри [5] улучшили это время до <math>O((8n)^k) \;</math>; Хоанг и Сунг [7] снизили его до <math>O((6n)^k) \;</math>, что показано в теореме 7. | ||
Теорема 7 ([7]). Пусть дано множество k бинарных деревьев T с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время O((6n)k) | '''Теорема 7 ([7])'''. Пусть дано множество k бинарных деревьев T с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время <math>O((6n)^k) \;</math>. | ||
Для случая, когда множество k бинарных деревьев T имеют степень D и n различных меток листьев, Хоанг и Сунг [7] предложили следующее решение для нахождения MASP с фиксированными параметрами и полиномиальным временем выполнения. | |||
Теорема 8 ([ ]). Пусть дано множество k бинарных деревьев T степени D с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время O((kD)kD+3(2n)k). | |||
'''Теорема 8 ([7])'''. Пусть дано множество k бинарных деревьев T степени D с n различных меток листьев; их супердерево максимального соответствия может быть найдено за время <math>O((kD)^{kD+3} (2n)^k) \;</math>. | |||
== Применение == | == Применение == | ||
| Строка 70: | Строка 71: | ||
Задача 2. Пусть D = | '''Задача 2'''. Пусть <math>D = \{ T_1, T_2, ..., T_k \} \;</math> – множество корневых неупорядоченных деревьев, в котором каждое дерево <math>T_i \;</math> имеет уникальные метки листьев, при этом множества меток листьев <math>\Lambda(T_i) \;</math> могут перекрываться. Задача нахождения супердерева максимальной совместимости (MCSP) заключается в построении дерева <math>Q \;</math> с уникальными метками листьев, с множеством меток листьев <math>\Lambda(Q) \subseteq \bigcup_{T_i \in D} \Lambda(T_i) \;</math>, таким, что <math>| \Lambda(Q) | \;</math> максимально и для каждого <math>T_i \in D \;</math> топологическое ограничение поддерева <math>Q_i' \;</math> дерева <math>Q \;</math> согласно <math>\Lambda(T_i) \;</math> уточняет топологическое ограничение <math>T'_i \;</math> согласно <math>T_i \;</math>; иначе говоря, <math>T'_i \;</math> может быть получено путем коллапсирования определенных ребер <math>Q'_i \;</math>. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 79: | Строка 79: | ||
== См. также == | == См. также == | ||
* ''[[Поддерево максимального соответствия|Поддерево максимального соответствия (для двух бинарных деревьев)]] | |||
* ''[[Поддерево максимального соответствия (для трех или более деревьев)]] | |||
* ''[[Дерево максимальной совместимости]] | |||
== Литература == | == Литература == | ||
| Строка 106: | Строка 106: | ||
11. Sanderson, M.J., Purvis, A., Henze, C.: Phylogenetic supertrees: assembling the trees of life. TRENDS in Ecology & Evolution, 13(3),105-109(1998) | 11. Sanderson, M.J., Purvis, A., Henze, C.: Phylogenetic supertrees: assembling the trees of life. TRENDS in Ecology & Evolution, 13(3),105-109(1998) | ||
[[Категория: Совместное определение связанных терминов]] | |||
