Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5)

Ключевые слова и синонимы

Перестройка генома

Постановка задачи

Одним из наиболее многообещающих способов определения эволюционного расстояния между двумя организмами является сравнение порядка появления идентичных (например, ортологичных) генов в их геномах. Соответствующая задача перестройки генома заключается в нахождении кратчайшей последовательности операций перегруппировки, при помощи которых один геном можно перестроить в другой. В работе [ ] Хартман и Шаран предложили алгоритм 1,5-аппроксимации для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, улучшив ранее полученный коэффициент аппроксимации для этой задачи. Их алгоритм также работает быстрее современных аналогов, требуя O(n3/2 plog n) времени для 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) удобно изображать на круге, поскольку его черные ребра (т. е. толстые линии) располагаются на окружности, а серые (т. е. тонкие) являются хордами