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

В данной статье будут описаны алгоритмы для поиска минимального количества шагов, необходимого для сортировки подписанных перестановок (также используются названия «расстояние инверсии» и «расстояние обращения»). Это практическая задача, встречающаяся, к примеру, в вычислительной биологии.

Поиск расстояния инверсии представляет собой сложную вычислительную задачу, активно изучавшуюся в последние годы [1, 4, 6, 7, 8, 9, 10]. Задача поиска расстояния инверсии между неподписанными перестановками является NP-трудной [7], в то же время для подписанных перестановок она может быть решена за линейное время [1].

Бадер и др. [1] представили первый алгоритм с линейным временем выполнения в худшем случае для вычисления расстояния обращения; это простой и практичный алгоритм, работающий быстрее по сравнению с ранее использовавшимися методами. Ключевым новшеством является новая техника вычисления связных компонент графа перекрытий, использующая только стек, что позволило создать простой алгоритм с линейный временем выполнения для вычисления расстояния инверсии между двумя подписанными перестановками. Бадер и коллеги представили обширные экспериментальные свидетельства эффективности данного алгоритма не только в теории, но и на практике. Они реализовали его наряду с алгоритмом Бермана и Ханненхалли, используя передовые принципы разработки алгоритмов, гарантирующие максимально возможную эффективность обеих реализаций, и сравнили время выполнения на широком спектре экземпляров данных, сгенерированных посредством имитационной эволюции.

Бафна и Певзнер представили граф циклов для перестановки [3], ставший базовой структурой данных для вычисления расстояния инверсии. После этого Ханненхалли и Певзнер разработали базовую теорию для выражения расстояния инверсии в легко вычисляемых терминах (количество точек разрывов минус количество циклов плюс количество "препятствий" плюс поправочный коэффициент для "укреплений" [3, 15] – укрепления и препятствия можно легко обнаружить при помощи анализа связных компонентов). Они также предложили первый алгоритм с полиномиальным временем выполнения для сортировки подписанных перестановок при помощи обращений [9] и <math>O(n^4)</math>-реализацию этого алгоритма, которая в случае ограничения вычисления только расстоянием выполняется за квадратичное время. Этот алгоритм требует вычисления связных компонент графа перекрытий, что является узким местом при вычислении расстояний. Впоследствии Берман и Ханненхалли применили некоторые комбинаторные свойства графа циклов, получив алгоритм с временем выполнения <math>O(n \alpha(n))</math> для вычисления связных компонент и реализацию алгоритма сортировки с временем выполнения <math>O(n^2 \alpha(n))</math> [6], где <math>\alpha</math> – обратная функция Аккермана. (Более поздний алгоритм Каплана, Шамира и Тарьяна (Kaplan-Shamir-Tarjan, KST) [10] сокращает время выполнения, необходимое для вычисления кратчайшей последовательности инверсий, но использует тот же подход для вычисления длины этой последовательности).

Ни один из алгоритмов, строящих граф перекрытий, не может выполняться за линейное время, поскольку этот граф может иметь квадратичный размер. Ключевое новшество Бадера заключается в построении ''леса перекрытий'', такого, что две вершины принадлежат к одному и тому же дереву леса точно в том случае, когда они принадлежат к одной и той же связной компоненте графа перекрытий. Лес перекрытий (композиция его деревьев уникальна, но их структура произвольна) содержит ровно одно дерево для каждой связной компоненты графа перекрытий и в силу этого имеет линейный размер. Шаг алгоритма с линейным временем выполнения, вычисляющий связные компоненты, сканирует перестановку дважды. Первое сканирование строит тривиальный лес, в котором каждая вершина является своим собственным деревом и помечена началом своего цикла. Второй проход выполняет итеративное уточнение этого первичного леса при помощи добавления ребер и слияния таким образом деревьев друг с другом; однако, в отличие от Union-Find, этот алгоритм не пытается сохранить определенные параметры формы деревьев. Данный шаг является ключевым элементом алгоритма Бадера с линейным временем выполнения для вычисления расстояния обращения между подписанными перестановками.

Некоторые организмы имеют одну хромосому либо содержат однохромосомные органеллы (такие как митохондрии или хлоропласты), эволюция которых в значительной степени независима от эволюции ядерного генома. Если имеется конкретная нить одиночной хромосомы, линейная или кольцевая, мы можем вывести упорядочение и направленность генов, представив таким образом каждую хромосому в виде упорядочения ориентированных генов. Во многих случаях эволюционный процесс, действующий над подобными однохромосомными организмами, состоит главным образом из инверсий фрагментов хромосомы; это открытие позволило многим биологам реконструировать филогении на основе порядка генов, используя в качестве меры эволюционного расстояния между двумя геномами расстояние инверсии, т. е. наименьшее количество инверсий, необходимое для преобразования одной подписанной перестановки в другую [11, 12, 14].

Реализация алгоритма с линейным временем выполнения в виде программы на C доступна на странице http://www.cc.gatech.edu/~bader. Также доступны две другие реализации, разработанные для вычисления кратчайшей последовательности инверсий наряду с длиной. Одна из них принадлежит Ханненхалли и реализует его первый алгоритм [9], выполняющийся за квадратичное время при вычислении расстояний; другая представляет собой Java-апплет, написанный Мантином (http://www.math.tau.ac.il/~rshamir/GR/) и реализующий алгоритм KST [10], но использующий явное представление графа перекрытий и в силу этого также имеющий квадратичное время выполнения. Реализация Ханненхалли работает очень медленно; в ней применен исходный метод Ханненхалли и Певзнера, а не более быстрый – Бермана и Ханненхалли. Апплет KST также оказывается очень медленным из-за явного построения графа перекрытий.

* [[Сортировка подписанных перестановок при помощи обращений (последовательность обращений)]]