Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями

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

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

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

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

Если операция отрезает некоторые черные ребра, мы говорим, что она действует на этих ребрах. Операция называется 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-циклов