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

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

Две пары черных ребер называются ''пересекающимися'', если они чередуются в порядке их появления в круге. Пара черных ребер ''пересекается'' с циклом C, если она пересекается с парой черных ребер, принадлежащих к C. Циклы C и D ''пересекаются'', если существует пара черных ребер в C, которая пересекается с D (см. рис. 2e). Два пересекающихся цикла называются ''перемежающимися'', если их пары черных чередуются в порядке их появления в круге (см. рис. 2f). Очевидно, что два цикла могут находиться друг с другом в одном из следующих отношений: (1) непересекающиеся, (2) пересекающиеся, но не перемежающиеся, (3) перемежающиеся. Пара черных ребер называется ''связанной'', если эти ребра соединены серым ребром и если при чтении ребер вдоль цикла они читаются в одном и том же направлении. К примеру, на рис. 2a все пары черных ребер являются связанными. Гу и др. [5] показали, что для пары связанных черных ребер <math>(b_1, b_2)</math> существует цикл С, пересекающийся с <math>(b_1, b_2)</math>. ''1-скрученной парой'' является пара 1-скрученных циклов, повороты которых являются последовательными на круге в конфигурации, состоящей только из этих двух циклов. 1-скрученный цикл называется ''закрытым'' в конфигурации, если два его связанных ребра пересекаются с некоторым другим циклом конфигурации. Конфигурация называется ''закрытой'', если по крайней мере один из ее 1-скрученных циклов является закрытым; в противном случае она называется ''открытой''.

Базовая идея алгоритма 1,5-аппроксимации Хартмана и Шарана для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений заключается в следующем. Авторы свели задачу к сортировке циклической 3-перестановки при помощи транспозиций и транспозиций-обращений и затем сосредоточились на преобразовании 3-циклов в 1-циклы в графе разрывов для этой 3-перестановки. По определению, ориентированный (т. е. 2- или 3-скрученный) 3-цикл позволяет выполнять 2-операцию; поэтому авторы продолжили рассмотрение только неориентированных (т. е. 0- или 1-скрученных) 3-циклов. Поскольку конфигурации, включающие только 0-скрученные 3-циклы, в работе [7] обрабатывались при помощи (0, 2, 2)-последовательностей, Хартман и Шаран ограничили рассмотрение конфигурациями, состоящими из 0- и 1-скрученных 3-циклов. Они показали, что все эти конфигурации являются закрытыми и что они могут быть отсортированы при помощи (0, 2, 2)-последовательности операций для каждой из следующих пяти возможных закрытых конфигураций: (1) закрытая конфигурация с двумя неориентированными перемежающимися 3-циклами, не формирующими 1-скрученную пару; (2) закрытая конфигурация с двумя пересекающимися, 0-скрученными 3-циклами; (3) закрытая конфигурация с двумя пересекающимися, 1-скрученными 3-циклами; (4) закрытая конфигурация с 0-скрученными 3-циклами, пересекающаяся со связанными ребрами 1-скрученного 3-цикла; (5) закрытая конфигурация, содержащая <math>k \ge 2</math> взаимно перемежающихся 1-скрученных 3-циклов, таких, что их повороты являются последовательными на круге, а k – максимальное число, обладающее этим свойством. В результате последовательность операций, использованных Хартманом и Шараном в их алгоритме, содержит только 2-операции и (0, 2, 2)-последовательности. Поскольку каждая последовательность из трех операций увеличивает количество нечетных циклов минимум на 4 из возможных 6 за 3 шага, коэффициент этого аппроксимационного алгоритма составляет 1,5. Кроме того, Хартман и Шаран показали, что их алгоритм можно реализовать за время <math>O(n^{3/2} \sqrt{log \; n})</math> с использованием структуры данных Каплана и Вербина [10], где n – число элементов в перестановке.

При попытке определить эволюционное расстояние между двумя организмами при помощи данных о геноме биологи могут захотеть реконструировать последовательность эволюционных событий, в результате которых один геном был преобразован в другой. Одним из наиболее многообещающих способов выполнения такого филогенетического исследования является сравнение порядка появления идентичных (например, ортологичных) генов в двух разных геномах [9, 12]. Сравнение вычислений глобальных событий перегруппировки (таких как обращения, транспозиции и транспозиции-обращения сегментов генома) может дать более точные и надежные ключи к пониманию эволюционного процесса, чем анализ локальных точечных мутаций (т. е. замен, вставок и удалений нуклеотидов и аминокислот). Обычно два сравниваемых генома представлены в виде перестановок со знаками, каждый элемент которых обозначает ген, а его знак обозначает (транскрипционное) направление соответствующего гена в хромосоме. Таким образом, цель соответствующей задачи перестройки генома заключается в нахождении кратчайшей последовательности операций перегруппировки, при помощи которых одну перестановку можно преобразовать (или, что эквивалентно, ''отсортировать'') в другую. Предыдущие работы были посвящены задаче сортировки перестановок при помощи обращений. Капрара [2] показал, что эта задача является NP-трудной, если рассматриваемая перестановка не имеет знаков. Однако для перестановок со знаками эта задача становится разрешимой; Ханненхалли и Певзнер [6] предложили первый алгоритм с полиномальным временем выполнения для ее решения. Наряду с этим прогресс в решении задачи сортировки при помощи транспозиций был более скромным. До настоящего момента остается открытым вопрос о сложности этой задачи, хотя для ее решения было предложено несколько алгоритмов 1,5-аппроксимации [1, 3, 7]. Недавно коэффициент аппроксимации задачи сортировки при помощи транспозиций был улучшен Элиасом и Хартманом [4] до 1,375. Гу и др. [5], а также Лиин и Сюэ [11] предложили алгоритмы 2-аппроксимации с квадратичным временем выполнения для сортировки линейных перестановок со знаками при помощи транспозиций и транспозиций-обращений. В работе [11] Лин и Сюэ рассмотрели задачу сортировки линейных перестановок со знаками при помощи транспозиций, транспозиций-обращений и двойных обращений и предложили квадратичный алгоритм 1,75-аппроксимации для ее решения. В работе [8] Хартман и Шаран также показали, что эта задача эквивалентна для линейных и циклических перестановок и может быть сведена к сортировке линейных перестановок со знаками при помощи только транспозиций и транспозиций-обращений. Кроме того, они предложили алгоритм 1,5-аппроксимации, который может быть реализован за время <math>O(n^{3/2} \sqrt{log \; n})</math>.