TY - JOUR AB - 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. DA - 2018 DO - 10.1186/s12859-018-2130-5 KW - Genome rearrangement KW - Double-cut-and-join KW - Family-free genomic similarity LA - eng IS - Suppl. 6 PY - 2018 SN - 1471-2105 T2 - BMC Bioinformatics TI - Computing the family-free DCJ similarity UR - https://nbn-resolving.org/urn:nbn:de:0070-pub-29190063 Y2 - 2024-11-22T00:54:11 ER -