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

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