An improved approximation algorithm for the complementary maximal strip recovery problem
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 720-730 |
| Journal / Publication | Journal of Computer and System Sciences |
| Volume | 78 |
| Issue number | 3 |
| Online published | 29 Oct 2011 |
| Publication status | Published - May 2012 |
Link(s)
Abstract
Given two genomic maps G1 and G2 each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G1 and G2 such that the resultant subsequences, denoted as G1* and G2*, can be partitioned into the same set of maximal strips, which are common substrings of length greater than or equal to two. The complementary maximal strip recovery (CMSR) problem has the complementary goal to delete the minimum number of markers. Both MSR and CMSR have been shown to be NP-hard and APX-complete, and they admit a 4-approximation and a 3-approximation respectively. In this paper, we present an improved 7/3-approximation algorithm for the CMSR problem, with its worst-case performance analysis done through a local amortization with a re-weighting scheme.
Research Area(s)
- Approximation algorithm, Local amortized analysis, Maximal strip recovery, Re-weighting scheme
Citation Format(s)
An improved approximation algorithm for the complementary maximal strip recovery problem. / Lin, Guohui; Goebel, Randy; Li, Zhong et al.
In: Journal of Computer and System Sciences, Vol. 78, No. 3, 05.2012, p. 720-730.
In: Journal of Computer and System Sciences, Vol. 78, No. 3, 05.2012, p. 720-730.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
