On the Approximability of Comparing Genomes with Duplicates

Details On the Approximability of Comparing Genomes with Duplicates On the Approximability of Comparing Genomes with Duplicates

2008-06-06

arxiv.org/abs/0806.1103v1

Biology

Quantitative Biology

Quantitative Methods

Scientific paper

A central problem in comparative genomics consists in computing a (dis-)similarity measure between two genomes, e.g. in order to construct a phylogeny. All the existing measures are defined on genomes without duplicates. However, we know that genes can be duplicated within the same genome. One possible approach to overcome this difficulty is to establish a one-to-one correspondence (i.e. a matching) between genes of both genomes, where the correspondence is chosen in order to optimize the studied measure. In this paper, we are interested in three measures (number of breakpoints, number of common intervals and number of conserved intervals) and three models of matching (exemplar, intermediate and maximum matching models). We prove that, for each model and each measure M, computing a matching between two genomes that optimizes M is APX-hard. We also study the complexity of the following problem: is there an exemplarization (resp. an intermediate/maximum matching) that induces no breakpoint? We prove the problem to be NP-Complete in the exemplar model for a new class of instances, and we show that the problem is in P in the maximum matching model. We also focus on a fourth measure: the number of adjacencies, for which we give several approximation algorithms in the maximum matching model, in the case where genomes contain the same number of duplications of each gene.

Affiliated with

Also associated with

No associations

Rating

On the Approximability of Comparing Genomes with Duplicates does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Approximability of Comparing Genomes with Duplicates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Approximability of Comparing Genomes with Duplicates will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-172266