On the Tractability of Maximal Strip Recovery

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

15 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)907-914
Journal / PublicationJournal of Computational Biology
Issue number7
Publication statusPublished - Jul 2010


Given two genomic maps G and H represented by a sequence of n gene markers, a strip (syntenic block) is a sequence of distinct markers of length at least two which appear as subsequences in the input maps, either directly or in reversed and negated form. The problem Maximal Strip Recovery (MSR) is to find two subsequences G' and H' of G and H, respectively, such that the total length of disjoint strips in G' and H' is maximized (or, conversely, the number of markers hence deleted, is minimized). Previously, several heuristic algorithms which work well in practice, have been proposed. Theoretically, a factor-4 polynomial-time approximation is known for the MSR problem. Moreover, several close variants of MSR, MSR-d (with d>2 input maps), MSR-DU (with marker duplications) and MSR-WT (with markers weighted) have been proved to be NP-complete. Before this work, the complexity of the original MSR problem was left open. In this article, we solve the open problem by showing that MSR is NP-complete, using a polynomial time reduction from One-in-Three 3SAT. We also present some fixed-parameter tractable algorithms for the (complement of) MSR problem and its variants. Let k be the minimum number of markers deleted in an optimal solution. The running time of our algorithms are O(23.61kn+n2) for MSR, O((2d+1)k/k) dn+dn2) for MSR-d, and O(27.22kn+n2) for MSR-DU, respectively.

Research Area(s)

  • alignment, combinatorial optimization, dynamic programming, genomic rearrangements, haplotypes

Citation Format(s)

On the Tractability of Maximal Strip Recovery. / WANG, LUSHENG; ZHU, BINHAI.
In: Journal of Computational Biology, Vol. 17, No. 7, 07.2010, p. 907-914.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review