On the inapproximability of the exemplar conserved interval distance problem of genomes

Zhixiang Chen (), Richard H. Fowler (), Bin Fu () and Binhai Zhu ()
Additional contact information
Zhixiang Chen: University of Texas-Pan American
Richard H. Fowler: University of Texas-Pan American
Bin Fu: University of Texas-Pan American
Binhai Zhu: Montana State University

Journal of Combinatorial Optimization, 2008, vol. 15, issue 2, No 6, 221 pages

Abstract: Abstract In this paper we present two main results about the inapproximability of the exemplar conserved interval distance problem of genomes. First, we prove that it is NP-complete to decide whether the exemplar conserved interval distance between any two 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 every gene appears in each of the given genomes at most three times. Second, we strengthen the first result under a weaker definition of approximation, called weak approximation. We show that the exemplar conserved interval distance problem does not admit any weak approximation within a super-linear factor of $\frac{2}{7}m^{1.5}$ , where m is the maximal length of the given genomes. We also investigate polynomial time algorithms for solving the exemplar conserved interval distance problem when certain constrains are given. We prove that the zero exemplar conserved interval distance problem of two genomes is decidable in polynomial time when one genome is O(log n)-spanned. We also prove that one can solve the constant-sized exemplar conserved interval distance problem in polynomial time, provided that one genome is trivial.

Keywords: Genome rearrangement; Exemplar conserved interval distance; Approximation algorithm; Inapproximability; Weak approximation (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9077-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:15:y:2008:i:2:d:10.1007_s10878-007-9077-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-007-9077-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().