DIMACS Seminar on Math and CS in Biology

Title:

How Hard is the Integration of Physical Maps?

Speaker:

Ron Shamir

Department of Computer Science

School of Mathematics

Tel Aviv University

Place:

CoRE Building, Conference Room 433

Busch Campus, Rutgers University

Time:

11:00 AM

Thursday, February 29, 1996

Abstract:

The mapping efforts of the human genome project will soon be changing emphasis from de-novo generation of maps into the integration of data from various existing maps into new, better and more accurate maps. In this study we address some basic problems which arise in map integration. Specifically, given clone overlap data, we study the algorithmic problems arising by the introduction of additional information on clone sizes or clone order.

We use graph-theoretic tools: Clone overlap data is modeled by an interval graph. When the additional information is order constraints on pairs of disjoint intervals, we give a linear time algorithm. Extant algorithms for this problem required quadratic time. When the constraints are bounds on distances between endpoints, and the graph admits a unique clique order, we show that the problem is linearly equivalent to network flow and hence polynomial. However, for arbitrary interval graphs, even when the lengths of all intervals are precisely predetermined, the problem is NP-complete. Side constraints on unit interval graphs will also be considered.

(Joint work with Itsik Pe'er, Tel Aviv University)

Document last modified on February 23, 1996