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
Journal Article | Original Article | Published | English
Author
; ; ; ;
Abstract / Notes
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.
Publishing Year
ISSN
Financial disclosure
Article Processing Charge funded by the Deutsche Forschungsgemeinschaft and the Open Access Publication Fund of Bielefeld University.
PUB-ID

Cite this

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.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-06-12T11:50:03Z

This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 29745861
PubMed | Europe PMC

Search this title in

Google Scholar