On the family-free DCJ distance and similarity

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

Download
OA
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Volltext vorhanden für diesen Nachweis
Abstract / Bemerkung
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.
Erscheinungsjahr
Zeitschriftentitel
Algorithms for Molecular Biology
Band
10
Artikelnummer
13
ISSN
Finanzierungs-Informationen
Article Processing Charge funded by the Deutsche Forschungsgemeinschaft and the Open Access Publication Fund of Bielefeld University.
PUB-ID

Zitieren

Viduani Martinez FH, Feijão P, Dias Vieira Braga M, Stoye J. On the family-free DCJ distance and similarity. Algorithms for Molecular Biology. 2015;10: 13.
Viduani Martinez, F. H., Feijão, P., Dias Vieira Braga, M., & Stoye, J. (2015). On the family-free DCJ distance and similarity. Algorithms for Molecular Biology, 10, 13. doi:10.1186/s13015-015-0041-9
Viduani Martinez, F. H., Feijão, P., Dias Vieira Braga, M., 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., Dias Vieira Braga, M., 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, Dias Vieira Braga, Marília, and Stoye, Jens. “On the family-free DCJ distance and similarity”. Algorithms for Molecular Biology 10 (2015): 13.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2016-02-24T12:48:43Z

4 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

The gene family-free median of three.
Doerr D, Balaban M, Feijão P, Chauve C., Algorithms Mol Biol 12(), 2017
PMID: 28559921
New Genome Similarity Measures based on Conserved Gene Adjacencies.
Doerr D, Kowada LAB, Araujo E, Deshpande S, Dantas S, Moret BME, Stoye J., J Comput Biol 24(6), 2017
PMID: 28590847
Algorithms for reconstruction of chromosomal structures.
Lyubetsky V, Gershgorin R, Seliverstov A, Gorbunov K., BMC Bioinformatics 17(), 2016
PMID: 26780836

18 References

Daten bereitgestellt von 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

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 25859276
PubMed | Europe PMC

Suchen in

Google Scholar