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(1): 13.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA
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.
Stichworte
Family-free genome comparison; Genome rearrangement; DCJ
Erscheinungsjahr
2015
Zeitschriftentitel
Algorithms for Molecular Biology
Band
10
Ausgabe
1
Art.-Nr.
13
ISSN
1748-7188
Finanzierungs-Informationen
Open-Access-Publikationskosten wurden durch die Deutsche Forschungsgemeinschaft und die Universität Bielefeld gefördert.
Page URI
https://pub.uni-bielefeld.de/record/2726366

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(1): 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(1), 13. doi:10.1186/s13015-015-0041-9
Viduani Martinez, Fábio Henrique, Feijão, Pedro, Dias Vieira Braga, Marília, and Stoye, Jens. 2015. “On the family-free DCJ distance and similarity”. Algorithms for Molecular Biology 10 (1): 13.
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(1): 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.1 (2015): 13.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
Dieses Objekt ist durch das Urheberrecht und/oder verwandte Schutzrechte geschützt. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-06T09:18:30Z
MD5 Prüfsumme
a7c56d8ee7c90d979865d39e56ed025f


5 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

Computing the family-free DCJ similarity.
Rubert DP, Hoshino EA, Braga MDV, Stoye J, Martinez FV., BMC Bioinformatics 19(suppl 6), 2018
PMID: 29745861
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