Exact and approximation algorithms for the complementary maximal strip recovery problem

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

12 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)493-506
Journal / PublicationJournal of Combinatorial Optimization
Issue number4
Publication statusPublished - May 2012


Given two genomic maps G 1 and G 2 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 G* 1 and G* 2, can be partitioned into the same set of maximal substrings of length greater than or equal to two. Such substrings can occur in the reversal and negated form. The complementary maximal strip recovery (CMSR) problem is to delete the minimum number of markers from both G 1 and G 2 for the same purpose, with its optimization goal exactly complementary to maximizing the total number of gene markers retained in the final maximal substrings. Both MSR and CMSR have been shown NP-hard and APX-hard. A 4-approximation algorithm is known for the MSR problem, but no constant ratio approximation algorithm for CMSR. In this paper, we present an O(3 kn 2)-time fixed-parameter tractable (FPT) algorithm, where k is the size of the optimal solution, and a 3-approximation algorithm for the CMSR problem. © Springer Science+Business Media, LLC. 2011.

Research Area(s)

  • Amortized analysis, Approximation algorithm, Fixed-parameter tractable