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

Перейти к навигации Перейти к поиску
Строка 56: Строка 56:


== Применение ==
== Применение ==
При попытке определить эволюционное расстояние между двумя организмами при помощи данных о геноме биологи могут захотеть реконструировать последовательность эволюционных событий, в результате которых один геном был преобразован в другой. Одним из наиболее многообещающих способов выполнения такого филогенетического исследования является сравнение порядка появления идентичных (например, ортологичных) генов в двух разных геномах [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)
Источник — http://pco.iis.nsk.su/wega/index.php/Сортировка_при_помощи_транспозиций_и_обращений_(коэффициент_аппроксимации_1,5)