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

   

== Ссылки на код ==

Теслер из группы Певзнера выложил в Интернет реализацию мультихромосомного обобщения алгоритма Каплана, Шамира и Тарьяна [10], названную им GRIMM, что означает «Genome Rearrangements In Man and Mouse» (Перестройка генома человека и мыши).

Название GRAPPA расшифровывается как "Genome Rearrangements Analysis under Parsimony and other Phylogenetic Algorithms" (Анализ перестройки генома при помощи подхода на базе максимальной экономичности и других филогенетических алгоритмов). Алгоритм включает вычисление расстояний и способен находить все безопасные обращения за один шаг. Он был разработано группой Морета.

Апплет, написанный Мантином, реализует алгоритм Каплана, Шамира и Тарьяна [10].

Созданная Дикманном программа выполняет поиск сценария обращений с дополнительными ограничениями для подписанных перестановок, реализуя алгоритм Танье и Сагот [17].

Программа, разработанная Марилией Брагой для обработки перестановок и, в частности, для сортировки подписанных перестановок при помощи обращений, а также для выдачи сжатого представления всех оптимальных последовательностей перестановок, является реализацией алгоритма из работы [6].

== Открытые вопросы ==

• Уменьшение сложности ниже значения <math>O(n^{3/2})</math>. Этого можно добиться за счет применения более рациональной структуры данных или изменения принципа работы алгоритма, в силу чего отпадет необходимость применения на каждом этапе обращения сортировки для получения возможности вычисления следующих.