1294
правки
Обмен ближайшими соседями и относительные расстояния: различия между версиями
Материал из WEGA
Обмен ближайшими соседями и относительные расстояния (посмотреть исходный код)
Версия от 04:35, 22 ноября 2024
, 22 ноября 2024→Литература
Irina (обсуждение | вклад) м (→Применение) |
KVN (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии 1 участника) | |||
| Строка 8: | Строка 8: | ||
• найдено соответствие между расстоянием обмена ближайшими соседями и расстоянием переноса поддеревьев с линейной стоимостью на невзвешенных деревьях; | • найдено соответствие между расстоянием обмена ближайшими соседями и расстоянием переноса поддеревьев с линейной стоимостью на невзвешенных деревьях; | ||
• вычисление расстояния обмена ближайшими соседями является NP-полной задачей, однако допускает возможность разрешимости с фиксированными параметрами и применение алгоритмов | • вычисление расстояния обмена ближайшими соседями является NP-полной задачей, однако допускает возможность разрешимости с фиксированными параметрами и применение аппроксимационных алгоритмов с логарифмическими коэффициентами; | ||
• разработан алгоритм 2-аппроксимации для вычисления расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях. | • разработан алгоритм 2-аппроксимации для вычисления расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях. | ||
| Строка 83: | Строка 83: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
1. Существует ли алгоритм | 1. Существует ли аппроксимационный алгоритм с константным коэффициентом для вычисления расстояния обмена ближайшими соседями на невзвешенных эволюционных деревьях, или O(log n)-аппроксимация – лучшая из всех? | ||
2. Является ли вычисление расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях NP-полной задачей, если | 2. Является ли вычисление расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях NP-полной задачей, если не допускается неуникальность меток листьев? | ||
3. Можно ли улучшить коэффициент аппроксимации для вычисления расстояния переноса поддерева с линейной стоимостью на взвешенных эволюционных деревьях? | 3. Можно ли улучшить коэффициент аппроксимации для вычисления расстояния переноса поддерева с линейной стоимостью на взвешенных эволюционных деревьях? | ||
== См. также == | == См. также == | ||
* ''[[Построение | * ''[[Построение тонкослойной филогенетической сети]] | ||
* ''[[Поддерево максимального соответствия (для двух бинарных деревьев)]] | * ''[[Поддерево максимального соответствия (для двух бинарных деревьев)]] | ||
* ''[[Поддерево максимального соответствия (для трех или более деревьев)]] | * ''[[Поддерево максимального соответствия (для трех или более деревьев)]] | ||
* ''[[Построение филогенетического дерева из матрицы расстояний]] | * ''[[Построение филогенетического дерева из матрицы расстояний]] | ||
== Литература == | == Литература == | ||
| Строка 116: | Строка 115: | ||
10. Robinson, D.F.: Comparison of labeled trees with valency three. J Combinator. Theory Series B 11,105-119 (1971) | 10. Robinson, D.F.: Comparison of labeled trees with valency three. J Combinator. Theory Series B 11,105-119 (1971) | ||
[[Категория: Совместное определение связанных терминов]] | |||
