Computing the family-free DCJ similarity

Rubert D, Hoshino EA, Dias Vieira Braga M, Stoye J, Martinez FHV (2018)
BMC Bioinformatics 19(Suppl. 6): 152.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
OA 1.62 MB
Abstract / Bemerkung
Background The genomic similarity is a large-scale measure for comparing two given genomes. In this work we study the (NP-hard) problem of computing the genomic similarity under the DCJ model in a setting that does not assume that the genes of the compared genomes are grouped into gene families. This problem is called family-free DCJ similarity. Results We propose an exact ILP algorithm to solve the family-free DCJ similarity problem, then we show its APX-hardness and present four combinatorial heuristics with computational experiments comparing their results to the ILP. Conclusions We show that the family-free DCJ similarity can be computed in reasonable time, although for larger genomes it is necessary to resort to heuristics. This provides a basis for further studies on the applicability and model refinement of family-free whole genome similarity measures.
Stichworte
Genome rearrangement; Double-cut-and-join; Family-free genomic similarity
Erscheinungsjahr
2018
Zeitschriftentitel
BMC Bioinformatics
Band
19
Ausgabe
Suppl. 6
Art.-Nr.
152
ISSN
1471-2105
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/2919006

Zitieren

Rubert D, Hoshino EA, Dias Vieira Braga M, Stoye J, Martinez FHV. Computing the family-free DCJ similarity. BMC Bioinformatics. 2018;19(Suppl. 6): 152.
Rubert, D., Hoshino, E. A., Dias Vieira Braga, M., Stoye, J., & Martinez, F. H. V. (2018). Computing the family-free DCJ similarity. BMC Bioinformatics, 19(Suppl. 6), 152. doi:10.1186/s12859-018-2130-5
Rubert, D., Hoshino, E. A., Dias Vieira Braga, M., Stoye, J., and Martinez, F. H. V. (2018). Computing the family-free DCJ similarity. BMC Bioinformatics 19:152.
Rubert, D., et al., 2018. Computing the family-free DCJ similarity. BMC Bioinformatics, 19(Suppl. 6): 152.
D. Rubert, et al., “Computing the family-free DCJ similarity”, BMC Bioinformatics, vol. 19, 2018, : 152.
Rubert, D., Hoshino, E.A., Dias Vieira Braga, M., Stoye, J., Martinez, F.H.V.: Computing the family-free DCJ similarity. BMC Bioinformatics. 19, : 152 (2018).
Rubert, Diego, Hoshino, Edna A., Dias Vieira Braga, Marília, Stoye, Jens, and Martinez, Fábio Henrique Viduani. “Computing the family-free DCJ similarity”. BMC Bioinformatics 19.Suppl. 6 (2018): 152.
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:58Z
MD5 Prüfsumme
e44aedab4664f12c505e2879fa252729

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 29745861
PubMed | Europe PMC

Suchen in

Google Scholar