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 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 studi

SUBMITTER: Rubert DP 

PROVIDER: S-EPMC5998916 | biostudies-literature | 2018 May

REPOSITORIES: biostudies-literature