Comparing genomes with duplications: a computational complexity point of view.

Area of Science:

• Computational Biology
• Genomics
• Bioinformatics

Background:

• Comparing whole nuclear genomes frequently involves duplicated genes or genomic markers.
• Existing methods compute genomic similarity by first establishing gene correspondences and then using permutation measures.
• These methods rely on both a correspondence model and a permutation similarity measure.

Purpose of the Study:

• To investigate the computational complexity of computing genomic (dis)similarity measures.
• To analyze the complexity of establishing optimal gene correspondences under different models.
• To evaluate the complexity for specific permutation (dis)similarity measures.

Main Methods:

• The study focuses on two models for gene correspondence: the exemplar model and the matching model.
• It examines three permutation (dis)similarity measures: common intervals, maximum adjacency disruption (MAD), and summed adjacency disruption (SAD).
• Computational complexity analysis, including NP-completeness and APX-hardness, is applied.

Main Results:

• The problem of computing an optimal correspondence is NP-complete for both the exemplar and matching models.
• For the MAD and SAD measures, the problem is shown to be APX-hard.
• This indicates significant computational challenges in accurately measuring genomic similarity with duplications.

Conclusions:

• Computing optimal gene correspondences for genomic similarity is computationally intractable.
• The findings highlight the inherent difficulty in comparing genomes with duplicated elements using current approaches.
• Further research may be needed to develop more efficient algorithms or alternative comparison strategies.