TY - GEN
T1 - An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
AU - Li, Zhong
AU - Goebel, Randy
AU - Wang, Lusheng
AU - Lin, Guohui
PY - 2011
Y1 - 2011
N2 - 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 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 sequential amortization.
AB - 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 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 sequential amortization.
KW - approximation algorithm
KW - Maximal strip recovery
KW - sequential amortized analysis
UR - http://www.scopus.com/inward/record.url?scp=79957938542&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-79957938542&origin=recordpage
U2 - 10.1007/978-3-642-21204-8_9
DO - 10.1007/978-3-642-21204-8_9
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783642212031
T3 - Lecture Notes in Computer Science
SP - 46
EP - 57
BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
A2 - Atallah, Mikhail
A2 - Li, Xiang-Yang
A2 - Zhu, Binhai
T2 - 5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management (FAW-AAIM 2011)
Y2 - 28 May 2011 through 31 May 2011
ER -