1294
правки
Построение тонкослойной филогенетической сети: различия между версиями
Материал из WEGA
Построение тонкослойной филогенетической сети (посмотреть исходный код)
Версия от 04:49, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 30: | Строка 30: | ||
Далее рассматривается задача построения тонкослойной сети N, согласующейся с максимальным количеством корневых триплетов из T для любого (не обязательно плотного) множества T. Поскольку из теоремы 2 следует, что эта задача является NP-полной, были исследованы алгоритмы | Далее рассматривается задача построения тонкослойной сети N, согласующейся с максимальным количеством корневых триплетов из T для любого (не обязательно плотного) множества T. Поскольку из теоремы 2 следует, что эта задача является NP-полной, были исследованы аппроксимационные алгоритмы для ее приближенного решения. Алгоритм называется k-аппроксимируемым, если он всегда возвращает тонкослойную сеть N, такую, что N(T)/|T| > k, где N(T) – количество корневых триплетов в T, согласующихся с N. | ||
Теорема 3. Пусть дано множество корневых триплетов T. Не существует алгоритма | Теорема 3. Пусть дано множество корневых триплетов T. Не существует аппроксимационного алгоритма, результатом работы которого является тонкослойная сеть N, такая, что N(T)/|T| > 0.4883. | ||
Теорема 4. Пусть дано множество корневых триплетов T. Существует алгоритм | Теорема 4. Пусть дано множество корневых триплетов T. Существует аппроксимационный алгоритм, результатом работы которого является тонкослойная сеть N, такая, что N(T)/|T| > 5/12. Время работы алгоритма составляет О(\А(Т)\\Т\Ъ). | ||
| Строка 92: | Строка 92: | ||
11. Kearney, P.: Phylogenetics and the quartet method. In: Jiang, T., Xu, Y., and Zhang, M.Q. (eds.) Current Topics in Computational Molecular Biology, pp. 111-133. MIT Press, Cambridge (2002) | 11. Kearney, P.: Phylogenetics and the quartet method. In: Jiang, T., Xu, Y., and Zhang, M.Q. (eds.) Current Topics in Computational Molecular Biology, pp. 111-133. MIT Press, Cambridge (2002) | ||
[[Категория: Совместное определение связанных терминов]] | |||
