Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles)
journal contributionposted on 01.11.2011 by Vineet Bafna, Babu Narayanan, Ramamoorthi Ravi
Any type of content formally published in an academic journal, usually following a peer-review process.
We consider the following problem motivated by an application in computational molecular biology. We are given a set of weighted axis-parallel rectangles such that for any pair of rectangles and either axis, the projection of one rectangle does not enclose that of the other. Define a pair to be independent if their projections in both axes are disjoint. The problem is to find a maximum-weight independent subset of rectangles. We show that the problem is NP-hard even in the uniform case when all the weights are the same. We analyze the performance of a natural local-improvement heuristic for the general problem and prove a performance ratio of 3.25. We extend the heuristic to the problem of finding a maximum-weight independent set in (d + 1)-claw-free graphs, and show a tight performance ratio of d − 1 + 1/d. A performance ratio of d/2 was known for the heuristic when applied to the uniform case. Our contributions are proving the hardness of the problem and providing a tight analysis of the local-improvement algorithm for the general weighted case.