World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A symmetry-inclusive algebraic approach to genome rearrangement

    https://doi.org/10.1142/S0219720021400151Cited by:3 (Source: Crossref)
    This article is part of the issue:

    Of the many modern approaches to calculating evolutionary distance via models of genome rearrangement, most are tied to a particular set of genomic modeling assumptions and to a restricted class of allowed rearrangements. The “position paradigm”, in which genomes are represented as permutations signifying the position (and orientation) of each region, enables a refined model-based approach, where one can select biologically plausible rearrangements and assign to them relative probabilities/costs. Here, one must further incorporate any underlying structural symmetry of the genomes into the calculations and ensure that this symmetry is reflected in the model. In our recently-introduced framework of genome algebras, each genome corresponds to an element that simultaneously incorporates all of its inherent physical symmetries. The representation theory of these algebras then provides a natural model of evolution via rearrangement as a Markov chain. Whilst the implementation of this framework to calculate distances for genomes with “practical” numbers of regions is currently computationally infeasible, we consider it to be a significant theoretical advance: one can incorporate different genomic modeling assumptions, calculate various genomic distances, and compare the results under different rearrangement models. The aim of this paper is to demonstrate some of these features.

    References

    • 1. Meidanis J, Dias Z, An alternative algebraic formalism for genome rearrangements, in Sankoff D, Nadeau JH (eds.), Comparative Genomics Computational Biology, Vol. 1, pp. 213–223, 2000. CrossrefGoogle Scholar
    • 2. Feijao P, Meidanis J, Extending the algebraic formalism for genome rearrangements to include linear chromosomes, in de Souto MC, Kann MG (eds.), Advances in Bioinformatics and Computational Biology, Springer, Berlin, pp. 13–24, 2012. CrossrefGoogle Scholar
    • 3. Francis AR, An algebraic view of bacterial genome evolution, J Math Biol 69(6–7) :1693–1718, 2014. Crossref, MedlineGoogle Scholar
    • 4. Egri-Nagy A, Gebhardt V, Tanaka MM, Francis AR, Group-theoretic models of the inversion process in bacterial genomes, J Math Biol 69(1) :243–265, 2014. Crossref, MedlineGoogle Scholar
    • 5. Bhatia S, Egri-Nagy A, Francis AR, Algebraic double cut and join: a group-theoretic approach to the operator on multichromosomal genomes, J Math Biol 71(5) :1149–1178, 2015. Crossref, MedlineGoogle Scholar
    • 6. Bhatia S, Feijão P, Francis AR, Position and content paradigms in genome rearrangements: The wild and crazy world of permutations in genomics, Bull Math Biol 80(12) :3227–3246, 2018. Crossref, MedlineGoogle Scholar
    • 7. Bergeron A, Mixtacki J, Stoye J, A unifying view of genome rearrangements, in Bücher P, Moret BME (eds.), Algorithms in Bioinformatics, Springer, Berlin, Heidelberg, pp. 163–173, 2006. CrossrefGoogle Scholar
    • 8. Braga M, Willing E, Stoye J, Double cut and join with insertions and deletions, J Comput Biol 18 :1167–1184, 2011. Crossref, MedlineGoogle Scholar
    • 9. Bohnenkämper L, Braga MDV, Doerr D, Stoye J, Computing the rearrangement distance of natural genomes, in Schwartz R (ed.), Research in Computational Molecular Biology RECOMB 2020, Springer International Publishing, Cham, pp. 3–18, 2020. CrossrefGoogle Scholar
    • 10. Simonaitis P, Chateau A, Swenson KM, A general framework for genome rearrangement with biological constraints, in Blanchette M, Ouangraoua A (eds.), Comparative Genomics, Springer International Publishing, New York, pp. 49–71, 2018. CrossrefGoogle Scholar
    • 11. 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, 2017. Crossref, MedlineGoogle Scholar
    • 12. Oliveira AR, Jean G, Fertin G, Dias U, Dias Z, Super short reversals on both gene order and intergenic sizes, in Alves R (ed.), Advances in Bioinformatics and Computational Biology, Springer International Publishing, Cham, pp. 14–25, 2018. CrossrefGoogle Scholar
    • 13. Zanetti JPP, Biller P, Meidanis J, Median approximations for genomes modeled as matrices, Bull Math Biol 78(4) :786–814, 2016. Crossref, MedlineGoogle Scholar
    • 14. Darling AE, Miklós I, Ragan MA, Dynamics of genome rearrangement in bacterial populations, PLoS Genetics 4(7) :e1000128, 2008. Crossref, MedlineGoogle Scholar
    • 15. Alexeev N, Aidagulov R, Alekseyev MA, A computational method for the rate estimation of evolutionary transpositions, in Ortuño F, Rojas I (eds.), Bioinformatics and Biomedical Engineering, Springer International Publishing, Cham, pp. 471–480, 2015. Google Scholar
    • 16. Serdoz S, Egri-Nagy A, Sumner J, Holland BR, Jarvis PD, Tanaka MM, Francis AR, Maximum likelihood estimates of pairwise rearrangement distances, J Theoret Biol 423 :31–40, 2017. Crossref, MedlineGoogle Scholar
    • 17. Galvao GR, Baudet C, Dias Z, Sorting circular permutations by super short reversals, IEEE/ACM Trans Comput Biol Bioinform 14(3) :620–633, 2017. Crossref, MedlineGoogle Scholar
    • 18. Terauds V, Sumner JG, Maximum likelihood estimates of rearrangement distance: Implementing a representation-theoretic approach, Bull Math Biol 81(2) :535–567, 2019. Crossref, MedlineGoogle Scholar
    • 19. Terauds V, Sumner JG, A new algebraic approach to genome rearrangement models, 2020, arXiv:2012.11665 (under review). Google Scholar
    • 20. Stevenson JD, Terauds V, Sumner JG, Rearrangement events on circular genomes, 2021 (in preparation). Google Scholar
    • 21. Baudet C, Dias U, Dias Z, Sorting by weighted inversions considering length and symmetry, BMC Bioinform 16, 2015. Crossref, MedlineGoogle Scholar
    • 22. Nguyen TC, Ngo HT, Nguyen NB, Sorting by restricted-length-weighted reversals, Genomics Proteomics Bioinformatics 3(2) :120–127, 2005. Crossref, MedlineGoogle Scholar
    • 23. Wang LS, Warnow T, Moret BME, Jansen RK, Raubeson LA, Distance-based genome rearrangement phylogeny, J Mol Evol 63(4) :473–483, 2006. Crossref, MedlineGoogle Scholar
    • 24. Lin Y, Moret BM, Estimating true evolutionary distances under the DCJ model, Bioinformatics 24(13) :i114–i122, 2008. Crossref, MedlineGoogle Scholar
    • 25. Sumner JG, Jarvis PD, Francis AR, A representation-theoretic approach to the calculation of evolutionary distance in bacteria, J Phys A 50(33):335601, 14, 2017. CrossrefGoogle Scholar
    • 26. Francis AR, Wynn HP, A mean first passage time genome rearrangement distance, J Math Biol 80(6) :1971–1992, 2020. Crossref, MedlineGoogle Scholar
    • 27. Moulton V, Steel M, The ‘butterfly effect’ in Cayley graphs with applications to genomics, J Math Biol 65(6–7) :1267–1284, 2012. Crossref, MedlineGoogle Scholar
    • 28. Clark C, Egri-Nagy A, Francis A, Gebhardt V, Bacterial phylogeny in the Cayley graph, Discrete Math Algorithms Appl 11(5) :1950059, 2019. LinkGoogle Scholar
    • 29. Developers TS, SageMath, the Sage Mathematics Software System (Version 9.1), 2020, http://www.sagemath.org. Google Scholar
    • 30. Hagberg AA, Schult DA, Swart PJ, Exploring network structure, dynamics, and function using NetworkX, Proc. 7th Python in Science Conf., USA, pp. 11–15, 2008. Google Scholar
    • 31. The GAP Group, GAP — Groups, Algorithms, and Programming, Version 4.11.1, 2021, https://www.gap-system.org. Google Scholar
    • 32. Dabbaghian V, GAP Team T, Repsn, Constructing representations of finite groups, Version 3.1.0, 2019, refereed GAP package. Google Scholar