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

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

Бафна и Певзнер представили граф циклов для перестановки [3], ставший базовой структурой данных для вычисления расстояния инверсии. После этого Хамменхалли и Певзнер разработали базовую теорию для выражения расстояния инверсии в легко вычисляемых терминах (количество точек разрывов минус количество циклов плюс количество препятствий плюс поправочный коэффициент для укреплений [3, 15] – укрепления и препятствия можно легко обнаружить при помощи анализа связных компонентов). Они также предложили первый алгоритм с полиномиальным временем выполнения для сортировки подписанных перестановок при помощи обращений [9] и O(n4)-реализацию этого алгоритма, которая в случае ограничения вычисления только расстоянием выполняется за квадратичное время. Этот алгоритм требует вычисления связных компонент графа перекрытий, что является узким местом при вычислении расстояний. Впоследствии Берман и Хамменхалли применили некоторые комбинаторные свойства графа циклов, получив алгоритм с временем выполнения O(na(n)) для вычисления связных компонент и реализацию алгоритма сортировки с временем выполнения O(n2a(n)) [ ], где a – обратная функция Аккермана. (Более поздний алгоритм Каплана, Шамира и Тарьяна (Kaplan-Shamir-Tarjan, KST) [10] сокращает время выполнения, необходимое для вычисления кратчайшей последовательности инверсий, но использует тот же подход для вычисления длины этой последовательности).

Данный линейный алгоритм получил широкое распространении (в течение первых нескольких лет после публикации на него было сделано почти 200 ссылок). Среди примеров использования можно упомянуть обработку многохромосомных перестановок генома [16], сравнение геномов [5], разбор вторичной структуры РНК [ ] и филогенетическое исследование вируса ВИЧ-1 [2].

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