Details

Autor(en) / Beteiligte

• Chen, Zhixiang
• Fowler, Richard H
• Fu, Bin
• Zhu, Binhai

Titel

Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem of Genomes

Ist Teil von

• Computing and Combinatorics, 2006, Vol.4112, p.245-254

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2006

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• In this paper we present several lower bounds on the approximation of the exemplar conserved interval distance problem of genomes. We first prove that the exemplar conserved interval distance problem cannot be approximated within a factor of clogn for some constant c>0 in polynomial time, unless P=NP. We then prove that it is NP-complete to decide whether the exemplar conserved interval distance between any two sets of genomes is zero or not. This result implies that the exemplar conserved interval distance problem does not admit any approximation in polynomial time, unless P=NP. In fact, this result holds even when a gene appears in each of the given genomes at most three times. Finally, we strengthen the second result under a weaker definition of approximation (which we call weak approximation). We show that the exemplar conserved interval distance problem does not admit a weak approximation within a factor of m, where m is the maximum length of the given genomes.