On the family-free DCJ distance and similarity

Viduani Martinez FH, Feijão P, Braga MDV, Stoye J (2015)
Algorithms for Molecular Biology 10: 13.

Download
OA
Journal Article | Published | English
Abstract
Structural variation in genomes can be revealed by many (dis)similarity measures. Rearrangement operations, such as the so called double-cut-and-join (DCJ), are large-scale mutations that can create complex changes and produce such variations in genomes. A basic task in comparative genomics is to find the rearrangement distance between two given genomes, i.e., the minimum number of rearragement operations that transform one given genome into another one. In a family-based setting, genes are grouped into gene families and efficient algorithms have already been presented to compute the DCJ distance between two given genomes. In this work we propose the problem of computing the DCJ distance of two given genomes without prior gene family assignment, directly using the pairwise similarities between genes. We prove that this new family-free DCJ distance problem is APX-hard and provide an integer linear program to its solution. We also study a family-free DCJ similarity and prove that its computation is NP-hard.
Publishing Year
ISSN
Financial disclosure
Article Processing Charge funded by the Deutsche Forschungsgemeinschaft and the Open Access Publication Fund of Bielefeld University.
PUB-ID

Cite this

Viduani Martinez FH, Feijão P, Braga MDV, Stoye J. On the family-free DCJ distance and similarity. Algorithms for Molecular Biology. 2015;10: 13.
Viduani Martinez, F. H., Feijão, P., Braga, M. D. V., & Stoye, J. (2015). On the family-free DCJ distance and similarity. Algorithms for Molecular Biology, 10: 13.
Viduani Martinez, F. H., Feijão, P., Braga, M. D. V., and Stoye, J. (2015). On the family-free DCJ distance and similarity. Algorithms for Molecular Biology 10:13.
Viduani Martinez, F.H., et al., 2015. On the family-free DCJ distance and similarity. Algorithms for Molecular Biology, 10: 13.
F.H. Viduani Martinez, et al., “On the family-free DCJ distance and similarity”, Algorithms for Molecular Biology, vol. 10, 2015, : 13.
Viduani Martinez, F.H., Feijão, P., Braga, M.D.V., Stoye, J.: On the family-free DCJ distance and similarity. Algorithms for Molecular Biology. 10, : 13 (2015).
Viduani Martinez, Fábio Henrique, Feijão, Pedro, Braga, Marília D. V., and Stoye, Jens. “On the family-free DCJ distance and similarity”. Algorithms for Molecular Biology 10 (2015): 13.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2016-02-24T12:48:43Z

This data publication is cited in the following publications:
This publication cites the following data publications:

1 Citation in Europe PMC

Data provided by Europe PubMed Central.

Algorithms for reconstruction of chromosomal structures.
Lyubetsky V, Gershgorin R, Seliverstov A, Gorbunov K., BMC Bioinformatics 17(), 2016
PMID: 26780836

18 References

Data provided by Europe PubMed Central.


D, 1992

A, 2006

AUTHOR UNKNOWN, 0

AUTHOR UNKNOWN, 0
Efficient sorting of genomic permutations by translocation, inversion and block interchange.
Yancopoulos S, Attie O, Friedberg R., Bioinformatics 21(16), 2005
PMID: 15951307
Genome rearrangement with gene families.
Sankoff D., Bioinformatics 15(11), 1999
PMID: 10743557

D, 2000

L, IEEE/ACM Trans Comput Biol Bioinf. 10(6), 2013

S, J Graph Algorithms Appl. 13(1), 2009

M, 2014
Self-organizing ontology of biochemically relevant small molecules.
Chepelev LL, Hastings J, Ennis M, Steinbeck C, Dumontier M., BMC Bioinformatics 13(), 2012
PMID: 22221313

MDV, 2013

FV, 2014

MDV, J Comp Biol. 17(9), 2010

P, IEEE/ACM Trans Comput Biol Bioinf. 8(5), 2011

G, 1999

DA, Mol Biol Evol. 29(4), 2012

M, PLOS ONE 9(8), 2014

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 25859276
PubMed | Europe PMC

Search this title in

Google Scholar