# DIMACS Seminar on Math and CS in Biology

## Title:

Nonoverlapping Local Alignments (Weighted independent sets of axis-parallel rectangles)

## Speaker:

- Dr. Vineet Bafna
- DIMACS

## Place:

- Room 402, Computer Science Building
- 35 Olden Street, Princeton University.

## Time:

- 3:00 PM
- Monday, February 20, 1995

## Abstract:

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 and either axis, the
projection of one rectangle on the axis 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 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 + \frac{1}{d}$. A performance ratio
of $\frac{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.

This is joint work with Babu Narayanan and R. Ravi.

Future speakers

Feb 27: Dr. Laszlo Szekely

March 6: Dr. Robert Vrijenhoek

dimacs-www@dimacs.rutgers.edu
Document last modified on February 17, 1995