4430
правок
Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями
Материал из WEGA
Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5) (посмотреть исходный код)
Версия от 14:37, 1 марта 2019
, 1 марта 2019нет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Перестройка генома == Постановка задачи == Одним из наиболе…») |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Одним из наиболее многообещающих способов определения эволюционного расстояния между двумя организмами является сравнение порядка появления идентичных (например, ортологичных) генов в их геномах. Соответствующая задача перестройки генома заключается в нахождении кратчайшей последовательности операций перегруппировки, при помощи которых один геном можно перестроить в другой. В работе [ ] Хартман и Шаран предложили алгоритм 1,5-аппроксимации для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, улучшив ранее полученный коэффициент аппроксимации для этой задачи. Их алгоритм также работает быстрее современных аналогов, требуя O( | Одним из наиболее многообещающих способов определения эволюционного расстояния между двумя организмами является сравнение порядка появления идентичных (например, ортологичных) генов в их геномах. Соответствующая задача перестройки генома заключается в нахождении кратчайшей последовательности операций перегруппировки, при помощи которых один геном можно перестроить в другой. В работе [8] Хартман и Шаран предложили алгоритм 1,5-аппроксимации для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, улучшив ранее полученный коэффициент аппроксимации для этой задачи. Их алгоритм также работает быстрее современных аналогов, требуя <math>O(n^{3/2} \sqrt{log \; n})</math> времени для n генов. | ||
== Нотация и определение == | == Нотация и определение == | ||
| Строка 9: | Строка 9: | ||
[[Файл:Sort_transp_1.png]] | |||
(a) Эквивалентность операций transreversal и revrev на циклических перестановках. (b) Граф разрывов G(JT) перестановки ж = [1,-4,6,-5,2, -7,-3], для которого f(n) = [1;2;8;7; 11; 12; 10;9; 3;4; 14; 13;6;5]. Граф G(n) удобно изображать на круге, поскольку его черные ребра (т. е. толстые линии) располагаются на окружности, а серые (т. е. тонкие) являются хордами | Рисунок 1. (a) Эквивалентность операций transreversal и revrev на циклических перестановках. (b) Граф разрывов G(JT) перестановки ж = [1,-4,6,-5,2, -7,-3], для которого f(n) = [1;2;8;7; 11; 12; 10;9; 3;4; 14; 13;6;5]. Граф G(n) удобно изображать на круге, поскольку его черные ребра (т. е. толстые линии) располагаются на окружности, а серые (т. е. тонкие) являются хордами | ||
== Основные результаты == | == Основные результаты == | ||
