Сортировка перестановок со знаками при помощи обращений (расстояние обращения)
Ключевые слова и синонимы
Сортировка при помощи обращений; расстояние инверсии; расстояние обращения
Постановка задачи
В данной статье будут описаны алгоритмы для поиска минимального количества шагов, необходимого для сортировки перестановок со знаками (также используются названия «расстояние инверсии» и «расстояние обращения»). Это практическая задача, встречающаяся, к примеру, в вычислительной биологии.
Поиск расстояния инверсии представляет собой сложную вычислительную задачу, активно изучавшуюся в последние годы [1, 4, 6, 7, 8, 9, 10]. Задача поиска расстояния инверсии между перестановками без знаков является NP-трудной [7], в то же время для перестановок со знаками она может быть решена за линейное время [1].
Основные результаты
Бадер и др. [1] представили первый алгоритм с линейным временем выполнения в худшем случае для вычисления расстояния обращения; это простой и практичный алгоритм, работающий быстрее по сравнению с ранее использовавшимися методами. Ключевым новшеством является новая техника вычисления связных компонент графа перекрытий, использующая только стек, что позволило создать простой алгоритм с линейный временем выполнения для вычисления расстояния инверсии между двумя перестановками со знаками. Бадер и коллеги представили обширные экспериментальные свидетельства эффективности данного алгоритма не только в теории, но и на практике. Они реализовали его наряду с алгоритмом Бермана и Ханненхалли, используя передовые принципы разработки алгоритмов, гарантирующие максимально возможную эффективность обеих реализаций, и сравнили время выполнения на широком спектре экземпляров данных, сгенерированных посредством имитационной эволюции.
Бафна и Певзнер представили граф циклов для перестановки [3], ставший базовой структурой данных для вычисления расстояния инверсии. После этого Ханненхалли и Певзнер разработали базовую теорию для выражения расстояния инверсии в легко вычисляемых терминах (количество точек разрывов минус количество циклов плюс количество "препятствий" плюс поправочный коэффициент для "укреплений" [3, 15] – укрепления и препятствия можно легко обнаружить при помощи анализа связных компонентов). Они также предложили первый алгоритм с полиномиальным временем выполнения для сортировки перестановок со знаками при помощи обращений [9] и [math]\displaystyle{ O(n^4) }[/math]-реализацию этого алгоритма, которая в случае ограничения вычисления только расстоянием выполняется за квадратичное время. Этот алгоритм требует вычисления связных компонент графа перекрытий, что является узким местом при вычислении расстояний. Впоследствии Берман и Ханненхалли применили некоторые комбинаторные свойства графа циклов, получив алгоритм с временем выполнения [math]\displaystyle{ O(n \alpha(n)) }[/math] для вычисления связных компонент и реализацию алгоритма сортировки с временем выполнения [math]\displaystyle{ O(n^2 \alpha(n)) }[/math] [6], где [math]\displaystyle{ \alpha }[/math] – обратная функция Аккермана. (Более поздний алгоритм Каплана, Шамира и Тарьяна (Kaplan-Shamir-Tarjan, KST) [10] сокращает время выполнения, необходимое для вычисления кратчайшей последовательности инверсий, но использует тот же подход для вычисления длины этой последовательности).
Ни один из алгоритмов, строящих граф перекрытий, не может выполняться за линейное время, поскольку этот граф может иметь квадратичный размер. Ключевое новшество Бадера заключается в построении леса перекрытий, такого, что две вершины принадлежат к одному и тому же дереву леса точно в том случае, когда они принадлежат к одной и той же связной компоненте графа перекрытий. Лес перекрытий (композиция его деревьев уникальна, но их структура произвольна) содержит ровно одно дерево для каждой связной компоненты графа перекрытий и в силу этого имеет линейный размер. Шаг алгоритма с линейным временем выполнения, вычисляющий связные компоненты, сканирует перестановку дважды. Первое сканирование строит тривиальный лес, в котором каждая вершина является своим собственным деревом и помечена началом своего цикла. Второй проход выполняет итеративное уточнение этого первичного леса при помощи добавления ребер и слияния таким образом деревьев друг с другом; однако, в отличие от Union-Find, этот алгоритм не пытается сохранить определенные параметры формы деревьев. Данный шаг является ключевым элементом алгоритма Бадера с линейным временем выполнения для вычисления расстояния обращения между перестановками со знаками.
Применение
Некоторые организмы имеют одну хромосому либо содержат однохромосомные органеллы (такие как митохондрии или хлоропласты), эволюция которых в значительной степени независима от эволюции ядерного генома. Если имеется конкретная нить одиночной хромосомы, линейная или кольцевая, мы можем вывести упорядочение и направленность генов, представив таким образом каждую хромосому в виде упорядочения ориентированных генов. Во многих случаях эволюционный процесс, действующий над подобными однохромосомными организмами, состоит главным образом из инверсий фрагментов хромосомы; это открытие позволило многим биологам реконструировать филогении на основе порядка генов, используя в качестве меры эволюционного расстояния между двумя геномами расстояние инверсии, т. е. наименьшее количество инверсий, необходимое для преобразования одной перестановки со знаками в другую [11, 12, 14].
Данный линейный алгоритм получил широкое распространение (в течение первых нескольких лет после публикации на него было сделано почти 200 ссылок). Среди примеров использования можно упомянуть обработку многохромосомных перестроек генома [16], сравнение геномов [5], разбор вторичной структуры РНК [13] и филогенетическое исследование вируса ВИЧ-1 [2].
Открытые вопросы
Необходима разработка эффективных алгоритмов для вычисления минимальных расстояний для инверсий с весами, транспозиций и инвертированных транспозиций.
Экспериментальные результаты
Экспериментальные результаты Бадера и др. приведены в работе [1].
Ссылка на код
Реализация алгоритма с линейным временем выполнения в виде программы на C доступна на странице http://www.cc.gatech.edu/~bader. Также доступны две другие, менее эффективные реализации, разработанные для вычисления кратчайшей последовательности инверсий наряду с длиной. Одна из них принадлежит Ханненхалли и реализует его первый алгоритм [9], выполняющийся за квадратичное время при вычислении расстояний; другая представляет собой Java-апплет, написанный Мантином (http://www.math.tau.ac.il/~rshamir/GR/) и реализующий алгоритм KST [10], но использующий явное представление графа перекрытий и в силу этого также имеющий квадратичное время выполнения. Реализация Ханненхалли работает очень медленно; в ней применен исходный метод Ханненхалли и Певзнера, а не более быстрый – Бермана и Ханненхалли. Апплет KST также оказывается очень медленным из-за явного построения графа перекрытий.
См. также
Фактические последовательности сортировок см. в статье
Литература
1. Bader, D.A., Moret, B.M.E., Yan, M.: A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. J. Comput. Biol. 8(5), 483-491 (2001) An earlier version of this work appeared In: the Proc. 7th Int'l Workshop on Algorithms and Data Structures (WADS 2001)
2. Badimo, A., Bergheim, A., Hazelhurst, S., Papathanasopolous, M., Morris, L.: The stability of phylogenetic tree construction of the HIV-1 virus using genome-ordering data versus env gene data. In: Proc. ACM Ann. Research Conf. of the South African institute of computer scientists and information technologists on enablement through technology (SAICSIT 2003), vol. 47, pp. 231-240, Fourways, ACM, South Africa, September 2003
3. Bafna, V., Pevzner, P.A.: Genome rearrangements and sorting by reversals. In: Proc. 34th Ann. IEEE Symp. Foundations of Computer Science (FOCS93), pp. 148-157. IEEE Press (1993)
4. Bafna, V., Pevzner, P.A.: Genome rearrangements and sorting by reversals. SIAM J. Comput. 25, 272-289 (1996)
5. Bergeron, A., Stoye, J.: On the similarity of sets of permutations and its applications to genome comparison. J. Comput. Biol. 13(7),1340-1354(2006)
6. Berman, P., Hannenhalli, S.: Fast sorting by reversal. In: Hirschberg, D.S., Myers, E.W. (eds.) Proc. 7th Ann. Symp. Combinatorial Pattern Matching (CPM96). Lecture Notes in Computer Science, vol. 1075, pp. 168-185. Laguna Beach, CA, June 1996. Springer (1996)
7. Caprara, A.: Sorting by reversals is difficult. In: Proc. 1st Conf. Computational Molecular Biology (RECOMB97), pp. 75-83. ACM, Santa Fe, NM (1997)
8. Caprara, A.: Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J. Discret. Math. 12(1), 91 -110 (1999)
9. Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). In: Proc. 27th Ann. Symp. Theory of Computing (STOC95), pp. 178-189. ACM, Las Vegas, NV (1995)
10. Kaplan, H., Shamir, R., Tarjan, R.E.: A faster and simpler algorithm for sorting signed permutations by reversals. SIAM J. Comput. 29(3), 880-892 (1999) First appeared In: Proc.8th Ann. Symp. Discrete Algorithms (SODA97), pp. 344-351. ACM Press, New Orleans, LA
11. Olmstead, R.G., Palmer, J.D.: Chloroplast DNA systematics: a review of methods and data analysis. Am. J. Bot. 81, 1205-1224 (1994)
12. Palmer, J.D.: Chloroplast and mitochondrial genome evolution in land plants. In: Herrmann, R. (ed.) Cell Organelles, pp. 99-133. Springer, Vienna (1992)
13. Rastegari, B., Condon, A.: Linear time algorithm for parsing RNA secondary structure. In: Casadio, R., Myers, E.: (eds.) Proc. 5th Workshop Algs. in Bioinformatics (WABI'05). Lecture Notes in Computer Science, vol. 3692, pp. 341-352. Springer, Mallorca, Spain (2005)
14. Raubeson, L.A., Jansen, R.K.: Chloroplast DNA evidence on the ancient evolutionary split in vascular land plants. Science 255, 1697-1699(1992)
15. Setubal, J.C., Meidanis, J.: Introduction to Computational Molecular Biology. PWS, Boston, MA (1997)
16. Tesler, G.: Efficient algorithms for multichromosomal genome rearrangements. J. Comput. Syst. Sci. 63(5), 587-609 (2002)