4501
правка
Необщие ребра в филогенетических деревьях: различия между версиями
Перейти к навигации
Перейти к поиску
м
Необщие ребра в филогенетических деревьях (посмотреть исходный код)
Версия от 14:23, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 40: | Строка 40: | ||
'''Теорема 1. Пусть T и T' – два входных филогенетических дерева с одним и тем же множеством меток листьев, n – число листьев в каждом дереве. Тогда расстояние в необщих ребрах между деревьями T и T' может быть найдено за время O(n).''' | '''Теорема 1. Пусть T и T' – два входных филогенетических дерева с одним и тем же множеством меток листьев, n – число листьев в каждом дереве. Тогда расстояние в необщих ребрах между деревьями T и T' может быть найдено за время O(n).''' | ||
Пусть <math>\Delta \;</math> – набор из k филогенетических деревьев с одним и тем же множеством меток листьев, n – число листьев в каждом дереве. Задача нахождения расстояния в необщих ребрах для всех пар может быть решена путем применения теоремы 1 к каждой паре филогенетических деревьев; таким образом, время ее решения составляет <math>O(k^2 n) \;</math>. Паттенгейл и Морэ [9] предложили рандомизированный алгоритм на базе [7] для приближенного решения задачи, который работает быстрее в случае <math>n \le k \le 2^n \;</math>. | Пусть <math>\Delta \;</math> – набор из k филогенетических деревьев с одним и тем же множеством меток листьев, n – число листьев в каждом дереве. Задача нахождения расстояния в необщих ребрах для всех пар может быть решена путем применения теоремы 1 к каждой паре филогенетических деревьев; таким образом, время ее решения составляет <math>O(k^2 n) \;</math>. Паттенгейл и Морэ [9] предложили рандомизированный алгоритм на базе [7] для приближенного решения задачи, который работает быстрее в случае <math>n \le k \le 2^n \;</math>. | ||
'''Теорема 2. Пусть <math>\varepsilon \;</math> – параметр, <math>\varepsilon > 0 \;</math>. Тогда существует рандомизированный алгоритм, такой, что с вероятностью не менее <math>1 - k^{-2} \;</math> расстояние в необщих ребрах между каждой парой входных филогенетических деревьев из <math>\Delta \;</math> может быть аппроксимировано с коэффициентом <math>(1 + \varepsilon) \;</math> от действительного расстояния; время | '''Теорема 2. Пусть <math>\varepsilon \;</math> – параметр, <math>\varepsilon > 0 \;</math>. Тогда существует рандомизированный алгоритм, такой, что с вероятностью не менее <math>1 - k^{-2} \;</math> расстояние в необщих ребрах между каждой парой входных филогенетических деревьев из <math>\Delta \;</math> может быть аппроксимировано с коэффициентом <math>(1 + \varepsilon) \;</math> от действительного расстояния; время выполнения этого алгоритма составляет <math>O(k(n^2 + k \; log \; k) / \varepsilon^2)</math>.''' | ||
В общем случае, пусть даны два входных филогенетических дерева R и R' с одним и тем же множеством меток листьев и одним и тем же мультимножеством весов ребер, n – число листьев в каждом дереве. Обобщенная задача нахождения расстояния в необщих ребрах может быть легко решена за время <math>O(n^2) \;</math> путем последовательного применения теоремы 1. Время | |||
В общем случае, пусть даны два входных филогенетических дерева R и R' с одним и тем же множеством меток листьев и одним и тем же мультимножеством весов ребер, n – число листьев в каждом дереве. Обобщенная задача нахождения расстояния в необщих ребрах может быть легко решена за время <math>O(n^2) \;</math> путем последовательного применения теоремы 1. Время выполнения удалось улучшить Хону и коллегам [5]. | |||
| Строка 54: | Строка 56: | ||
Филогенетические деревья широко используются в биологии для моделирования эволюционных взаимоотношений между видами. Многие применяемые методы реконструкции (такие как максимальная экономичность, максимальное правдоподобие, совместимость и матрица расстояний) дают в результате разные филогенетические деревья на основе одного и того же набора видов; любопытно было бы вычислить расхождения между этими деревьями. Кроме того, в процессе сравнения можно обнаружить информацию о редких генетических событиях – таких как рекомбинация или конверсия генов. Чаще всего применяется метрика расхождения под названием «метрика Робинсона-Фоулдса» [11], представляющая собой расстояние в необщих ребрах. | Филогенетические деревья широко используются в биологии для моделирования эволюционных взаимоотношений между видами. Многие применяемые методы реконструкции (такие как максимальная экономичность, максимальное правдоподобие, совместимость и матрица расстояний) дают в результате разные филогенетические деревья на основе одного и того же набора видов; любопытно было бы вычислить расхождения между этими деревьями. Кроме того, в процессе сравнения можно обнаружить информацию о редких генетических событиях – таких как рекомбинация или конверсия генов. Чаще всего применяется метрика расхождения под названием «метрика Робинсона-Фоулдса» [11], представляющая собой расстояние в необщих ребрах. | ||
Были предложены и другие метрики расхождения – например, [[Обмен ближайшими соседями и относительные расстояния|обмен ближайшими соседями (NNI) и расстояние переноса поддеревьев (STT)]] (подробнее об этом в [2]). Иногда биологи предпочитают именно эти метрики, поскольку они могут использоваться для обнаружения биологических событий, которые и вызвали расхождение. Однако вычислить эти метрики обычно значительно сложнее. В частности, ДасГупта и коллеги показали, что | Были предложены и другие метрики расхождения – например, [[Обмен ближайшими соседями и относительные расстояния|обмен ближайшими соседями (NNI) и расстояние переноса поддеревьев (STT)]] (подробнее об этом в [2]). Иногда биологи предпочитают именно эти метрики, поскольку они могут использоваться для обнаружения биологических событий, которые и вызвали расхождение. Однако вычислить эти метрики обычно значительно сложнее. В частности, ДасГупта и коллеги показали, что задачи вычисления расстояний NNI и STT являются NP-полными [1, 2]. Для этих задач были разработаны аппроксимационные алгоритмы (NNI: [4, 8], STT: [1, 6]). Любопытно, что для вычисления коэффициентов аппроксимации эти алгоритмы используют расстояние в необщих ребрах. | ||
== См. также == | == См. также == | ||
Родственная задача измерения сходства между двумя входными филогенетическими деревьями | Родственная задача измерения сходства между двумя входными филогенетическими деревьями: | ||
* ''[[Поддерево максимального соответствия]] | * ''[[Поддерево максимального соответствия]] | ||
== Литература == | == Литература == | ||