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