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.

Incorporating intergenic regions into reversal and transposition distances with indels

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

    Problems in the genome rearrangement field are often formulated in terms of pairwise genome comparison: given two genomes G1 and G2, find the minimum number of genome rearrangements that may have occurred during the evolutionary process. This broad definition lacks at least two important considerations: the first being which features are extracted from genomes to create a useful mathematical model, and the second being which types of genome rearrangement events should be represented. Regarding the first consideration, seminal works in the genome rearrangement field solely used gene order to represent genomes as permutations of integer numbers, neglecting many important aspects like gene duplication, intergenic regions, and complex interactions between genes. Regarding the second consideration, some rearrangement events are widely studied such as reversals and transpositions. In this paper, we shed light on the first consideration and created a model that takes into account gene order and the number of nucleotides in intergenic regions. In addition, we consider events of reversals, transpositions, and indels (insertions and deletions) of genomic material. We present a 4-approximation algorithm for reversals and indels, a 4.5-approximation algorithm for transpositions and indels, and a 6-approximation for reversals, transpositions, and indels.

    References

    • 1. Christie DA, Genome rearrangement problems, PhD Thesis, Department of Computing Science, University of Glasgow, Glasgow, 1998. Google Scholar
    • 2. Braga MD, Willing E, Stoye J, Double cut and join with insertions and deletions, J Comput Biol 18(9) :1167–1184, 2011. Crossref, MedlineGoogle Scholar
    • 3. Willing E, Stoye J, Braga MD, Computing the inversion-indel distance, IEEE/ACM Trans Comput Biol Bioinf, 2020. Google Scholar
    • 4. Alexandrino AO, Oliveira AR, Dias U, Dias Z, Genome rearrangement distance with reversals, transpositions, and indels, J Comput Biol 28(3) :235–247, 2021. Crossref, MedlineGoogle Scholar
    • 5. Biller P, Guguen 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. Crossref, MedlineGoogle Scholar
    • 6. Biller P, Knibbe C, Beslon G, Tannier E, Comparative genomics on artificial life, Pursuit of the Universal, Springer International Publishing, Switzerland, pp. 35–44, 2016. CrossrefGoogle Scholar
    • 7. Bulteau L, Fertin G, Tannier E, Genome rearrangements with indels in intergenes restrict the scenario space, BMC Bioinf 17(14) :426, 2016. Crossref, MedlineGoogle Scholar
    • 8. Brito KL, Jean G, Fertin G, Oliveira AR, Dias U, Dias Z, Sorting by genome rearrangements on both gene order and intergenic sizes, J Comput Biol 27(2) :156–174, 2020. Crossref, MedlineGoogle Scholar
    • 9. Oliveira AR, Jean G, Fertin G, Brito KL, Bulteau L, Dias U, Dias Z, Sorting signed permutations by intergenic reversals, IEEE/ACM Trans Comput Biol Bioinf, 2020. MedlineGoogle Scholar
    • 10. Caprara A, Sorting permutations by reversals and Eulerian cycle decompositions, SIAM J Discrete Math 12(1) :91–110, 1999. CrossrefGoogle Scholar
    • 11. Alexandrino AO, Lintzmayer CN, Dias Z, Sorting permutations by fragmentation-weighted operations, J Bioinform Comput Biol 18 :2050006, 2020. LinkGoogle Scholar
    • 12. Brito KL, Jean G, Fertin G, Oliveira AR, Dias U, Dias Z, Sorting by reversals, transpositions, and indels on both gene order and intergenic sizes, Int Symp Bioinformatics Research and Applications, Springer International Publishing, pp. 28–39, 2019. CrossrefGoogle Scholar
    • 13. Bulteau L, Fertin G, Rusu I, Sorting by transpositions is difficult, SIAM J Discrete Math 26(3) :1148–1180, 2012. CrossrefGoogle Scholar
    • 14. Oliveira AR, Brito KL, Dias U, Dias Z, On the complexity of sorting by reversals and transpositions problems, J Comput Biol 26(11) :1223–1229, 2019. Crossref, MedlineGoogle Scholar