On the approximability of the exemplar adjacency number problem for genomes with gene repetitions
Full Text: 1-s2.0-S0304397514005416-main.pdf
In this paper, we apply a measure, exemplar adjacency number, which complements and extends the well-studied breakpoint distance between two permutations, to measure the similarity between two genomes (or in general, between any two sequences drawn from the same alphabet). For two genomes and drawn from the same set of n gene families and containing gene repetitions, we consider the corresponding Exemplar Adjacency Number problem (EAN), in which we delete duplicated genes from and such that the resultant exemplar genomes (permutations) G and H have the maximum adjacency number. We obtain the following results. First, we prove that the one-sided 2-repetitive EAN problem, i.e., when one of and is given exemplar and each gene occurs in the other genome at most twice, can be linearly reduced from the Maximum Independent Set problem. This implies that EAN does not admit any -approximation algorithm, for any , unless P = NP. This hardness result also implies that EAN, parameterized by the optimal solution value, is W[1]-hard. Secondly, we show that the two-sided 2-repetitive EAN problem has an -approximation algorithm, which is tight up to a constant factor.
Citation
Z. Chen, B. Fu, R. Goebel, G. Lin, W. Tong, J. Xu, B. Yang, Z. Zhao, B. Zhu. "On the approximability of the exemplar adjacency number problem for genomes with gene repetitions". Theoretical Computer Science, 550, pp 59-65, September 2014.| Keywords: | Genome comparison, Adjacency, Breakpoint, NP-hard, Approximation algorithm |
| Category: | In Journal |
| Web Links: | DOI |
| Elsevier |
BibTeX
@article{Chen+al:14,
author = {Zhixiang Chen and Bin Fu and Randy Goebel and Guohui Lin and
Weitian Tong and Jinhui Xu and Boting Yang and Zhiyu Zhao and Binhai Zhu},
title = {On the approximability of the exemplar adjacency number problem for
genomes with gene repetitions},
Volume = "550",
Pages = {59-65},
journal = {Theoretical Computer Science},
year = 2014,
}Last Updated: February 13, 2020Submitted by Sabina P
