Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 9 промежуточных версий этого же участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Одним из наиболее многообещающих способов определения эволюционного расстояния между двумя организмами является сравнение порядка появления идентичных (например, ортологичных) генов в их геномах. Соответствующая задача перестройки генома заключается в нахождении кратчайшей последовательности операций перегруппировки, при помощи которых один геном можно перестроить в другой. В работе [8] Хартман и Шаран предложили алгоритм 1,5-аппроксимации для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, улучшив ранее полученный коэффициент аппроксимации для этой задачи. Их алгоритм также работает быстрее современных аналогов, требуя <math>O(n^{3/2} \sqrt{log \; n})</math> времени для n генов. | Одним из наиболее многообещающих способов определения эволюционного расстояния между двумя организмами является сравнение порядка появления идентичных (например, ортологичных) генов в их геномах. Соответствующая задача перестройки генома заключается в нахождении кратчайшей последовательности операций перегруппировки, при помощи которых один геном можно перестроить в другой. В работе [8] Хартман и Шаран предложили алгоритм 1,5-аппроксимации для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, улучшив ранее полученный коэффициент аппроксимации 1,75 для этой задачи. Их алгоритм также работает быстрее современных ему аналогов, требуя <math>O(n^{3/2} \sqrt{log \; n})</math> времени для n генов. | ||
== Нотация и определение == | == Нотация и определение == | ||
''Перестановка со знаками'' <math>\pi = [ \pi_1, \pi_2, ..., \pi_n]</math> на <math>n (\pi) | ''Перестановка со знаками'' <math>\pi = [ \pi_1, \pi_2, ..., \pi_n]</math> на <math>n (\pi) \equiv 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>. | ||
| Строка 12: | Строка 12: | ||
'''Линейные и циклические перестановки''' | '''Линейные и циклические перестановки''' | ||
Операция ''действует | ''Операция'' действует на затронутые сегменты, а также на элементы этих сегментов. Две операции <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), из чего следует, что задача сортировки линейной или циклической перестановки при помощи транспозиций, транспозиций-обращений и двойных обращений может быть сведена к задаче сортировки циклической перестановки при помощи транспозиций и транспозиций-обращений. | ||
| Строка 22: | Строка 22: | ||
'''Граф разрывов''' | '''Граф разрывов''' | ||
Пусть дана перестановка со знаками <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>, если | Пусть дана перестановка со знаками <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>, если <math>\pi</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>. | ||
| Строка 32: | Строка 32: | ||
'''Типы циклов''' | '''Типы циклов''' | ||
Если операция отрезает некоторые черные ребра, мы говорим, что она действует на этих ребрах. Операция называется 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-скрученным. | Если операция ''отрезает'' некоторые черные ребра, мы говорим, что она действует на этих ребрах. Операция называется ''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-скрученным. | ||
[[Файл:Sort_transp_2.png]] | [[Файл:Sort_transp_2.png]] | ||
Рисунок 2. Конфигурации 3-циклов. (a) Неориентированный, 0-скрученный 3-цикл. (b) Неориентированный, 1-скрученный 3-цикл. (c) Ориентированный, 2-скрученный 3-цикл. (d) Ориентированный, 3-скрученный 3-цикл. (e) Пара пересекающихся 3-циклов. (f) Пара | Рисунок 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 – число элементов в перестановке. | |||
'''Теорема 1. Задача сортировки линейных перестановок при помощи транспозиций, транспозиций-обращений и двойных обращений является линейно эквивалентной задаче сортировки циклических перестановок при помощи транспозиций, транспозиций-обращений и двойных обращений.''' | |||
'''Теорема 2. Существует алгоритм 1,5-аппроксимации для сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, выполняющийся за время <math>O(n^{3/2} \sqrt{log \; n})</math>.''' | |||
== Применение == | |||
При попытке определить эволюционное расстояние между двумя организмами при помощи данных о геноме биологи могут захотеть реконструировать последовательность эволюционных событий, в результате которых один геном был преобразован в другой. Одним из наиболее многообещающих способов выполнения такого филогенетического исследования является сравнение порядка появления идентичных (например, ортологичных) генов в двух разных геномах [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>. | |||
== См. также == | |||
* [[Сортировка перестановок со знаками при помощи обращений (расстояние обращения)]] | |||
* [[Сортировка перестановок со знаками при помощи обращений (последовательность обращений)]] | |||
== Литература == | |||
1. Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM J. Discret. Math. 11, 224-240 (1998) | |||
2. Caprara, A.: Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J. Discret. Math. 12,91-110 (1999) | |||
3. Christie, D.A.: Genome Rearrangement Problems. Ph. D. thesis, Department of Computer Science. University of Glasgow, U.K. (1999) | |||
4. Elias, I., Hartman, T.: A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Transactions on Computational Biology and Bioinformatics 3, 369-379 (2006) | |||
5. Gu, Q.P., Peng, S., Sudborough, H.: A 2-approximation algorithm for genome rearrangements by reversals and transpositions. Theor. Comput. Sci. 210, 327-339 (1999) | |||
6. Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. Assoc. Comput. Mach. 46,1 -27 (1999) | |||
7. Hartman, T., Shamir, R.: A simpler and faster 1.5-approximation algorithm for sorting by transpositions. Inf. Comput. 204, 275-290 (2006) | |||
8. Hartman, T., Sharan, R.: A 1.5-approximation algorithm for sorting by transpositions and transreversals. In: Proceedings of the 4th Workshop on Algorithms in Bioinformatics (WABI'04), pp. 50-61. Bergen, Norway, 17-21 Sep (2004) | |||
9. Hoot, S.B., Palmer, J.D.: Structural rearrangements, including parallel inversions, within the chloroplast genome of Anemone and related genera. J. Mol. Evol. 38, 274-281 (1994) | |||
10. Kaplan, H., Verbin, E.: Efficient data structures and a new randomized approach for sorting signed permutations by reversals. In: Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching (CPM'03), pp. 170-185. Morelia, Michocan, Mexico, 25-27 Jun (2003) | |||
11. Lin, G.H., Xue, G.: Signed genome rearrangements by reversals and transpositions: models and approximations. Theor. Comput. Sci.259,513-531 (2001) | |||
12. Palmer, J.D., Herbon, L.A.: Tricircular mitochondrial genomes of Brassica and Raphanus: reversal of repeat configurations by inversion. Nucleic Acids Res. 14,9755-9764 (1986) | |||
Текущая версия от 13:38, 1 октября 2023
Ключевые слова и синонимы
Перестройка генома
Постановка задачи
Одним из наиболее многообещающих способов определения эволюционного расстояния между двумя организмами является сравнение порядка появления идентичных (например, ортологичных) генов в их геномах. Соответствующая задача перестройки генома заключается в нахождении кратчайшей последовательности операций перегруппировки, при помощи которых один геном можно перестроить в другой. В работе [8] Хартман и Шаран предложили алгоритм 1,5-аппроксимации для решения задачи сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, улучшив ранее полученный коэффициент аппроксимации 1,75 для этой задачи. Их алгоритм также работает быстрее современных ему аналогов, требуя [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) \equiv 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], если [math]\displaystyle{ \pi }[/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-циклов
Конфигурации циклов
Две пары черных ребер называются пересекающимися, если они чередуются в порядке их появления в круге. Пара черных ребер пересекается с циклом C, если она пересекается с парой черных ребер, принадлежащих к C. Циклы C и D пересекаются, если существует пара черных ребер в C, которая пересекается с D (см. рис. 2e). Два пересекающихся цикла называются перемежающимися, если их пары черных чередуются в порядке их появления в круге (см. рис. 2f). Очевидно, что два цикла могут находиться друг с другом в одном из следующих отношений: (1) непересекающиеся, (2) пересекающиеся, но не перемежающиеся, (3) перемежающиеся. Пара черных ребер называется связанной, если эти ребра соединены серым ребром и если при чтении ребер вдоль цикла они читаются в одном и том же направлении. К примеру, на рис. 2a все пары черных ребер являются связанными. Гу и др. [5] показали, что для пары связанных черных ребер [math]\displaystyle{ (b_1, b_2) }[/math] существует цикл С, пересекающийся с [math]\displaystyle{ (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]\displaystyle{ k \ge 2 }[/math] взаимно перемежающихся 1-скрученных 3-циклов, таких, что их повороты являются последовательными на круге, а k – максимальное число, обладающее этим свойством. В результате последовательность операций, использованных Хартманом и Шараном в их алгоритме, содержит только 2-операции и (0, 2, 2)-последовательности. Поскольку каждая последовательность из трех операций увеличивает количество нечетных циклов минимум на 4 из возможных 6 за 3 шага, коэффициент этого аппроксимационного алгоритма составляет 1,5. Кроме того, Хартман и Шаран показали, что их алгоритм можно реализовать за время [math]\displaystyle{ O(n^{3/2} \sqrt{log \; n}) }[/math] с использованием структуры данных Каплана и Вербина [10], где n – число элементов в перестановке.
Теорема 1. Задача сортировки линейных перестановок при помощи транспозиций, транспозиций-обращений и двойных обращений является линейно эквивалентной задаче сортировки циклических перестановок при помощи транспозиций, транспозиций-обращений и двойных обращений.
Теорема 2. Существует алгоритм 1,5-аппроксимации для сортировки при помощи транспозиций, транспозиций-обращений и двойных обращений, выполняющийся за время [math]\displaystyle{ O(n^{3/2} \sqrt{log \; n}) }[/math].
Применение
При попытке определить эволюционное расстояние между двумя организмами при помощи данных о геноме биологи могут захотеть реконструировать последовательность эволюционных событий, в результате которых один геном был преобразован в другой. Одним из наиболее многообещающих способов выполнения такого филогенетического исследования является сравнение порядка появления идентичных (например, ортологичных) генов в двух разных геномах [9, 12]. Сравнение вычислений глобальных событий перегруппировки (таких как обращения, транспозиции и транспозиции-обращения сегментов генома) может дать более точные и надежные ключи к пониманию эволюционного процесса, чем анализ локальных точечных мутаций (т. е. замен, вставок и удалений нуклеотидов и аминокислот). Обычно два сравниваемых генома представлены в виде перестановок со знаками, каждый элемент которых обозначает ген, а его знак обозначает (транскрипционное) направление соответствующего гена в хромосоме. Таким образом, цель соответствующей задачи перестройки генома заключается в нахождении кратчайшей последовательности операций перегруппировки, при помощи которых одну перестановку можно преобразовать (или, что эквивалентно, отсортировать) в другую. Предыдущие работы были посвящены задаче сортировки перестановок при помощи обращений. Капрара [2] показал, что эта задача является NP-трудной, если рассматриваемая перестановка не имеет знаков. Однако для перестановок со знаками эта задача становится разрешимой; Ханненхалли и Певзнер [6] предложили первый алгоритм с полиномальным временем выполнения для ее решения. Наряду с этим прогресс в решении задачи сортировки при помощи транспозиций был более скромным. До настоящего момента остается открытым вопрос о сложности этой задачи, хотя для ее решения было предложено несколько алгоритмов 1,5-аппроксимации [1, 3, 7]. Недавно коэффициент аппроксимации задачи сортировки при помощи транспозиций был улучшен Элиасом и Хартманом [4] до 1,375. Гу и др. [5], а также Лиин и Сюэ [11] предложили алгоритмы 2-аппроксимации с квадратичным временем выполнения для сортировки линейных перестановок со знаками при помощи транспозиций и транспозиций-обращений. В работе [11] Лин и Сюэ рассмотрели задачу сортировки линейных перестановок со знаками при помощи транспозиций, транспозиций-обращений и двойных обращений и предложили квадратичный алгоритм 1,75-аппроксимации для ее решения. В работе [8] Хартман и Шаран также показали, что эта задача эквивалентна для линейных и циклических перестановок и может быть сведена к сортировке линейных перестановок со знаками при помощи только транспозиций и транспозиций-обращений. Кроме того, они предложили алгоритм 1,5-аппроксимации, который может быть реализован за время [math]\displaystyle{ O(n^{3/2} \sqrt{log \; n}) }[/math].
См. также
- Сортировка перестановок со знаками при помощи обращений (расстояние обращения)
- Сортировка перестановок со знаками при помощи обращений (последовательность обращений)
Литература
1. Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM J. Discret. Math. 11, 224-240 (1998)
2. Caprara, A.: Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J. Discret. Math. 12,91-110 (1999)
3. Christie, D.A.: Genome Rearrangement Problems. Ph. D. thesis, Department of Computer Science. University of Glasgow, U.K. (1999)
4. Elias, I., Hartman, T.: A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Transactions on Computational Biology and Bioinformatics 3, 369-379 (2006)
5. Gu, Q.P., Peng, S., Sudborough, H.: A 2-approximation algorithm for genome rearrangements by reversals and transpositions. Theor. Comput. Sci. 210, 327-339 (1999)
6. Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. Assoc. Comput. Mach. 46,1 -27 (1999)
7. Hartman, T., Shamir, R.: A simpler and faster 1.5-approximation algorithm for sorting by transpositions. Inf. Comput. 204, 275-290 (2006)
8. Hartman, T., Sharan, R.: A 1.5-approximation algorithm for sorting by transpositions and transreversals. In: Proceedings of the 4th Workshop on Algorithms in Bioinformatics (WABI'04), pp. 50-61. Bergen, Norway, 17-21 Sep (2004)
9. Hoot, S.B., Palmer, J.D.: Structural rearrangements, including parallel inversions, within the chloroplast genome of Anemone and related genera. J. Mol. Evol. 38, 274-281 (1994)
10. Kaplan, H., Verbin, E.: Efficient data structures and a new randomized approach for sorting signed permutations by reversals. In: Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching (CPM'03), pp. 170-185. Morelia, Michocan, Mexico, 25-27 Jun (2003)
11. Lin, G.H., Xue, G.: Signed genome rearrangements by reversals and transpositions: models and approximations. Theor. Comput. Sci.259,513-531 (2001)
12. Palmer, J.D., Herbon, L.A.: Tricircular mitochondrial genomes of Brassica and Raphanus: reversal of repeat configurations by inversion. Nucleic Acids Res. 14,9755-9764 (1986)