Approximating the DCJ distance of balanced genomes in linear time

Rubert D, Feijão P, Dias Vieira Braga M, Stoye J, Martinez FHV (2017)
Algorithms for Molecular Biology 12: 3.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA 2.08 MB
Abstract / Bemerkung
Background Rearrangements are large-scale mutations in genomes, responsible for complex changes and structural variations. Most rearrangements that modify the organization of a genome can be represented by the double cut and join (DCJ) operation. Given two balanced genomes, i.e., two genomes that have exactly the same number of occurrences of each gene in each genome, we are interested in the problem of computing the rearrangement distance between them, i.e., finding the minimum number of DCJ operations that transform one genome into the other. This problem is known to be NP-hard. Results We propose a linear time approximation algorithm with approximation factor O(k) for the DCJ distance problem, where k is the maximum number of occurrences of any gene in the input genomes. Our algorithm works for linear and circular unichromosomal balanced genomes and uses as an intermediate step an O(k)-approximation for the minimum common string partition problem, which is closely related to the DCJ distance problem. Conclusions Experiments on simulated data sets show that our approximation algorithm is very competitive both in efficiency and in quality of the solutions.
Stichworte
Double cut and join (DCJ); Genome rearrangements; Comparative genomics; Approximation algorithms
Erscheinungsjahr
2017
Zeitschriftentitel
Algorithms for Molecular Biology
Band
12
Art.-Nr.
3
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/2909057

Zitieren

Rubert D, Feijão P, Dias Vieira Braga M, Stoye J, Martinez FHV. Approximating the DCJ distance of balanced genomes in linear time. Algorithms for Molecular Biology. 2017;12: 3.
Rubert, D., Feijão, P., Dias Vieira Braga, M., Stoye, J., & Martinez, F. H. V. (2017). Approximating the DCJ distance of balanced genomes in linear time. Algorithms for Molecular Biology, 12, 3. doi:10.1186/s13015-017-0095-y
Rubert, D., Feijão, P., Dias Vieira Braga, M., Stoye, J., and Martinez, F. H. V. (2017). Approximating the DCJ distance of balanced genomes in linear time. Algorithms for Molecular Biology 12:3.
Rubert, D., et al., 2017. Approximating the DCJ distance of balanced genomes in linear time. Algorithms for Molecular Biology, 12: 3.
D. Rubert, et al., “Approximating the DCJ distance of balanced genomes in linear time”, Algorithms for Molecular Biology, vol. 12, 2017, : 3.
Rubert, D., Feijão, P., Dias Vieira Braga, M., Stoye, J., Martinez, F.H.V.: Approximating the DCJ distance of balanced genomes in linear time. Algorithms for Molecular Biology. 12, : 3 (2017).
Rubert, Diego, Feijão, Pedro, Dias Vieira Braga, Marília, Stoye, Jens, and Martinez, Fábio Henrique Viduani. “Approximating the DCJ distance of balanced genomes in linear time”. Algorithms for Molecular Biology 12 (2017): 3.
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:43Z
MD5 Prüfsumme
46aa2db63dc99fc0c8116c5eff36c4d9

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 28293275
PubMed | Europe PMC

Suchen in

Google Scholar