Abstract
All combinatorial works on genome rearrangements have so far ignored the influence of intergene sizes, i.e. the number of nucleotides between consecutive genes, although it was recently shown decisive for the accuracy of the inference methods [3, 4]. In this line, we define a new genome rearrangement model called wDCJ, a generalization of the well-known Double Cut and Join (or DCJ) model that allows for modifying both the gene order and the intergene size distribution of a genome. We first provide a generic formula for the wDCJ distance between two genomes, and show that computing this distance is strongly NP-complete. We then propose an approximation algorithm of ratio 3/2, and two exact ones: a fixed parameterized (FPT) algorithm and an ILP formulation. We finally provide theoretical and empirical bounds on the expected growth of the parameter at the center of our FPT and ILP algorithms, assuming a probabilistic model of evolution under wDCJ, which shows that both these algorithms should run reasonably fast in practice.
Supported by GRIOTE project, funded by Région Pays de la Loire, and the ANCESTROME project, Investissement d’avenir ANR-10-BINF-01-01.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The word gene is as usual in genome rearrangement studies taken in a liberal meaning, as any segment of DNA, computed from homologous genes or synteny blocks, which is not touched by a rearrangement in the considered history.
References
Alexeev, N., Alekseyev, M.A.: Estimation of the true evolutionary distance under the fragile breakage model. In: Proceedings of the 5th IEEE International Conference on Computational Advances in Bio and Medical Sciences (ICCABS) (2015)
Baudet, C., Dias, U., Dias, Z.: Length and symmetry on the sorting by weighted inversions problem. In: Campos, S. (ed.) BSB 2014. LNCS, vol. 8826, pp. 99–106. Springer, Heidelberg (2014)
Biller, P., Knibbe, C., Beslon, G., Tannier, E.: Comparative genomics on artificial life. In: Proceedings of Computability in Europe (2016)
Biller, P., Guéguen, L., Knibbe, C., Tannier, E.: Breaking good: accounting for the diversity of fragile regions for estimating rearrangement distances. Genome Biol. Evol. 8, 1427–1439 (2016)
Fertin, G., Labarre, A., Rusu, I., Tannier, E., Vialette, S.: Combinatorics of Genome Rearrangements. Computational Molecular Biology. MIT Press, Cambridge (2009)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1990)
Lynch, M.: The Origin of Genome Architecture. Sinauer, Sunderland (2007)
Swenson, K.M., Blanchette, M.: Models and algorithms for genome rearrangement with positional constraints. In: Pop, M., Touzet, H. (eds.) WABI 2015. LNCS, vol. 9289, pp. 243–256. Springer, Heidelberg (2015)
Yancopoulos, S., Attie, O., Friedberg, R.: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21(16), 3340–3346 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Fertin, G., Jean, G., Tannier, E. (2016). Genome Rearrangements on Both Gene Order and Intergenic Regions. In: Frith, M., Storm Pedersen, C. (eds) Algorithms in Bioinformatics. WABI 2016. Lecture Notes in Computer Science(), vol 9838. Springer, Cham. https://doi.org/10.1007/978-3-319-43681-4_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-43681-4_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-43680-7
Online ISBN: 978-3-319-43681-4
eBook Packages: Computer ScienceComputer Science (R0)