4430
правок
Irina (обсуждение | вклад) м (→Ссылки на код) |
Irina (обсуждение | вклад) |
||
(не показано 8 промежуточных версий этого же участника) | |||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
'' | ''Перестановка со знаками'' <math>\pi</math> размера n представляет собой перестановку над множеством {-n, ... , -1, 1, ..., n}, где <math>\pi_{- i} = - \pi_i</math> для всех i. | ||
Строка 11: | Строка 11: | ||
Пусть <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>\rho_1, ..., \rho_k</math> – последовательность обращений. Она ''сортирует'' перестановку <math>\pi</math>, если <math>\pi \cdot \rho_1 \cdot \cdot \cdot \rho_k = Id</math>, где <math>Id = (1, ..., n)</math> – тождественная перестановка. Длина кратчайшей последовательности обращений, сортирующей <math>\pi</math>, называется ''расстоянием обращения'' <math>\pi</math> и обозначается как <math>d(\pi)</math>. | ||
Если вычисление <math>d(\pi)</math> производится за линейное время [2] (см. статью «[[Сортировка | Если вычисление <math>d(\pi)</math> производится за линейное время [2] (см. статью «[[Сортировка перестановок со знаками при помощи обращений (расстояние обращения)|Расстояние обращений]]»), то вычисление последовательности размера <math>d(\pi)</math>, выполняющей сортировку <math>\pi</math>, является более сложным, и для него пока не разработано линейных алгоритмов. Наилучшие параметры сложности на данный момент демонстрирует решение Танье и Сагот [17], которое было теоретически улучшено в работах Танье, Бержерон и Сагот [18] и Хана [8]. | ||
== Основные результаты == | == Основные результаты == | ||
Строка 31: | Строка 31: | ||
Вторая часть представляет собой «узкое место» всей процедуры. На этот момент неориентированных компонентов уже не осталось, расстояние составляет <math>d(\pi) = n + 1 - c(\pi)</math>, так что безопасным обращением будет являться такое, которое увеличивает <math>c(\pi)</math> и не создает неориентированных компонентов (это увеличило бы <math>t(\pi)</math>). | Вторая часть представляет собой «узкое место» всей процедуры. На этот момент, если неориентированных компонентов уже не осталось, расстояние составляет <math>d(\pi) = n + 1 - c(\pi)</math>, так что безопасным обращением будет являться такое, которое увеличивает <math>c(\pi)</math> и не создает неориентированных компонентов (это увеличило бы <math>t(\pi)</math>). | ||
Обращение, увеличивающее <math>t(\pi)</math>, называется ''ориентированным''. Найти ориентированное обращение несложно: его определяют любые два последовательных числа в перестановке, имеющих разные знаки. Гораздо сложнее убедиться в том, что | |||
Обращение, увеличивающее <math>t(\pi)</math>, называется ''ориентированным''. Найти ориентированное обращение несложно: его определяют любые два последовательных числа в перестановке, имеющих разные знаки. Гораздо сложнее убедиться в том, что оно не увеличивает число неориентированных компонентов. | |||
Строка 39: | Строка 40: | ||
Алгоритм основан на следующей теореме, приведенной в работе [18]. Последовательность ориентированных обращений <math>\rho_1, ..., \rho_k</math> называется ''максимальной'', если не существует ориентированного обращения в <math>\pi \cdot \rho_1 \cdot \cdot \cdot \rho_k</math>. В частности, последовательность | Алгоритм основан на следующей теореме, приведенной в работе [18]. Последовательность ориентированных обращений <math>\rho_1, ..., \rho_k</math> называется ''максимальной'', если не существует ориентированного обращения в <math>\pi \cdot \rho_1 \cdot \cdot \cdot \rho_k</math>. В частности, сортирующая последовательность является максимальной, в то же время обратное неверно. | ||
'''Теорема 1. Если последовательность S является максимальной, но не является последовательностью | '''Теорема 1. Если последовательность S является максимальной, но не является сортирующей последовательностью ориентированных обращений для перестановки, то существует непустая последовательность S' ориентированных обращений, такая, что S может быть разбита на две части <math>S = S_1, S_2</math>, и <math>S_1, S', S_2</math> является последовательностью ориентированных обращений.''' | ||
Это позволяет строить последовательности ориентированных обращений вместо безопасных обращений и увеличивать их размер за счет добавления обращений внутрь последовательности, а не в ее конец, получая последовательность | Это позволяет строить последовательности ориентированных обращений вместо безопасных обращений и увеличивать их размер за счет добавления обращений внутрь последовательности, а не в ее конец, получая в итоге сортирующую последовательность. | ||
Строка 57: | Строка 58: | ||
'''Пространство оптимальных решений''' | '''Пространство всех оптимальных решений''' | ||
Почти все исследования последовательностей сортировки для обращений были ориентированы на выдачу строго одной последовательности, хотя было замечено, что нередко этих последовательностей оказывается много (даже для <math>n \le 10</math> их может быть несколько миллионов). Лишь несколько исследований попытались восполнить этот пробел. | Почти все исследования последовательностей сортировки для обращений были ориентированы на выдачу строго одной последовательности, хотя было замечено, что нередко этих последовательностей оказывается много (даже для <math>n \le 10</math> их может быть несколько миллионов). Лишь несколько исследований попытались восполнить этот пробел. | ||
Строка 65: | Строка 66: | ||
== Применение == | == Применение == | ||
Основной мотивацией и основной областью применения для этих исследований является вычислительная биология. | Основной мотивацией и основной областью применения для этих исследований является вычислительная биология. Перестановки со знаками оказались адекватным способом моделирования относительного положения и ориентации гомологичных участков ДНК двух особей. Обобщение этой задачи до мультихромосомных моделей было разработано и применено для геномов млекопитающих [15], свидетельствуя в пользу эволюционной модели, в которой обращения встречаются не случайным образом. | ||
Строка 71: | Строка 72: | ||
Обобщения этого подхода для сравнения более чем двух геномов широко рассматривались в литературе и применялись для реконструкции эволюционных событий и организации геномов общих предков биологических видов, а также для вывода ортологичных генов на основе их позиций; они основаны на эвристических принципах, базирующихся на теории сортировки | Обобщения этого подхода для сравнения более чем двух геномов широко рассматривались в литературе и применялись для реконструкции эволюционных событий и организации геномов общих предков биологических видов, а также для вывода ортологичных генов на основе их позиций; они основаны на эвристических принципах, базирующихся на теории сортировки перестановок со знаками при помощи обращений [12, 13]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Строка 90: | Строка 91: | ||
• http://www.cs.unm.edu/~moret/GRAPPA/ | • http://www.cs.unm.edu/~moret/GRAPPA/ | ||
Название GRAPPA расшифровывается как «Genome Rearrangements Analysis under Parsimony and other Phylogenetic Algorithms» (Анализ перестройки генома при помощи подхода на базе максимальной экономичности и других филогенетических алгоритмов). Алгоритм включает вычисление расстояний и способен находить все безопасные обращения за один шаг. Он был | Название GRAPPA расшифровывается как «Genome Rearrangements Analysis under Parsimony and other Phylogenetic Algorithms» (Анализ перестройки генома при помощи подхода на базе максимальной экономичности и других филогенетических алгоритмов). Алгоритм включает вычисление расстояний и способен находить все безопасные обращения за один шаг. Он был разработан группой Морета. | ||
• http://www.math.tau.ac.il/~rshamir/GR/ | • http://www.math.tau.ac.il/~rshamir/GR/ | ||
Строка 98: | Строка 99: | ||
• http://biomserv.univ-lyon1.fr/~tannier/PSbR/ | • http://biomserv.univ-lyon1.fr/~tannier/PSbR/ | ||
Созданная Дикманном программа выполняет поиск сценария обращений с дополнительными ограничениями для | Созданная Дикманном программа выполняет поиск сценария обращений с дополнительными ограничениями для перестановок со знаками, реализуя алгоритм Танье и Сагот [17]. | ||
• http://www.geocities.com/mdvbraga/baobabLuna.html | • http://www.geocities.com/mdvbraga/baobabLuna.html | ||
Программа, разработанная Марилией Брагой для обработки перестановок и, в частности, для сортировки | Программа, разработанная Марилией Брагой для обработки перестановок и, в частности, для сортировки перестановок со знаками при помощи обращений, а также для выдачи сжатого представления всех оптимальных последовательностей перестановок, является реализацией алгоритма из работы [6]. | ||
== См. также == | == См. также == | ||
[[Сортировка | [[Сортировка перестановок со знаками при помощи обращений (расстояние обращения)]] | ||
== Литература == | == Литература == |
правок