Сортировка перестановок со знаками при помощи обращений (последовательность обращений): различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 17 промежуточных версий этого же участника) | |||
| Строка 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]. | ||
== Основные результаты == | == Основные результаты == | ||
Вспомним, что существует линейный алгоритм для вычисления расстояния обращений по формуле <math>d(\pi) = n + 1 - c(\pi) + t(\pi)</math> (нотация из работы [4]), где <math>c(\pi)</math> – количество циклов в графе разрывов, а <math>t(\pi)</math> вычисляется из неориентированных компонентов перестановки, см. статью «Расстояние обращений»). После расчета этого показателя тривиальный алгоритм вычисляет последовательность размера <math>d(\pi)</math>: на очередном шаге алгоритма пробовать каждое возможное обращение | Вспомним, что существует линейный алгоритм для вычисления расстояния обращений по формуле <math>d(\pi) = n + 1 - c(\pi) + t(\pi)</math> (нотация из работы [4]), где <math>c(\pi)</math> – количество циклов в графе разрывов, а <math>t(\pi)</math> вычисляется из неориентированных компонентов перестановки, см. статью «Расстояние обращений»). После расчета этого показателя тривиальный алгоритм вычисляет последовательность размера <math>d(\pi)</math>: на очередном шаге алгоритма пробовать каждое возможное обращение <math>\rho</math>, до тех пор, пока не будет найдено такое, что <math>d(\pi \cdot \rho) = d(\pi) - 1</math>. Такое обращение называется ''безопасным''. Этот подход требует O(n) вычислений для каждого возможного обращения (которых может быть не более не более <math>(n + 1)(n + 2)/2 = O(n^2))</math>; в результате итераций для поиска последовательности получаем алгоритм со сложностью <math>O(n^4)</math>. | ||
| Строка 25: | Строка 25: | ||
'''Сценарий обращений''' | '''Сценарий обращений''' | ||
Все опубликованные решения для вычисления последовательности сортировок делятся на две части, следуя разбиению формулы расстояния на два параметра: | Все опубликованные решения для вычисления последовательности сортировок делятся на две части, следуя разбиению формулы расстояния на два параметра: первая часть решений вычисляет последовательность обращений таким образом, что полученная перестановка не имеет неориентированных компонентов; вторая часть сортирует все ориентированные компоненты. | ||
| Строка 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>, называется ''ориентированным''. Найти ориентированное обращение несложно: его определяют любые два последовательных числа в перестановке, имеющих разные знаки. Гораздо сложнее убедиться в том, что оно не увеличивает число неориентированных компонентов. | |||
Квадратичные алгоритмы, разработанные, с одной стороны, Берманом и Ханненхалли [5], а с другой – Капланом, Шамиром и Тарьяном [10], основаны на распознавании безопасных обращений за линейное время. На данный момент не известно улучшенных алгоритмов распознавания безопасных обращений, и представляется, что нижняя граница уже была достигнута, что было замечено Озери-Флато и Шамир в работе [14], в которой они сообщили, что «главный вопрос в исследованиях перестановок геномов заключается в том, можно ли получить субквадратичный алгоритм для сортировки при помощи обращений». Этот алгоритм был получен Танье и Сагот [17], которые доказали, что распознавание безопасного обращения на каждом этапе не является необходимым; требуется только распознавание ориентированных обращений. | |||
Алгоритм основан на следующей теореме, приведенной в работе [18]. Последовательность ориентированных обращений <math>\rho_1, ..., \rho_k</math> называется ''максимальной'', если не существует ориентированного обращения в <math>\pi \cdot \rho_1 \cdot \cdot \cdot \rho_k</math>. В частности, сортирующая последовательность является максимальной, в то же время обратное неверно. | |||
'''Теорема 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], свидетельствуя в пользу эволюционной модели, в которой обращения встречаются не случайным образом. | |||
Аджана и др. [1] применили случайные исследования в пространстве решений для проверки гипотезы, заключавшейся в том, что у бактерий обращения встречаются главным образом вблизи точек начала или окончания репликации. | |||
Обобщения этого подхода для сравнения более чем двух геномов широко рассматривались в литературе и применялись для реконструкции эволюционных событий и организации геномов общих предков биологических видов, а также для вывода ортологичных генов на основе их позиций; они основаны на эвристических принципах, базирующихся на теории сортировки перестановок со знаками при помощи обращений [12, 13]. | |||
== Открытые вопросы == | |||
• Уменьшение сложности ниже значения <math>O(n^{3/2})</math>. Этого можно добиться за счет применения более рациональной структуры данных или изменения принципа работы алгоритма, в силу чего отпадет необходимость применения на каждом этапе обращения сортировки для получения возможности вычисления следующих. | |||
• Эффективное представление и перечисление всего множества решений (определенные шаги в этом направлении были сделаны в работах [3, 6]). | |||
• Поиск среди всех решений таких, которые удовлетворяли бы некоторым биологическим ограничениям – таким как сохранение некоторой общей группы генов или приоритетность небольших инверсий (некоторые достижения представлены в работе [7]). | |||
== Экспериментальные результаты == | |||
Алгоритм Танье, Бержерон и Сагот [18] был реализован в его квадратичной версии (без конкретной структуры данных, что, вероятно, имеет смысл только для перестановок очень большого размера) Дикманном (http://biomserv.univ-lyon1.fr/~tannier/PSbR/), однако не сообщалось ни о реализации структур данных, ни об экспериментальных данных по сложности. | |||
== Ссылки на код == | |||
• http://www.cse.ucsd.edu/groups/bioinformatics/GRIMM/ | |||
Теслер из группы Певзнера выложил в Интернет реализацию мультихромосомного обобщения алгоритма Каплана, Шамира и Тарьяна [10], названную им GRIMM, что означает «Genome Rearrangements In Man and Mouse» (Перестройка генома человека и мыши). | |||
• http://www.cs.unm.edu/~moret/GRAPPA/ | |||
Название GRAPPA расшифровывается как «Genome Rearrangements Analysis under Parsimony and other Phylogenetic Algorithms» (Анализ перестройки генома при помощи подхода на базе максимальной экономичности и других филогенетических алгоритмов). Алгоритм включает вычисление расстояний и способен находить все безопасные обращения за один шаг. Он был разработан группой Морета. | |||
• http://www.math.tau.ac.il/~rshamir/GR/ | |||
Апплет, написанный Мантином, реализует алгоритм Каплана, Шамира и Тарьяна [10]. | |||
• http://biomserv.univ-lyon1.fr/~tannier/PSbR/ | |||
Созданная Дикманном программа выполняет поиск сценария обращений с дополнительными ограничениями для перестановок со знаками, реализуя алгоритм Танье и Сагот [17]. | |||
• http://www.geocities.com/mdvbraga/baobabLuna.html | |||
Программа, разработанная Марилией Брагой для обработки перестановок и, в частности, для сортировки перестановок со знаками при помощи обращений, а также для выдачи сжатого представления всех оптимальных последовательностей перестановок, является реализацией алгоритма из работы [6]. | |||
== См. также == | |||
[[Сортировка перестановок со знаками при помощи обращений (расстояние обращения)]] | |||
== Литература == | |||
1. Ajana, Y., Lefebvre, J.-F.,Tillier, E., El-Mabrouk, N.: Exploring the Set of All Minimal Sequences of Reversals - An Application to Test the Replication-Directed Reversal Hypothesis, Proceedings of the Second Workshop on Algorithms in Bioinformatics. Lecture Notes in Computer Science, vol. 2452, pp. 300-315.Springer, Berlin (2002) | |||
2. Bader, D.A., Moret, B.M.E., Yan, M.: A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study. J. Comput. Biol. 8(5), 483-491 (2001) | |||
3. Bergeron, A., Chauve, C., Hartman, T., St-Onge, K.: On the properties of sequences of reversals that sort a signed permutation. Proceedings of JOBIM'02,99-108 (2002) | |||
4. Bergeron, A., Mixtacki, J., Stoye, J.:The inversion distance problem. In: Gascuel, O. (ed.) Mathematics of evolution and phylogeny. Oxford University Press, USA (2005) | |||
5. Berman, P., Hannenhalli, S.: Fast Sorting by Reversal, proceedings of CPM '96. Lecture notes in computer science 1075,168-185(1996) | |||
6. Braga, M.D.V., Sagot, M.F., Scornavacca, C., Tannier, E.: The Solution Space of Sorting by Reversals. In: Proceedings of IS-BRA'07. Lect. Notes Comp. Sci. 4463,293-304 (2007) | |||
7. Diekmann, Y., Sagot, M.F., Tannier, E.: Evolution under Reversals: Parsimony and Conversation of Common Intervals. IEEE/ACMTransactions in Computational Biology and Bioinformatics, 4, 301-309,1075 (2007) | |||
8. Han, Y.: Improving the Efficiency of Sorting by Reversals, Proceedings of The 2006 International Conference on Bioinformatics and Computational Biology. Las Vegas, Nevada, USA (2006) | |||
9. Hannenhalli, S., Pevzner, P.: Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). J. ACM 46,1 -27 (1999) | |||
10. Kaplan, H., Shamir, R., Tarjan, R.E.: Faster and simpler algorithm for sorting signed permutations by reversals. SIAM J. Comput. 29,880-892(1999) | |||
11. Kaplan, H., Verbin, E.: Efficient data structures and a new randomized approach for sorting signed permutations by reversals. In: Proceedings of CPM'03. Lecture Notes in Computer Science 2676,170-185 | |||
12. Moret, B.M.E.,Tang, J.,Warnow,T.: Reconstructing phylogenies from gene-content and gene-order data. In: Gascuel, O. (ed.) Mathematics of Evolution and Phylogeny. pp. 321-352, Oxford Univ. Press, USA (2005) | |||
13. Murphy, W., et al.: Dynamics of Mammalian Chromosome Evolution Inferred from Multispecies Comparative Maps. Science 309,613-617(2005) | |||
14. Ozery-Flato, M., Shamir, R.: Two notes on genome rearrangement. J. Bioinf. Comput. Biol. 1, 71-94 (2003) | |||
15. Pevzner, P., Tesler, G.: Human and mouse genomic sequences reveal extensive breakpoint reuse in mammalian evolution. PNAS 100,7672-7677 (2003) | |||
16. Siepel, A.C.: An algorithm to enumerate sorting reversals for signed permutations. J. Comput. Biol. 10, 575-597 (2003) | |||
17. Tannier, E., Sagot, M.-F.: Sorting by reversals in subquadratic time. In: Proceedings of CPM'04. Lecture Notes Comput. Sci. 3109,1-13 | |||
18. Tannier, E., Bergeron, A., Sagot, M.-F.: Advances on Sorting by Reversals. Discret. | |||
Текущая версия от 13:57, 22 марта 2019
Ключевые слова и синонимы
Сортировка при помощи инверсий
Постановка задачи
Перестановка со знаками [math]\displaystyle{ \pi }[/math] размера n представляет собой перестановку над множеством {-n, ... , -1, 1, ..., n}, где [math]\displaystyle{ \pi_{- i} = - \pi_i }[/math] для всех i.
Обращение [math]\displaystyle{ \rho = \rho_{i, j} (1 \le i \le j \le n) }[/math] представляет собой операцию, которая меняет порядок на противоположный и переключает знаки при элементах [math]\displaystyle{ \pi_i, ..., \pi_j }[/math] в перестановке [math]\displaystyle{ \pi }[/math]:
[math]\displaystyle{ \pi \cdot \rho = (\pi_1, ..., \pi_{i - 1}, - \pi_j, ..., - \pi_i, \pi_{j + 1}, ..., \pi_n) }[/math].
Пусть [math]\displaystyle{ \rho_1, ..., \rho_k }[/math] – последовательность обращений. Она сортирует перестановку [math]\displaystyle{ \pi }[/math], если [math]\displaystyle{ \pi \cdot \rho_1 \cdot \cdot \cdot \rho_k = Id }[/math], где [math]\displaystyle{ Id = (1, ..., n) }[/math] – тождественная перестановка. Длина кратчайшей последовательности обращений, сортирующей [math]\displaystyle{ \pi }[/math], называется расстоянием обращения [math]\displaystyle{ \pi }[/math] и обозначается как [math]\displaystyle{ d(\pi) }[/math].
Если вычисление [math]\displaystyle{ d(\pi) }[/math] производится за линейное время [2] (см. статью «Расстояние обращений»), то вычисление последовательности размера [math]\displaystyle{ d(\pi) }[/math], выполняющей сортировку [math]\displaystyle{ \pi }[/math], является более сложным, и для него пока не разработано линейных алгоритмов. Наилучшие параметры сложности на данный момент демонстрирует решение Танье и Сагот [17], которое было теоретически улучшено в работах Танье, Бержерон и Сагот [18] и Хана [8].
Основные результаты
Вспомним, что существует линейный алгоритм для вычисления расстояния обращений по формуле [math]\displaystyle{ d(\pi) = n + 1 - c(\pi) + t(\pi) }[/math] (нотация из работы [4]), где [math]\displaystyle{ c(\pi) }[/math] – количество циклов в графе разрывов, а [math]\displaystyle{ t(\pi) }[/math] вычисляется из неориентированных компонентов перестановки, см. статью «Расстояние обращений»). После расчета этого показателя тривиальный алгоритм вычисляет последовательность размера [math]\displaystyle{ d(\pi) }[/math]: на очередном шаге алгоритма пробовать каждое возможное обращение [math]\displaystyle{ \rho }[/math], до тех пор, пока не будет найдено такое, что [math]\displaystyle{ d(\pi \cdot \rho) = d(\pi) - 1 }[/math]. Такое обращение называется безопасным. Этот подход требует O(n) вычислений для каждого возможного обращения (которых может быть не более не более [math]\displaystyle{ (n + 1)(n + 2)/2 = O(n^2)) }[/math]; в результате итераций для поиска последовательности получаем алгоритм со сложностью [math]\displaystyle{ O(n^4) }[/math].
Первый полиномиальный алгоритм Ханненхалли и Певзнера [9] не мог обеспечить лучшую сложность, и его история началась с алгоритмических исследований процесса поиска кратчайшей последовательности обращений.
Сценарий обращений
Все опубликованные решения для вычисления последовательности сортировок делятся на две части, следуя разбиению формулы расстояния на два параметра: первая часть решений вычисляет последовательность обращений таким образом, что полученная перестановка не имеет неориентированных компонентов; вторая часть сортирует все ориентированные компоненты.
Лучшее решение для первой части предложили Каплан, Шамир и Тарьян [10]; их алгоритм выполняется за линейное время при сочетании с линейным алгоритмом вычисления расстояния [2], он основан на ранних находках Ханненхалли и Певзнера [9].
Вторая часть представляет собой «узкое место» всей процедуры. На этот момент, если неориентированных компонентов уже не осталось, расстояние составляет [math]\displaystyle{ d(\pi) = n + 1 - c(\pi) }[/math], так что безопасным обращением будет являться такое, которое увеличивает [math]\displaystyle{ c(\pi) }[/math] и не создает неориентированных компонентов (это увеличило бы [math]\displaystyle{ t(\pi) }[/math]).
Обращение, увеличивающее [math]\displaystyle{ t(\pi) }[/math], называется ориентированным. Найти ориентированное обращение несложно: его определяют любые два последовательных числа в перестановке, имеющих разные знаки. Гораздо сложнее убедиться в том, что оно не увеличивает число неориентированных компонентов.
Квадратичные алгоритмы, разработанные, с одной стороны, Берманом и Ханненхалли [5], а с другой – Капланом, Шамиром и Тарьяном [10], основаны на распознавании безопасных обращений за линейное время. На данный момент не известно улучшенных алгоритмов распознавания безопасных обращений, и представляется, что нижняя граница уже была достигнута, что было замечено Озери-Флато и Шамир в работе [14], в которой они сообщили, что «главный вопрос в исследованиях перестановок геномов заключается в том, можно ли получить субквадратичный алгоритм для сортировки при помощи обращений». Этот алгоритм был получен Танье и Сагот [17], которые доказали, что распознавание безопасного обращения на каждом этапе не является необходимым; требуется только распознавание ориентированных обращений.
Алгоритм основан на следующей теореме, приведенной в работе [18]. Последовательность ориентированных обращений [math]\displaystyle{ \rho_1, ..., \rho_k }[/math] называется максимальной, если не существует ориентированного обращения в [math]\displaystyle{ \pi \cdot \rho_1 \cdot \cdot \cdot \rho_k }[/math]. В частности, сортирующая последовательность является максимальной, в то же время обратное неверно.
Теорема 1. Если последовательность S является максимальной, но не является сортирующей последовательностью ориентированных обращений для перестановки, то существует непустая последовательность S' ориентированных обращений, такая, что S может быть разбита на две части [math]\displaystyle{ S = S_1, S_2 }[/math], и [math]\displaystyle{ S_1, S', S_2 }[/math] является последовательностью ориентированных обращений.
Это позволяет строить последовательности ориентированных обращений вместо безопасных обращений и увеличивать их размер за счет добавления обращений внутрь последовательности, а не в ее конец, получая в итоге сортирующую последовательность.
Этот алгоритм, с классической структурой данных для представления перестановок (например, в виде массива), также имеет сложность [math]\displaystyle{ O(n^2) }[/math], поскольку на каждом этапе он должен провести проверку на наличие ориентированного обращения и применить его к перестановке.
Небольшая модификация структуры данных, предложенная Капланом и Вербином [11], позволяет выбирать и применять ориентированное обращение за время [math]\displaystyle{ O(\sqrt{n \; log \; n}) }[/math]; с ее помощью алгоритм Танье-Сагот достигает временной сложности [math]\displaystyle{ O(n^{3/2} \sqrt{log \; n}) }[/math].
Недавно Хан [8] предложил еще одну структуру данных, позволяющую выбирать и применять ориентированное обращение за время [math]\displaystyle{ O(\sqrt{n}) }[/math]; аналогичная небольшая модификация, вероятно, поможет снизить сложность алгоритма в целом до [math]\displaystyle{ O(n^{3/2}) }[/math].
Пространство всех оптимальных решений
Почти все исследования последовательностей сортировки для обращений были ориентированы на выдачу строго одной последовательности, хотя было замечено, что нередко этих последовательностей оказывается много (даже для [math]\displaystyle{ n \le 10 }[/math] их может быть несколько миллионов). Лишь несколько исследований попытались восполнить этот пробел.
Алгоритм перечисления всех безопасных обращений на одном этапе был предложен и реализован Сипелем [16]. Структуру пространства оптимальных решений открыли Шаве и др. [3]; алгоритмические подходы к этой структуре исследовались в работе [6].
Применение
Основной мотивацией и основной областью применения для этих исследований является вычислительная биология. Перестановки со знаками оказались адекватным способом моделирования относительного положения и ориентации гомологичных участков ДНК двух особей. Обобщение этой задачи до мультихромосомных моделей было разработано и применено для геномов млекопитающих [15], свидетельствуя в пользу эволюционной модели, в которой обращения встречаются не случайным образом.
Аджана и др. [1] применили случайные исследования в пространстве решений для проверки гипотезы, заключавшейся в том, что у бактерий обращения встречаются главным образом вблизи точек начала или окончания репликации.
Обобщения этого подхода для сравнения более чем двух геномов широко рассматривались в литературе и применялись для реконструкции эволюционных событий и организации геномов общих предков биологических видов, а также для вывода ортологичных генов на основе их позиций; они основаны на эвристических принципах, базирующихся на теории сортировки перестановок со знаками при помощи обращений [12, 13].
Открытые вопросы
• Уменьшение сложности ниже значения [math]\displaystyle{ O(n^{3/2}) }[/math]. Этого можно добиться за счет применения более рациональной структуры данных или изменения принципа работы алгоритма, в силу чего отпадет необходимость применения на каждом этапе обращения сортировки для получения возможности вычисления следующих.
• Эффективное представление и перечисление всего множества решений (определенные шаги в этом направлении были сделаны в работах [3, 6]).
• Поиск среди всех решений таких, которые удовлетворяли бы некоторым биологическим ограничениям – таким как сохранение некоторой общей группы генов или приоритетность небольших инверсий (некоторые достижения представлены в работе [7]).
Экспериментальные результаты
Алгоритм Танье, Бержерон и Сагот [18] был реализован в его квадратичной версии (без конкретной структуры данных, что, вероятно, имеет смысл только для перестановок очень большого размера) Дикманном (http://biomserv.univ-lyon1.fr/~tannier/PSbR/), однако не сообщалось ни о реализации структур данных, ни об экспериментальных данных по сложности.
Ссылки на код
• http://www.cse.ucsd.edu/groups/bioinformatics/GRIMM/
Теслер из группы Певзнера выложил в Интернет реализацию мультихромосомного обобщения алгоритма Каплана, Шамира и Тарьяна [10], названную им GRIMM, что означает «Genome Rearrangements In Man and Mouse» (Перестройка генома человека и мыши).
• http://www.cs.unm.edu/~moret/GRAPPA/
Название GRAPPA расшифровывается как «Genome Rearrangements Analysis under Parsimony and other Phylogenetic Algorithms» (Анализ перестройки генома при помощи подхода на базе максимальной экономичности и других филогенетических алгоритмов). Алгоритм включает вычисление расстояний и способен находить все безопасные обращения за один шаг. Он был разработан группой Морета.
• http://www.math.tau.ac.il/~rshamir/GR/
Апплет, написанный Мантином, реализует алгоритм Каплана, Шамира и Тарьяна [10].
• http://biomserv.univ-lyon1.fr/~tannier/PSbR/
Созданная Дикманном программа выполняет поиск сценария обращений с дополнительными ограничениями для перестановок со знаками, реализуя алгоритм Танье и Сагот [17].
• http://www.geocities.com/mdvbraga/baobabLuna.html
Программа, разработанная Марилией Брагой для обработки перестановок и, в частности, для сортировки перестановок со знаками при помощи обращений, а также для выдачи сжатого представления всех оптимальных последовательностей перестановок, является реализацией алгоритма из работы [6].
См. также
Сортировка перестановок со знаками при помощи обращений (расстояние обращения)
Литература
1. Ajana, Y., Lefebvre, J.-F.,Tillier, E., El-Mabrouk, N.: Exploring the Set of All Minimal Sequences of Reversals - An Application to Test the Replication-Directed Reversal Hypothesis, Proceedings of the Second Workshop on Algorithms in Bioinformatics. Lecture Notes in Computer Science, vol. 2452, pp. 300-315.Springer, Berlin (2002)
2. Bader, D.A., Moret, B.M.E., Yan, M.: A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study. J. Comput. Biol. 8(5), 483-491 (2001)
3. Bergeron, A., Chauve, C., Hartman, T., St-Onge, K.: On the properties of sequences of reversals that sort a signed permutation. Proceedings of JOBIM'02,99-108 (2002)
4. Bergeron, A., Mixtacki, J., Stoye, J.:The inversion distance problem. In: Gascuel, O. (ed.) Mathematics of evolution and phylogeny. Oxford University Press, USA (2005)
5. Berman, P., Hannenhalli, S.: Fast Sorting by Reversal, proceedings of CPM '96. Lecture notes in computer science 1075,168-185(1996)
6. Braga, M.D.V., Sagot, M.F., Scornavacca, C., Tannier, E.: The Solution Space of Sorting by Reversals. In: Proceedings of IS-BRA'07. Lect. Notes Comp. Sci. 4463,293-304 (2007)
7. Diekmann, Y., Sagot, M.F., Tannier, E.: Evolution under Reversals: Parsimony and Conversation of Common Intervals. IEEE/ACMTransactions in Computational Biology and Bioinformatics, 4, 301-309,1075 (2007)
8. Han, Y.: Improving the Efficiency of Sorting by Reversals, Proceedings of The 2006 International Conference on Bioinformatics and Computational Biology. Las Vegas, Nevada, USA (2006)
9. Hannenhalli, S., Pevzner, P.: Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). J. ACM 46,1 -27 (1999)
10. Kaplan, H., Shamir, R., Tarjan, R.E.: Faster and simpler algorithm for sorting signed permutations by reversals. SIAM J. Comput. 29,880-892(1999)
11. Kaplan, H., Verbin, E.: Efficient data structures and a new randomized approach for sorting signed permutations by reversals. In: Proceedings of CPM'03. Lecture Notes in Computer Science 2676,170-185
12. Moret, B.M.E.,Tang, J.,Warnow,T.: Reconstructing phylogenies from gene-content and gene-order data. In: Gascuel, O. (ed.) Mathematics of Evolution and Phylogeny. pp. 321-352, Oxford Univ. Press, USA (2005)
13. Murphy, W., et al.: Dynamics of Mammalian Chromosome Evolution Inferred from Multispecies Comparative Maps. Science 309,613-617(2005)
14. Ozery-Flato, M., Shamir, R.: Two notes on genome rearrangement. J. Bioinf. Comput. Biol. 1, 71-94 (2003)
15. Pevzner, P., Tesler, G.: Human and mouse genomic sequences reveal extensive breakpoint reuse in mammalian evolution. PNAS 100,7672-7677 (2003)
16. Siepel, A.C.: An algorithm to enumerate sorting reversals for signed permutations. J. Comput. Biol. 10, 575-597 (2003)
17. Tannier, E., Sagot, M.-F.: Sorting by reversals in subquadratic time. In: Proceedings of CPM'04. Lecture Notes Comput. Sci. 3109,1-13
18. Tannier, E., Bergeron, A., Sagot, M.-F.: Advances on Sorting by Reversals. Discret.