Genome Rearrangements on Both Gene Order and Intergenic Regions

摘要

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. 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.