Computing the family-free DCJ similarity
Abstract 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 fami...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2018-05-01
|
| Series: | BMC Bioinformatics |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s12859-018-2130-5 |
| _version_ | 1811239792328835072 |
|---|---|
| author | Diego P. Rubert Edna A. Hoshino Marília D. V. Braga Jens Stoye Fábio V. Martinez |
| author_facet | Diego P. Rubert Edna A. Hoshino Marília D. V. Braga Jens Stoye Fábio V. Martinez |
| author_sort | Diego P. Rubert |
| collection | DOAJ |
| description | Abstract 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. |
| first_indexed | 2024-04-12T13:07:23Z |
| format | Article |
| id | doaj.art-a77b39417949404393504d35df9e3ccf |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-04-12T13:07:23Z |
| publishDate | 2018-05-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-a77b39417949404393504d35df9e3ccf2022-12-22T03:32:00ZengBMCBMC Bioinformatics1471-21052018-05-0119S6314210.1186/s12859-018-2130-5Computing the family-free DCJ similarityDiego P. Rubert0Edna A. Hoshino1Marília D. V. Braga2Jens Stoye3Fábio V. Martinez4Faculdade de Computação, Universidade Federal de Mato Grosso do SulFaculdade de Computação, Universidade Federal de Mato Grosso do SulFaculty of Technology and Center for Biotechnology (CeBiTec), Bielefeld UniversityFaculty of Technology and Center for Biotechnology (CeBiTec), Bielefeld UniversityFaculdade de Computação, Universidade Federal de Mato Grosso do SulAbstract 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.http://link.springer.com/article/10.1186/s12859-018-2130-5Genome rearrangementDouble-cut-and-joinFamily-free genomic similarity |
| spellingShingle | Diego P. Rubert Edna A. Hoshino Marília D. V. Braga Jens Stoye Fábio V. Martinez Computing the family-free DCJ similarity BMC Bioinformatics Genome rearrangement Double-cut-and-join Family-free genomic similarity |
| title | Computing the family-free DCJ similarity |
| title_full | Computing the family-free DCJ similarity |
| title_fullStr | Computing the family-free DCJ similarity |
| title_full_unstemmed | Computing the family-free DCJ similarity |
| title_short | Computing the family-free DCJ similarity |
| title_sort | computing the family free dcj similarity |
| topic | Genome rearrangement Double-cut-and-join Family-free genomic similarity |
| url | http://link.springer.com/article/10.1186/s12859-018-2130-5 |
| work_keys_str_mv | AT diegoprubert computingthefamilyfreedcjsimilarity AT ednaahoshino computingthefamilyfreedcjsimilarity AT mariliadvbraga computingthefamilyfreedcjsimilarity AT jensstoye computingthefamilyfreedcjsimilarity AT fabiovmartinez computingthefamilyfreedcjsimilarity |