Algorithms for computing the double cut and join distance on both gene order and intergenic sizes

Algorithms for Molecular Biology

Eric Tannier¹  Guillaume Fertin²  Géraldine Jean² 

[1] Institut National de Recherche en Informatique et en Automatique (Inria) Grenoble Rhône-Alpes;LS2N UMR CNRS 6004, Université de Nantes;

关键词: DCJ;    Intergenic regions;    Genome rearrangements;    Algorithms;   

DOI  :  10.1186/s13015-017-0107-y

来源: DOAJ

【 摘 要 】

Abstract Background 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 inference methods (Biller et al. in Genome Biol Evol 8:1427–39, 2016; Biller et al. in Beckmann A, Bienvenu L, Jonoska N, editors. Proceedings of Pursuit of the Universal-12th conference on computability in Europe, CiE 2016, Lecture notes in computer science, vol 9709, Paris, France, June 27–July 1, 2016. Berlin: Springer, p. 35–44, 2016). In this line, we define a new genome rearrangement model called wDCJ, a generalization of the well-known double cut and join (or DCJ) operation that modifies both the gene order and the intergene size distribution of a genome. Results 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 4/3, and two exact ones: a fixed-parameter tractable (FPT) algorithm and an integer linear programming (ILP) formulation. Conclusions We 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.

【 授权许可】

Unknown