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

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

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

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

Одним из наиболее многообещающих способов определения эволюционного расстояния между двумя организмами является сравнение порядка появления идентичных (например, ортологичных) генов в их геномах. Соответствующая задача перестройки генома заключается в нахождении кратчайшей последовательности операций перегруппировки, при помощи которых один геном можно перестроить в другой. В работе [8] Хартман и Шаран предложили алгоритм 1,5-аппроксимации для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, улучшив ранее полученный коэффициент аппроксимации для этой задачи. Их алгоритм также работает быстрее современных аналогов, требуя [math]\displaystyle{ O(n^{3/2} \sqrt{log \; n}) }[/math] времени для n генов.

Нотация и определение

Перестановка со знаками [math]\displaystyle{ \pi = [ \pi_1, \pi_2, ..., \pi_n] }[/math] на [math]\displaystyle{ n (\pi) = n }[/math] элементах представляет собой перестановку, в которой каждому элементу присвоен знак – плюс или минус. Сегментом [math]\displaystyle{ \pi }[/math] является последовательность последовательных элементов [math]\displaystyle{ \pi_i, \pi_{i + 1}, ..., \pi_k }[/math], где [math]\displaystyle{ 1 \le i \le k \le n }[/math]. Обращение [math]\displaystyle{ \rho }[/math] представляет собой операцию, которая меняет порядок элементов в сегменте на противоположный и при этом переключает их знаки. Два сегмента [math]\displaystyle{ \pi_i, \pi_{i + 1}, ..., \pi_k }[/math] и [math]\displaystyle{ \pi_j, \pi_{j + 1}, ..., \pi_l }[/math], называются смежными, если j = k + 1 или i = l + 1. Транспозиция [math]\displaystyle{ \tau }[/math] представляет собой операцию, переставляющую друг с другом два смежных (непересекающихся) сегмента. Транспозиция-обращение (transreversal) [math]\displaystyle{ \tau \rho_{A, B} }[/math] ([math]\displaystyle{ \tau \rho_{B, A} }[/math], соответственно) представляет собой транспозицию, которая переставляет два сегмента A и B и при этом выполняет обращение A (соответственно, B). Операция двойного обращения (revrev) [math]\displaystyle{ \rho \rho }[/math] выполняет обращение каждого из двух смежных сегментов (без перестановки их друг с другом). Задача нахождения кратчайшей последовательности операций транспозиции, транспозиции-обращения и двойного обращения, преобразующей заданную перестановку в тождественную, называется задачей сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений. Длина кратчайшей сортирующей последовательности обращений называется расстоянием обращения [math]\displaystyle{ \pi }[/math] и обозначается как [math]\displaystyle{ d(\pi) }[/math].

Основные результаты

Линейные и циклические перестановки

Операция действует на затронутые сегменты, а также на элементы этих сегментов. Две операции [math]\displaystyle{ \mu }[/math] и [math]\displaystyle{ \mu' }[/math] эквивалентны, если они имеют один и тот же результат перегруппировки, т. е. [math]\displaystyle{ \mu \cdot \pi = \mu\ \cdot \pi }[/math] для всех [math]\displaystyle{ \pi }[/math]. В работе [8] Хартман и Шаран показали, что для элемента [math]\displaystyle{ \chi }[/math] циклической перестановки [math]\displaystyle{ \pi }[/math] и операции [math]\displaystyle{ \mu }[/math], действующей на [math]\displaystyle{ \chi }[/math], существует эквивалентная операция [math]\displaystyle{ \mu' }[/math], не действующая на [math]\displaystyle{ \chi }[/math]. Основываясь на этом свойстве, они доказали, что задача сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений эквивалентна линейным и циклическим перестановкам. Кроме того, они заметили, что операции транспозиций-обращений и двойных обращений являются эквивалентными для циклических перестановок (как показано на рис. 1a), из чего следует, что задача сортировки линейной или циклической перестановки при помощи транспозиций, транспозиций-обращений и двойных обращений может быть сведена к задаче сортировки циклической перестановки при помощи транспозиций и транспозиций-обращений.

Рисунок 1. (a) Эквивалентность операций transreversal и revrev на циклических перестановках. (b) Граф разрывов [math]\displaystyle{ G(\pi) }[/math] перестановки [math]\displaystyle{ \pi = [1, -4, 6, -5, 2, -7, -3] }[/math], для которого [math]\displaystyle{ f(\pi) = [1, 2, 8, 7, 11, 12, 10, 9, 3, 4, 14, 13, 6, 5] }[/math]. [math]\displaystyle{ G(\pi) }[/math] удобно изображать на круге таким образом, что его черные ребра (т. е. толстые линии) располагаются на окружности, а серые (т. е. тонкие) являются хордами

Граф разрывов

