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.

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
Art.-Nr.
13
ISSN
1748-7188
Finanzierungs-Informationen
Article Processing Charge funded by the Deutsche Forschungsgemeinschaft and the Open Access Publication Fund of Bielefeld University.
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: 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
2019-09-06T09:18:30Z
MD5 Prüfsumme
a7c56d8ee7c90d979865d39e56ed025f

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