Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями
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) удобно изображать на круге, поскольку его черные ребра (т. е. толстые линии) располагаются на окружности, а серые (т. е. тонкие) являются хордами | ||
== Основные результаты == | == Основные результаты == |
Версия от 14:37, 1 марта 2019
Ключевые слова и синонимы
Перестройка генома
Постановка задачи
Одним из наиболее многообещающих способов определения эволюционного расстояния между двумя организмами является сравнение порядка появления идентичных (например, ортологичных) генов в их геномах. Соответствующая задача перестройки генома заключается в нахождении кратчайшей последовательности операций перегруппировки, при помощи которых один геном можно перестроить в другой. В работе [8] Хартман и Шаран предложили алгоритм 1,5-аппроксимации для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, улучшив ранее полученный коэффициент аппроксимации для этой задачи. Их алгоритм также работает быстрее современных аналогов, требуя [math]\displaystyle{ O(n^{3/2} \sqrt{log \; n}) }[/math] времени для n генов.
Нотация и определение
Перестановка со знаками ж = [ж\,%i, ..., ж„] из п{л) = и элементов представляет собой перестановку, в которой каждому элементу присвоен знак – плюс или минус. Сегментом я является последовательность последовательных элементов ж,-, лг,+ь ..., k , где 1 < i < k < n. Обращение р представляет собой операцию, которая меняет порядок элементов в сегменте на противоположный и при этом переключает их знаки. Два сегмента itj, Jij+\,..., ж^ и itj, Jij+\,...,Ж\ называются смежными, если j = k + 1 или i = l + 1. Транспозиция x представляет собой операцию, переставляющую друг с другом два смежных (непересекающихся) сегмента. Транспозиция-обращение (transreversal) xp^,B (XPB,A, соответственно) представляет собой транспозицию, которая переставляет два сегмента A и B и при этом выполняет обращение A (соответственно, B). Операция двойного обращения (revrev) pp выполняет обращение каждого из двух смежных сегментов (без перестановки их друг с другом). Задача нахождения кратчайшей последовательности операций транспозиции, транспозиции-обращения и двойного обращения, преобразующей заданную перестановку в тождественную, называется задачей сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений. Длина кратчайшей сортирующей последовательности обращений называется расстоянием обращения я и обозначается как d(jr).
Рисунок 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) удобно изображать на круге, поскольку его черные ребра (т. е. толстые линии) располагаются на окружности, а серые (т. е. тонкие) являются хордами