Abstract
The article, “On the Tractability of Maximal Strip Recovery,” by Lusheng Wang and Binhai Zhu, Journal of Computational Biology July 2010; 17(7):907–914 (doi: 10.1089/cmb.2009.0084), contained an error, which the authors address here:
The FPT algorithm proposed in Section 3 (pages 912–913) is for the complement of MSR (now called CMSR), which is a minimization problem. The algorithm on pages 912–913 is based on an erroneous Lemma 1 and hence is incorrect.
Lemma 1 can be easily fixed by replacing a length-2 maximal common substring (or its signed reversal) in G1 and G2 by a length-4 one. Based on this new, fixed lemma, it is possible to have a new FPT algorithm that runs in O(3kn2) time (in fact, faster than the FPT algorithm on pages 912–913).
This correction is presented in the results of another paper, “Exact and Approximation Algorithms for the Complementary Maximal Strip Recovery Problem,” recently accepted by Journal of Combinatorial Optimization (Jiang, H., Li, Z., Lin, G., Wang, L., and Zhu, B., to appear, 2011).