4446
правок
Сортировка перестановок со знаками при помощи обращений (последовательность обращений): различия между версиями
Материал из WEGA
Сортировка перестановок со знаками при помощи обращений (последовательность обращений) (посмотреть исходный код)
Версия от 11:48, 26 февраля 2019
, 26 февраля 2019→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 65: | Строка 65: | ||
== Применение == | == Применение == | ||
Основной мотивацией и основной областью применения для этих исследований является вычислительная биология. Подписанные перестановки оказались адекватным способом моделирования относительного положения и ориентации гомологичных участков ДНК двух видов. Обобщение этой задачи до мультихромосомных моделей было разработано и применено для геномов млекопитающих [15], свидетельствуя в пользу эволюционной модели, в которой обращения встречаются не случайным образом. | |||
Аджана и др. [1] применили случайные исследования в пространстве решений для проверки гипотезы, заключавшейся в том, что у бактерий обращения встречаются главным образом вблизи точек начала или окончания репликации. | |||
Обобщения этого подхода для сравнения более чем двух геномов широко рассматривались в литературе и применялись для реконструкции эволюционных событий и организации геномов общих предков биологических видов, а также для вывода ортологичных генов на основе их позиций; они основаны на эвристических принципах, базирующихся на теории сортировки подписанных перестановок при помощи обращений [12, 13]. | |||
== Ссылки на код == | |||
• www.cse.ucsd.edu/groups/bioinformatics/GRIMM/ | |||
Теслер из группы Певзнера выложил в Интернет реализацию мультихромосомного обобщения алгоритма Каплана, Шамира и Тарьяна [10], названную им GRIMM, что означает «Genome Rearrangements In Man and Mouse» (Перестройка генома человека и мыши). | |||
• www.cs.unm.edu/~moret/GRAPPA/ | |||
Название GRAPPA расшифровывается как "Genome Rearrangements Analysis under Parsimony and other Phylogenetic Algorithms" (Анализ перестройки генома при помощи подхода на базе максимальной экономичности и других филогенетических алгоритмов). Алгоритм включает вычисление расстояний и способен находить все безопасные обращения за один шаг. Он был разработано группой Морета. | |||
• www.math.tau.ac.il/~rshamir/GR/ | |||
Апплет, написанный Мантином, реализует алгоритм Каплана, Шамира и Тарьяна [10]. | |||
• biomserv.univ-lyon1.fr/~tannier/PSbR/ | |||
Созданная Дикманном программа выполняет поиск сценария обращений с дополнительными ограничениями для подписанных перестановок, реализуя алгоритм Танье и Сагот [17]. | |||
• www.geocities.com/mdvbraga/baobabLuna.html | |||
Программа, разработанная Марилией Брагой для обработки перестановок и, в частности, для сортировки подписанных перестановок при помощи обращений, а также для выдачи сжатого представления всех оптимальных последовательностей перестановок, является реализацией алгоритма из работы [6]. | |||
== Открытые вопросы == | |||
• Уменьшение сложности ниже значения <math>O(n^{3/2})</math>. Этого можно добиться за счет применения более рациональной структуры данных или изменения принципа работы алгоритма, в силу чего отпадет необходимость применения на каждом этапе обращения сортировки для получения возможности вычисления следующих. | |||
• Эффективное представление и перечисление всего множества решений (определенные шаги в этом направлении были сделаны в работах [3, 6]). | |||
• Поиск среди всех решений таких, которые удовлетворяли бы некоторым биологическим ограничениям – таким как сохранение некоторой общей группы генов или приоритетность небольших инверсий (некоторые достижения представлены в работе [7]). | |||
== Экспериментальные результаты == | |||
Алгоритм Танье, Бержерон и Сагот [18] был реализован в его квадратичной версии (без конкретной структуры данных, что, вероятно, имеет смысл только для перестановок очень большого размера) Дикманном (biomserv.univ-lyon1.fr/~tannier/PSbR/), однако не сообщалось ни о реализации структур данных, ни об экспериментальных данных по сложности. | |||
== См. также == | |||
[[Сортировка подписанных перестановок при помощи обращений (расстояние обращения)]] | |||
== Литература == | |||
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. | |||
