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

''Подписанная перестановка'' <math>\pi</math> размера n представляет собой перестановку над множеством {-n, ... , -1, 1, ..., n}, где <math>\pi_{- i} = - \pi_i</math> для всех i.

Пусть <math>\rho_1, ..., \rho_k</math> – последовательность обращений. Она ''сортирует'' перестановку <math>\pi</math>, если <math>\pi \cdot \rho_1 \cdot \cdot \cdot \rho_k = Id</math>, где Id = (1, ..., n) – тождественная перестановка. Длина кратчайшей последовательности обращений при сортировке <math>\pi</math> называется ''расстоянием обращения'' <math>\pi</math> и обозначается как <math>d(\pi)</math>.

Если вычисление <math>d(\pi)</math> производится за линейное время [2] (см. статью «[[Сортировка подписанных перестановок при помощи обращений (расстояние обращения)|Расстояние обращений]]»), то вычисление последовательности размера <math>d(\pi)</math>, выполняющей сортировку <math>\pi</math>, является более сложным, и для него пока не разработано линейных алгоритмов. Наилучшие параметры сложности на данный момент демонстрирует решение Танье и Сагот [17], которое было теоретически улучшено в работах Танье, Бержерон и Сагот [18] и Хана [8].

Вторая часть представляет собой «узкое место» всей процедуры. На этот момент неориентированных компонентов уже не осталось, расстояние составляет <math>d(\pi) = n + 1 - c(\pi)</math>, так что безопасным обращением будет являться такое, которое увеличивает <math>c(\pi)</math> и не создает неориентированных компонентов (это увеличило бы <math>t(\pi)</math>).

Это позволяет строить последовательность ориентированных обращений вместо безопасных обращений и увеличивать их размер за счет добавления обращений внутрь последовательности, а не в ее конец, получая последовательность сортировки.

'''Пространство оптимальных решений'''

Основной мотивацией и основной областью применения для этих исследований является вычислительная биология. Подписанные перестановки оказались адекватным способом моделирования относительного положения и ориентации гомологичных участков ДНК двух видов. Обобщение этой задачи до мультихромосомных моделей было разработано и применено для геномов млекопитающих [15], свидетельствуя в пользу эволюционной модели, в которой обращения встречаются не случайным образом.

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

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

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

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

 

 

 

 

Алгоритм Танье, Бержерон и Сагот [18] был реализован в его квадратичной версии (без конкретной структуры данных, что, вероятно, имеет смысл только для перестановок очень большого размера) Дикманном (http://biomserv.univ-lyon1.fr/~tannier/PSbR/), однако не сообщалось ни о реализации структур данных, ни об экспериментальных данных по сложности.

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