World Scientific
  • Search
    Quick Search in Journals
    Access type:
    Quick Search anywhere
    Access type:
    Advanced Search
  • My Cart
  •   
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
×

Our site uses Javascript to enchance its usability.You can disable your ad blocker or whitelist our website www.worldscientific.com to view the full content.

Select your blocker:

Adblock Plus Instructions

  1. Click the AdBlock Plus icon in the extension bar
  2. Click the blue power button
  3. Click refresh

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.
Research PaperNo Access

Bacterial phylogeny in the Cayley graph

    https://doi.org/10.1142/S1793830919500599Cited by:4 (Source: Crossref)
    Previous
    Next

    Abstract

    Many models of genome rearrangement involve operations that are self-inverse, and hence generate a group acting on the space of genomes. This gives a correspondence between genome arrangements and the elements of a group, and consequently, between evolutionary paths and walks on the Cayley graph. Many common methods for phylogenetic reconstruction rely on calculating the minimal distance between two genomes; this omits much of the other information available from the Cayley graph. In this paper, we begin an exploration of some of this additional information, in particular describing the phylogeny as a Steiner tree within the Cayley graph, and exploring the “interval” between two genomes. While motivated by problems in systematic biology, many of these ideas are of independent group-theoretic interest.

    AMSC: 05C12, 06A07, 92D15

    References

    • 1. D. A. Bader, B. M. E. Moret and M. Yan , A linear-time algorithm for computing inversion distance between signed permutations with an experimental study, J. Comput. Biol. 8(5) (2001) 483–491. Crossref, Google Scholar
    • 2. V. Bafna and P. Pevzner , Sorting permutations by transpositions, in Proc. Sixth Annual ACM-SIAM Symp. Discrete Algorithms (Society for Industrial and Applied Mathematics, 1995), pp. 614–623. Google Scholar
    • 3. S. Bhatia, P. Feijão and A. R. Francis , Position and content paradigms in genome rearrangements: The wild and crazy world of permutations in genomics, Bull. Math. Biol. 80(12) (2018) 3227–3246. Crossref, Google Scholar
    • 4. A. Björner and F. Brenti , Combinatorics of Coxeter Groups (Graduate Texts in Mathematics, Springer, 2005). Google Scholar
    • 5. G. Bourque and P. A. Pevzner , Genome-scale evolution: Reconstructing gene orders in the ancestral species, Genome Res. 12(1) (2002) 26–36. Google Scholar
    • 6. M. Braga , Baobabluna: The solution space of sorting by reversals, Bioinformatics 25(14) (2009) 1833–1835. Crossref, Google Scholar
    • 7. M. Braga, M. Sagot, C. Scornavacca and E. Tannier , The solution space of sorting by reversals, in Int. Symp. Bioinformatics Research and Applications (Springer, 2007), pp. 293–304. Crossref, Google Scholar
    • 8. A. Caprara , On the practical solution of the reversal median problem, in Int. Workshop on Algorithms in Bioinformatics (Springer, 2001), pp. 238–251. Crossref, Google Scholar
    • 9. A. Caprara , The reversal median problem, INFORMS J. Comput. 15(1) (2003) 93. Crossref, Google Scholar
    • 10. N. Caspard, B. Leclerc and B. Monjardet , Finite ordered sets: Concepts, results and uses, in Encyclopedia of Mathematics and its Applications, Vol. 144 (Cambridge University Press, 2012). Crossref, Google Scholar
    • 11. L. F. I. Cunha, P. Feijão, V. F. dos Santos, L. A. B. Kowada and C. M. H. de Figueiredo , On the computational complexity of closest genome problems, Discrete Appl. Math. (2019) (in press). Crossref, Google Scholar
    • 12. A. C. E. Darling, B. Mau, F. R. Blattner and N. T. Perna , Mauve: Multiple alignment of conserved genomic sequence with rearrangements, Genome Res. 14(7) (2004) 1394–1403. Crossref, Google Scholar
    • 13. B. A. Davey and H. A. Priestley , Introduction to Lattices and Order, 2nd edn. (Cambridge University Press, 2002). Crossref, Google Scholar
    • 14. A. Egri-Nagy, A. R. Francis and V. Gebhardt , Bacterial genomics and computational group theory: The BioGAP package for GAP, in Mathematical Software — ICMS 2014, Lecture Notes in Computer Science, eds. H. Hong and C. Yap , Vol. 8592 (Springer Berlin Heidelberg, 2014), pp. 67–74, https://github.com/egri-nagy/biogap. Crossref, Google Scholar
    • 15. A. Egri-Nagy, V. Gebhardt, M. M. Tanaka and A. R. Francis , Group-theoretic models of the inversion process in bacterial genomes, J. Math. Biol. 69(1) (2014) 243–265. Crossref, Google Scholar
    • 16. G. Fertin , Combinatorics of Genome Rearrangements (MIT Press, 2009). Crossref, Google Scholar
    • 17. N. Gao, N. Yang and J. Tang , Ancestral genome inference using a genetic algorithm approach, PloS One 8(5) (2013) e62156. Crossref, Google Scholar
    • 18. GAP Group, GAP — Groups, Algorithms, and Programming, Version 4.7.8 (2015), https://www.gap-system.org. Google Scholar
    • 19. O. Gascuel , Mathematics of Evolution and Phylogeny (Oxford University Press, 2005). Crossref, Google Scholar
    • 20. S. Hannenhalli and P. A. Pevzner , Transforming men into mice (polynomial algorithm for genomic distance problem), in Proc. 36th Annual Symp. Foundations of Computer Science, 1995 (IEEE, Milwaukee, USA, 1995), pp. 581–592. Crossref, Google Scholar
    • 21. J. Kececioglu and D. Sankoff , Exact and approximation algorithms for the inversion distance between two permutations, Algorithmica 13(1–2) (1995) 180–210. Crossref, Google Scholar
    • 22. B. M. E. Moret, L.-S. Wang, T. Warnow and S. K. Wyman , New approaches for reconstructing phylogenies from gene order data, Bioinformatics, 17(suppl 1) (2001) S165–S173. Crossref, Google Scholar
    • 23. V. Moulton and M. Steel , The butterfly effect in Cayley graphs with applications to genomics, J. Math. Biol. 65(6–7) (2012) 1267–1284. Crossref, Google Scholar
    • 24. D. Sankoff , Edit distance for genome comparison based on non-local operations, in Annual Symp. Combinatorial Pattern Matching (Springer, 1992), pp. 121–135. Crossref, Google Scholar
    • 25. D. Sankoff, G. Sundaram and J. Kececioglu , Steiner points in the space of genome rearrangements, Int. J. Found. Comput. Sci. 7(1) (1996) 1–9. Link, Google Scholar
    • 26. J. G. Sumner, P. D. Jarvis and A. R. Francis , A representation-theoretic approach to the calculation of evolutionary distance in bacteria, J. Phys. A Math. Theor. 50(33) (2017) 335601. Crossref, Google Scholar
    • 27. K. M. Swenson, V. Rajan, Y. Lin and B. Moret , Sorting signed permutations by inversions in O(nlogn) time, in Annual Int. Conf. Research in Computational Molecular Biology (Springer, 2009), pp. 386–399. Crossref, Google Scholar
    • 28. V. Terauds and J. Sumner , Maximum likelihood estimates of rearrangement distance: Implementing a representation-theoretic approach, Bull. Math. Biol. 81(2) (2019) 535–567. Crossref, Google Scholar
    • 29. G. A. Watterson, W. J. Ewens, T. E. Hall and A. Morgan , The chromosome inversion problem, J. Theor. Biol. 99(1) (1982) 1–7. Crossref, Google Scholar
    • 30. J. P. P. Zanetti, P. Biller and J. Meidanis , Median approximations for genomes modeled as matrices, Bull. Math. Biol. 78(4) (2016) 786–814. Crossref, Google Scholar
    Remember to check out the Most Cited Articles!

    Be inspired by these NEW Mathematics books for inspirations & latest information in your research area!