Top

Published in:

2019 | OriginalPaper | Chapter

Generalizations of the Genomic Rank Distance to Indels

Authors : João Paulo Pereira Zanetti, Leonid Chindelevitch, João Meidanis

Published in: Algorithms for Computational Biology

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The rank distance model, introduced by Zanetti et al. in 2016, represents genome rearrangements in multi-chromosomal genomes looking at them as matrices. So far, this model only supported comparisons between genomes with the same gene content. We seek to generalize it, allowing for genomes with different gene content. In this paper, we approach such generalization from two different angles, both using the same representation of genomes, and leading to simple distance formulas and sorting algorithms for genomes with different gene contents, but without duplications.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Counting Sorting Scenarios and Intermediate Genomes for the Rank Distance

next chapter Using INC Within Divide-and-Conquer Phylogeny Estimation

Braga, M., Machado, R., Ribeiro, L., Stoye, J.: On the weight of indels in genomic distances. BMC Bioinformatics 12 (2011). https://doi.org/10.1186/1471-2105-12-S9-S13

Braga, M.D.V., Machado, R., Ribeiro, L.C., Stoye, J.: Genomic distance under gene substitutions. BMC Bioinform. 12(Suppl 9), S8 (2011)CrossRef

Braga, M.D.V.: An overview of genomic distances modeled with indels. In: Bonizzoni, P., Brattka, V., Löwe, B. (eds.) CiE 2013. LNCS, vol. 7921, pp. 22–31. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39053-1_3CrossRef

Braga, M.D., Willing, E., Stoye, J.: Double cut and join with insertions and deletions. J. Comput. Biol. 18(9), 1167–1184 (2011)MathSciNetCrossRef

Compeau, P.E.C.: DCJ-indel sorting revisited. Algorithms Mol. Biol. 8(1), 6 (2013). https://doi.org/10.1186/1748-7188-8-6CrossRef

El-Mabrouk, N.: Sorting signed permutations by reversals and insertions/deletions of contiguous segments. J. Discrete Algorithms 1(1), 105–122 (2001)MathSciNet

Gladieux, P., et al.: Gene flow between divergent cereal- and grass-specific lineages of the rice blast fungus Magnaporthe oryzae. mBio 9(1) (2018). https://doi.org/10.1128/mBio.01219-17

Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM 46(1), 1–27 (1999). https://doi.org/10.1145/300515.300516MathSciNetCrossRefMATH

Kumar, S., Stecher, G., Li, M., Knyaz, C., Tamura, K.: MEGA X: molecular evolutionary genetics analysis across computing platforms. Mol. Biol. Evol. 35(6), 1547–1549 (2018)CrossRef

10.

Meidanis, J., Biller, P., Zanetti, J.P.P.: A matrix-based theory for genome rearrangements. Technical report IC-17-11, Institute of Computing, University of Campinas, in English, 45 p., August 2017

11.

Paten, B., Zerbino, D.R., Hickey, G., Haussler, D.: A unifying model of genome evolution under parsimony. BMC Bioinform. 15(1), 206 (2014)CrossRef

12.

Saitou, N., Nei, M.: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4(4), 406–425 (1987)

13.

Willing, E., Zaccaria, S., Braga, M.D., Stoye, J.: On the inversion-indel distance. In: BMC Bioinformatics, vol. 14, p. S3. BioMed Central (2013)CrossRef

14.

Yancopoulos, S., Attie, O., Friedberg, R.: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21(16), 3340–3346 (2005)CrossRef

15.

Yancopoulos, S., Friedberg, R.: DCJ path formulation for genome transformations which include insertions, deletions, and duplications. J. Comput. Biol. 16(10), 1311–1338 (2009)MathSciNetCrossRef

16.

Zanetti, J.P.P., Biller, P., Meidanis, J.: Median approximations for genomes modeled as matrices. Bull. Math. Biol. 78(4), 786–814 (2016)MathSciNetCrossRef

Title: Generalizations of the Genomic Rank Distance to Indels
Authors: João Paulo Pereira Zanetti
Leonid Chindelevitch
João Meidanis
Publisher: Springer International Publishing
Book: Algorithms for Computational Biology
Print ISBN: 978-3-030-18173-4

Electronic ISBN: 978-3-030-18174-1

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-18174-1_11

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner