Simple approximation algorithm for nonoverlapping local alignments
Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan · 2002
Abstract We consider the following problem motivated by applications to nonoverlapping local alignment problems in computational molecular biology: we are a given a set of n positively weighted axis parallel rectangles such that, for each axis, the projection of a rectangle on this axis does not enclose that of another, and our goal is to select a subset of independent rectangles from the given set of rectangles of total maximum weight, where two rectangles are independent provided for each axis, the projection of one rectangle does not overlap that of another. We use the two-phase technique of [3] to provide a simple approximation algorithm for this problem that runs in O(n log n) time with a worstcase performance ratio of 3. We also discuss extension and analysis of the algorithm in d dimensions.