4501
правка
Необщие ребра в филогенетических деревьях: различия между версиями
Перейти к навигации
Перейти к поиску
м
Необщие ребра в филогенетических деревьях (посмотреть исходный код)
Версия от 13:53, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 56: | Строка 56: | ||
Филогенетические деревья широко используются в биологии для моделирования эволюционных взаимоотношений между видами. Многие применяемые методы реконструкции (такие как максимальная экономичность, максимальное правдоподобие, совместимость и матрица расстояний) дают в результате разные филогенетические деревья на основе одного и того же набора видов; любопытно было бы вычислить расхождения между этими деревьями. Кроме того, в процессе сравнения можно обнаружить информацию о редких генетических событиях – таких как рекомбинация или конверсия генов. Чаще всего применяется метрика расхождения под названием «метрика Робинсона-Фоулдса» [11], представляющая собой расстояние в необщих ребрах. | Филогенетические деревья широко используются в биологии для моделирования эволюционных взаимоотношений между видами. Многие применяемые методы реконструкции (такие как максимальная экономичность, максимальное правдоподобие, совместимость и матрица расстояний) дают в результате разные филогенетические деревья на основе одного и того же набора видов; любопытно было бы вычислить расхождения между этими деревьями. Кроме того, в процессе сравнения можно обнаружить информацию о редких генетических событиях – таких как рекомбинация или конверсия генов. Чаще всего применяется метрика расхождения под названием «метрика Робинсона-Фоулдса» [11], представляющая собой расстояние в необщих ребрах. | ||
Были предложены и другие метрики расхождения – например, [[Обмен ближайшими соседями и относительные расстояния|обмен ближайшими соседями (NNI) и расстояние переноса поддеревьев (STT)]] (подробнее об этом в [2]). Иногда биологи предпочитают именно эти метрики, поскольку они могут использоваться для обнаружения биологических событий, которые и вызвали расхождение. Однако вычислить эти метрики обычно значительно сложнее. В частности, ДасГупта и коллеги показали, что задачи вычисления расстояний NNI и STT являются NP-полными [1, 2]. Для этих задач были разработаны алгоритмы | Были предложены и другие метрики расхождения – например, [[Обмен ближайшими соседями и относительные расстояния|обмен ближайшими соседями (NNI) и расстояние переноса поддеревьев (STT)]] (подробнее об этом в [2]). Иногда биологи предпочитают именно эти метрики, поскольку они могут использоваться для обнаружения биологических событий, которые и вызвали расхождение. Однако вычислить эти метрики обычно значительно сложнее. В частности, ДасГупта и коллеги показали, что задачи вычисления расстояний NNI и STT являются NP-полными [1, 2]. Для этих задач были разработаны аппроксимационные алгоритмы (NNI: [4, 8], STT: [1, 6]). Любопытно, что для вычисления коэффициентов аппроксимации эти алгоритмы используют расстояние в необщих ребрах. | ||
== См. также == | == См. также == | ||