Format

Send to

Choose Destination
BMC Bioinformatics. 2018 May 8;19(Suppl 6):152. doi: 10.1186/s12859-018-2130-5.

Computing the family-free DCJ similarity.

Author information

1
Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS, Brazil.
2
Faculty of Technology and Center for Biotechnology (CeBiTec), Bielefeld University, Bielefeld, Germany.
3
Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS, Brazil. fhvm@facom.ufms.br.

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.

KEYWORDS:

Double-cut-and-join; Family-free genomic similarity; Genome rearrangement

PMID:
29745861
PMCID:
PMC5998916
DOI:
10.1186/s12859-018-2130-5
[Indexed for MEDLINE]
Free PMC Article

Supplemental Content

Full text links

Icon for BioMed Central Icon for PubMed Central
Loading ...
Support Center