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

При попытке определить эволюционное расстояние между двумя организмами при помощи данных о геноме биологи могут захотеть реконструировать последовательность эволюционных событий, в результате которых один геном был преобразован в другой. Одним из наиболее многообещающих способов выполнения такого филогенетического исследования является сравнение порядка появления идентичных (например, ортологичных) генов в двух разных геномах [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>.