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

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

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

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

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

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

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

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