Пусть дана перестановка со знаками [math]\displaystyle{ \pi }[/math] на множестве {1, 2, ..., n} из n элементов. Ее можно преобразовать в перестановку без знаков [math]\displaystyle{ f(\pi) = \pi' = [\pi'_1, \pi'_2, ..., \pi'_{2n}] }[/math] на множестве {1, 2, ..., 2n} из 2n элементов путем замены каждого положительного элемента i двумя элементами 2i – 1, 2i (именно в таком порядке), а каждого отрицательного элемента -i – двумя элементами 2i, 2i - 1. Расширенная перестановка [math]\displaystyle{ f(\pi) }[/math] здесь рассматривается как циклическая перестановка при помощи определения 2n + 1 и 1 в индексах и элементах. Чтобы гарантировать, что каждая операция на [math]\displaystyle{ f(\pi) }[/math] может быть имитирована операцией на [math]\displaystyle{ \pi }[/math], для [math]\displaystyle{ f(\pi) }[/math] допускаются только операции, выполняющие разрезание перед нечетными позициями. Граф разрывов [math]\displaystyle{ G(\pi) }[/math] представляет собой граф с раскрашенными ребрами с 2n вершинами {1, 2, ..., 2n}, в котором для любого [math]\displaystyle{ 1 \le i \le n }[/math] вершина [math]\displaystyle{ \pi'_{2i} }[/math] соединяется с [math]\displaystyle{ \pi'_{2i + 1} }[/math] ребром черного цвета, а вершина 2i соединяется с 2i + 1 ребром серого цвета (см. пример на рис. 1b). Поскольку степень каждой вершины в [math]\displaystyle{ G(\pi) }[/math] в точности равна 2, граф уникальным образом разбивается на циклы. k-цикл (то есть цикл длины k) представляет собой цикл с k черными ребрами и является нечетным, если k нечетно. Обозначим количество нечетных циклов в [math]\displaystyle{ G(\pi) }[/math] за [math]\displaystyle{ c_{odd}(\pi) }[/math]. Несложно убедиться в том, что [math]\displaystyle{ G(\pi) }[/math] состоит из n 1-циклов и, следовательно, [math]\displaystyle{ c_{odd}(\pi) = n }[/math], если ж является тождественной перестановкой [1, 2, ..., n]. Гу и др. [5] показали, что [math]\displaystyle{ c_{odd}(\mu \cdot \pi_ \le c_{odd}(\pi) + 2 }[/math] для всех линейных перестановок [math]\displaystyle{ \pi }[/math] и операций [math]\displaystyle{ \mu }[/math]. В работе [8] Хартман и Шаран также отметили, что вышеприведенный результат имеет место также для циклических перестановок, и доказали, что нижняя граница [math]\displaystyle{ d(\pi) }[/math] составляет [math]\displaystyle{ (n(\pi) - c_{odd}(\pi))/2 }[/math].

Преобразование в 3-перестановки

Перестановка называется простой, если ее граф разрывов содержит только k-циклы, где [math]\displaystyle{ k \le 3 }[/math]. Простая перестановка также называется 3-перестановкой, если она не содержит 2-циклов. Преобразование из [math]\displaystyle{ \pi }[/math] в [math]\displaystyle{ \hat{\pi} }[/math] называется безопасным, если [math]\displaystyle{ n(\pi) - c_{odd}(\pi) = n(\hat{\pi}) - c_{odd}(\hat{\pi}) }[/math]. Было показано, что любая перестановка [math]\displaystyle{ \pi }[/math] может быть преобразована в простую перестановку [math]\displaystyle{ \pi' }[/math] при помощи безопасных преобразований и, более того, что любая сортировка [math]\displaystyle{ \pi' }[/math] имитирует сортировку [math]\displaystyle{ \pi }[/math] с тем же количеством операций [6, 11]. Хартман и Шаран [8] также показали, что любая простая перестановка [math]\displaystyle{ \pi' }[/math] может быть преобразована в 3-перестановку [math]\displaystyle{ \hat{\pi} }[/math] при помощи безопасных операций заполнения (преобразующих эти 2-циклы в 1-скрученные 3-циклы) и, более того, что любая сортировка [math]\displaystyle{ \hat{\pi} }[/math] имитирует сортировку [math]\displaystyle{ \pi' }[/math] с тем же количеством операций. Основываясь на этих двух свойствах, можно заключить, что произвольная перестановка [math]\displaystyle{ \pi }[/math] может быть преобразована в 3-перестановку [math]\displaystyle{ \hat{\pi} }[/math], такую, что любая сортировка [math]\displaystyle{ \hat{\pi} }[/math] имитирует сортировку [math]\displaystyle{ \pi }[/math] с тем же количеством операций, предполагая, что можно ограничить рассмотрение только циклическими 3-перестановками.

Типы циклов

Если операция отрезает некоторые черные ребра, мы говорим, что она действует на этих ребрах. Операция называется k-операцией, если она увеличивает число нечетных циклов на k. (0, 2, 2)-последовательностью называется последовательность из трех операций, первая из которых является 0-операцией, а две другие – 2-операциями. Нечетный цикл называется ориентированным, если существует 2-операция, действующая на трех его черных ребрах; в противном случае он является неориентированным. Конфигурация циклов представляет собой подграф графа разрывов, содержащий один или несколько циклов. Как показано на рис. 2(a-d), существуют четыре возможных конфигурации одиночных 3-циклов. Черное ребро называется скрученным, если два его смежных серых ребра пересекают друг друга в циклическом графе разрывов. Цикл является k-скрученным, если k из его черных ребер скручены. Например, 3-циклы на рис. 2(a-d) являются 0-, 1-, 2- и 3-скрученными, соответственно. Хартман и Шаран заметили, что 3-цикл является ориентированным в том или только том случае, если он оказывается 2- или 3-скрученным.

Рисунок 2. Конфигурации 3-циклов. (a) Неориентированный, 0-скрученный 3-цикл. (b) Неориентированный, 1-скрученный 3-цикл. (c) Ориентированный, 2-скрученный 3-цикл. (d) Ориентированный, 3-скрученный 3-цикл. (e) Пара пересекающихся 3-циклов. (f) Пара чередующихся 3-циклов

Конфигурации циклов