↓ Skip to main content

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

Overview of attention for article published in Algorithms for Molecular Biology, June 2017
Altmetric Badge

Mentioned by

twitter
1 X user

Citations

dimensions_citation
25 Dimensions

Readers on

mendeley
6 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Title
Algorithms for computing the double cut and join distance on both gene order and intergenic sizes
Published in
Algorithms for Molecular Biology, June 2017
DOI 10.1186/s13015-017-0107-y
Pubmed ID
Authors

Guillaume Fertin, Géraldine Jean, Eric Tannier

Abstract

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

X Demographics

X Demographics

The data shown below were collected from the profile of 1 X user who shared this research output. Click here to find out more about how the information was compiled.
Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 6 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
Unknown 6 100%

Demographic breakdown

Readers by professional status Count As %
Student > Doctoral Student 2 33%
Professor 1 17%
Student > Ph. D. Student 1 17%
Student > Master 1 17%
Unknown 1 17%
Readers by discipline Count As %
Computer Science 2 33%
Biochemistry, Genetics and Molecular Biology 1 17%
Unknown 3 50%
Attention Score in Context

Attention Score in Context

This research output has an Altmetric Attention Score of 1. This is our high-level measure of the quality and quantity of online attention that it has received. This Attention Score, as well as the ranking and number of research outputs shown below, was calculated when the research output was last mentioned on 06 June 2017.
All research outputs
#20,427,593
of 22,979,862 outputs
Outputs from Algorithms for Molecular Biology
#233
of 264 outputs
Outputs of similar age
#275,988
of 317,195 outputs
Outputs of similar age from Algorithms for Molecular Biology
#5
of 6 outputs
Altmetric has tracked 22,979,862 research outputs across all sources so far. This one is in the 1st percentile – i.e., 1% of other outputs scored the same or lower than it.
So far Altmetric has tracked 264 research outputs from this source. They receive a mean Attention Score of 3.1. This one is in the 1st percentile – i.e., 1% of its peers scored the same or lower than it.
Older research outputs will score higher simply because they've had more time to accumulate mentions. To account for age we can compare this Altmetric Attention Score to the 317,195 tracked outputs that were published within six weeks on either side of this one in any source. This one is in the 1st percentile – i.e., 1% of its contemporaries scored the same or lower than it.
We're also able to compare this research output to 6 others from the same source and published within six weeks on either side of this one.