Computing the family-free DCJ similarity

Rubert D, Hoshino EA, Dias Vieira Braga M, Stoye J, Martinez FHV (2018)
BMC Bioinformatics 19(Suppl. 6): 152.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
OA 1.62 MB
Abstract / Bemerkung
Background The genomic similarity is a large-scale measure for comparing two given genomes. In this work we study the (NP-hard) problem of computing the genomic similarity under the DCJ model in a setting that does not assume that the genes of the compared genomes are grouped into gene families. This problem is called family-free DCJ similarity. Results We propose an exact ILP algorithm to solve the family-free DCJ similarity problem, then we show its APX-hardness and present four combinatorial heuristics with computational experiments comparing their results to the ILP. Conclusions We show that the family-free DCJ similarity can be computed in reasonable time, although for larger genomes it is necessary to resort to heuristics. This provides a basis for further studies on the applicability and model refinement of family-free whole genome similarity measures.
Genome rearrangement; Double-cut-and-join; Family-free genomic similarity
BMC Bioinformatics
Suppl. 6
Page URI


Rubert D, Hoshino EA, Dias Vieira Braga M, Stoye J, Martinez FHV. Computing the family-free DCJ similarity. BMC Bioinformatics. 2018;19(Suppl. 6): 152.
Rubert, D., Hoshino, E. A., Dias Vieira Braga, M., Stoye, J., & Martinez, F. H. V. (2018). Computing the family-free DCJ similarity. BMC Bioinformatics, 19(Suppl. 6), 152. doi:10.1186/s12859-018-2130-5
Rubert, D., Hoshino, E. A., Dias Vieira Braga, M., Stoye, J., and Martinez, F. H. V. (2018). Computing the family-free DCJ similarity. BMC Bioinformatics 19:152.
Rubert, D., et al., 2018. Computing the family-free DCJ similarity. BMC Bioinformatics, 19(Suppl. 6): 152.
D. Rubert, et al., “Computing the family-free DCJ similarity”, BMC Bioinformatics, vol. 19, 2018, : 152.
Rubert, D., Hoshino, E.A., Dias Vieira Braga, M., Stoye, J., Martinez, F.H.V.: Computing the family-free DCJ similarity. BMC Bioinformatics. 19, : 152 (2018).
Rubert, Diego, Hoshino, Edna A., Dias Vieira Braga, Marília, Stoye, Jens, and Martinez, Fábio Henrique Viduani. “Computing the family-free DCJ similarity”. BMC Bioinformatics 19.Suppl. 6 (2018): 152.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Access Level
OA Open Access
Zuletzt Hochgeladen
MD5 Prüfsumme

30 References

Daten bereitgestellt von Europe PubMed Central.

Genome rearrangement with gene families.
Sankoff D., Bioinformatics 15(11), 1999
PMID: 10743557
Genome rearrangements and sorting by reversals
Bafna V, Pevzner P., 1993
Transforming men into mice (polynomial algorithm for genomic distance problem)
Hannenhalli S, Pevzner P., 1995
Efficient sorting of genomic permutations by translocation, inversion and block interchange.
Yancopoulos S, Attie O, Friedberg R., Bioinformatics 21(16), 2005
PMID: 15951307
A unifying view of genome rearrangements
Bergeron A, Mixtacki J, Stoye J., 2006
Double cut and join with insertions and deletions.
Braga MD, Willing E, Stoye J., J. Comput. Biol. 18(9), 2011
PMID: 21899423
The complexity of calculating exemplar distances
Bryant D., 2000
Inapproximability of (1,2)-exemplar distance.
Bulteau L, Jiang M., IEEE/ACM Trans Comput Biol Bioinform 10(6), 2013
PMID: 24407297
A pseudo-boolean framework for computing rearrangement distances between genomes with duplicates.
Angibaud S, Fertin G, Rusu I, Vialette S., J. Comput. Biol. 14(4), 2007
PMID: 17572018
Efficient tools for computing the number of breakpoints and the number of adjacencies between two genomes with duplicate genes.
Angibaud S, Fertin G, Rusu I, Thevenin A, Vialette S., J. Comput. Biol. 15(8), 2008
PMID: 18774903
On the approximability of comparing genomes with duplicates
Angibaud S, Fertin G, Rusu I, Thévenin A, Vialette S., 2009
An exact algorithm to compute the DCJ distance for genomes with duplicate genes
Shao M, Lin Y, Moret B., 2014
Gene family assignment-free comparative genomics.
Doerr D, Thevenin A, Stoye J., BMC Bioinformatics 13 Suppl 19(), 2012
PMID: 23281826
The potential of family-free genome comparison
Braga MDV, Chauve C, Doerr D, Jahn K, Stoye J, Thévenin A, Wittler R., 2013
Bayesian estimation of genomic distance.
Durrett R, Nielsen R, York TL., Genetics 166(1), 2004
PMID: 15020449
On the family-free DCJ distance and similarity.
Martinez FV, Feijao P, Braga MD, Stoye J., Algorithms Mol Biol 10(), 2015
PMID: 25859276
Algorithms for computing the family-free genomic similarity under DCJ
Rubert DP, Medeiros GL, Hoshino EA, Braga MDV, Stoye J, Martinez FV., 2017
Non-breaking similarity of genomes with gene repetitions
Chen Z, Fu B, Xu J, Yang B, Zhao Z, Zhu B., 2007
Approximating the DCJ distance of balanced genomes in linear time.
Rubert DP, Feijao P, Braga MDV, Stoye J, Martinez FHV., Algorithms Mol Biol 12(), 2017
PMID: 28293275
Algorithms for the assignment and transportation problems
Munkres J., 1957
Theoretical improvements in algorithmic efficiency for network flow problems
Edmonds J, Karp RM., 1972
On some techniques useful for solution of transportation network problems
Tomizawa N., 1971

Finding all the elementary circuits of a directed graph
Johnson D., 1975
A d/2 approximation for maximum weight independent set in d-claw free graphs
Berman P., 2000
ALF--a simulation framework for genome evolution.
Dalquen DA, Anisimova M, Gonnet GH, Dessimoz C., Mol. Biol. Evol. 29(4), 2011
PMID: 22160766


Ohno S., 2013


Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®


PMID: 29745861
PubMed | Europe PMC

Suchen in

Google Scholar