DIMACS Seminar on Math and CS in Biology


How Hard is the Integration of Physical Maps?


Ron Shamir
Department of Computer Science
School of Mathematics
Tel Aviv University


CoRE Building, Conference Room 433
Busch Campus, Rutgers University


11:00 AM
Thursday, February 29, 1996


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