Abstract
The evolutionary distance between two genomes can be estimated by computing the minimum length sequence of operations, called genome rearrangements, that transform one genome into another. Usually, a genome is modeled as an ordered sequence of (possibly signed) genes, and almost all the studies that have been undertaken in the genome rearrangement literature consist in shaping biological scenarios into mathematical models: for instance, allowing different genome rearrangements operations at the same time, adding constraints to these rearrangements (e.g., each rearrangement can affect at most a given number k of genes), considering that a rearrangement implies a cost depending on its length rather than a unit cost, etc. However, most of the works in the field have overlooked some important features inside genomes, such as the presence of sequences of nucleotides between genes, called intergenic regions. In this work, we investigate the problem of computing the distance between two genomes, taking into account both gene order and intergenic sizes; the genome rearrangement operation we consider here is a constrained type of reversals, called super short reversals, which affect up to two (consecutive) genes. We propose here three algorithms to solve the problem: a 3-approximation algorithm that applies to any instance, and two additional algorithms that apply only on specific types of genomes with respect to their gene order: the first one is an exact algorithm, while the second is a 2-approximation algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Biller, P., Guéguen, L., Knibbe, C., Tannier, E.: Breaking good: accounting for fragility of genomic regions in rearrangement distance estimation. Genome Biol. Evol. 8(5), 1427–1439 (2016)
Biller, P., Knibbe, C., Beslon, G., Tannier, E.: Comparative genomics on artificial life. In: Beckmann, A., Bienvenu, L., Jonoska, N. (eds.) CiE 2016. LNCS, vol. 9709, pp. 35–44. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40189-8_4
Bulteau, L., Fertin, G., Tannier, E.: Genome rearrangements with indels in intergenes restrict the scenario space. BMC Bioinform. 17(S14), 225–231 (2016)
Caprara, A.: Sorting permutations by reversals and eulerian cycle decompositions. SIAM J. Discret. Math. 12(1), 91–110 (1999)
Chen, T., Skiena, S.S.: Sorting with fixed-length reversals. Discret. Appl. Math. 71(1–3), 269–295 (1996)
Fertin, G., Jean, G., Tannier, E.: Algorithms for computing the double cut and join distance on both gene order and intergenic sizes. Algorithms Mol. Biol. 12(16), 1–11 (2017)
Fertin, G., Labarre, A., Rusu, I., Tannier, E., Vialette, S.: Combinatorics of Genome Rearrangements. Computational Molecular Biology. The MIT Press, London (2009)
Galvão, G.R., Baudet, C., Dias, Z.: Sorting circular permutations by super short reversals. IEEE/ACM Trans. Comput. Biol. Bioinform. 14(3), 620–633 (2017)
Galvão, G.R., Lee, O., Dias, Z.: Sorting signed permutations by short operations. Algorithms Mol. Biol. 10(12), 1–17 (2015)
Hannenhalli, S., Pevzner, P.A.: Transforming men into mice (polynomial algorithm for genomic distance problem). In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS 1995), pp. 581–592. IEEE Computer Society Press, Washington, DC (1995)
Jerrum, M.R.: The complexity of finding minimum-length generator sequences. Theor. Comput. Sci. 36(2–3), 265–289 (1985)
Knuth, D.E.: The art of Computer Programming: Fundamental Algorithms. Addison-Wesley, Reading (1973)
Oliveira, A.R., Fertin, G., Dias, U., Dias, Z.: Sorting signed circular permutations by super short operations. Algorithms Mol. Biol. 13(13), 1–16 (2018)
Yancopoulos, S., Attie, O., Friedberg, R.: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21(16), 3340–3346 (2005)
Acknowledgments
This work was supported by the National Council for Scientific and Technological Development - CNPq (grants 400487/2016-0, 425340/2016-3, and 140466/2018-5), the São Paulo Research Foundation - FAPESP (grants 2013/08293-7, 2015/ 11937-9, 2017/12646-3, 2017/16246-0, and 2017/16871-1), the Brazilian Federal Agency for the Support and Evaluation of Graduate Education - CAPES, and the CAPES/COFECUB program (grant 831/15).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Oliveira, A.R., Jean, G., Fertin, G., Dias, U., Dias, Z. (2018). Super Short Reversals on Both Gene Order and Intergenic Sizes. In: Alves, R. (eds) Advances in Bioinformatics and Computational Biology. BSB 2018. Lecture Notes in Computer Science(), vol 11228. Springer, Cham. https://doi.org/10.1007/978-3-030-01722-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-01722-4_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-01721-7
Online ISBN: 978-3-030-01722-4
eBook Packages: Computer ScienceComputer Science (R0)