Algorithms for Sorting by Reversals or Transpositions, with Application to Genome Rearrangement

• Gustavo Rodrigues Galvão UNICAMP
• Zanoni Dias UNICAMP

DOI: https://doi.org/10.5753/ctd.2016.9145

Resumo

The problem of finding the minimum sequence of rearrangements that transforms one genome into another is a well-studied problem that finds application in comparative genomics. Representing genomes as permutations, in which genes appear as elements, that problem can be reduced to the combinatorial problem of sorting a permutation using a minimum number of rearrangements. Such combinatorial problem varies according to the types of rearrangements considered. The PhD thesis summarized in this paper presents exact, approximation, and heuristic algorithms for solving variants of the permutation sorting problem involving two types of rearrangements: reversals and transpositions.

Referências

Benoît-Gagné, M. and Hamel, S. (2007). A new and faster method of sorting by transpositions. In Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM’2007), volume 4580 of Lecture Notes in Computer Science, pages 131–141, London, Ontario, Canada. Springer-Verlag.

Dalevi, D. A., Eriksen, N., Eriksson, K., and Andersson, S. G. E. (2002). Measuring genome divergence in bacteria: A case study using chlamydian data. Journal of Molecular Evolution, 55(1):24–36.

Darling, A. E., Miklós, I., and Ragan, M. A. (2008). Dynamics of genome rearrangement in bacterial populations. PLoS Genetics, 4(7):e1000128.

Dias, U., Galvão, G. R., Lintzmayer, C. N., and Dias, Z. (2014). A general heuristic for genome rearrangement problems. Journal of Bioinformatics and Computational Biology, 12(3):1450012.

Egri-Nagy, A., Gebhardt, V., Tanaka, M. M., and Francis, A. R. (2014). Group-theoretic models of the inversion process in bacterial genomes. Journal of Mathematical Biology, 69(1):243–265.

Fertin, G., Labarre, A., Rusu, I., Tannier, E., and Vialette, S. (2009). Combinatorics of Genome Rearrangements. The MIT Press, Cambridge, MA, USA.

Galvão, , G. R. (2012). Uma Ferramenta de Auditoria para Algoritmos de Rearranjo de Genomas. Master’s thesis, University of Campinas. In Portuguese.

Galvão, , G. R. (2015). Algorithms for Sorting by Reversals or Transpositions, with Application to Genome Rearrangement. PhD thesis, University of Campinas.

Galvão, , G. R., Baudet, C., and Dias, Z. (2015a). Sorting signed circular permutations by super short reversals. In Proceedings of the 11th International Symposium on Bioinformatics Research and Applications (ISBRA’2015), volume 9096 of Lecture Notes in Computer Science, pages 272–283. Springer International Publishing.

Galvão, G. R., Baudet, C., and Dias, Z. (2016). Sorting circular permutations by super short reversals. IEEE/ACM Transactions on Computational Biology and Bioinformatics. To appear.