Computing the family-free DCJ similarity

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

Download
OA 1.62 MB
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Autor
; ; ; ;
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.
Erscheinungsjahr
Zeitschriftentitel
BMC Bioinformatics
Band
19
Zeitschriftennummer
Suppl. 6
Artikelnummer
152
ISSN
Finanzierungs-Informationen
Article Processing Charge funded by the Deutsche Forschungsgemeinschaft and the Open Access Publication Fund of Bielefeld University.
PUB-ID

Zitieren

Rubert DP, Hoshino EA, Dias Vieira Braga M, Stoye J, Martinez FV. Computing the family-free DCJ similarity. BMC Bioinformatics. 2018;19(Suppl. 6): 152.
Rubert, D. P., Hoshino, E. A., Dias Vieira Braga, M., Stoye, J., & Martinez, F. V. (2018). Computing the family-free DCJ similarity. BMC Bioinformatics, 19(Suppl. 6), 152. doi:10.1186/s12859-018-2130-5
Rubert, D. P., Hoshino, E. A., Dias Vieira Braga, M., Stoye, J., and Martinez, F. V. (2018). Computing the family-free DCJ similarity. BMC Bioinformatics 19:152.
Rubert, D.P., et al., 2018. Computing the family-free DCJ similarity. BMC Bioinformatics, 19(Suppl. 6): 152.
D.P. Rubert, et al., “Computing the family-free DCJ similarity”, BMC Bioinformatics, vol. 19, 2018, : 152.
Rubert, D.P., Hoshino, E.A., Dias Vieira Braga, M., Stoye, J., Martinez, F.V.: Computing the family-free DCJ similarity. BMC Bioinformatics. 19, : 152 (2018).
Rubert, Diego P., Hoshino, Edna A., Dias Vieira Braga, Marília, Stoye, Jens, and Martinez, Fábio V. “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
2018-06-12T11:50:03Z

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