### Graph-theoretic support for
physical mapping of DNA

**Ron Shamir**
Computer Science Department

Tel Aviv University, Tel Aviv, Israel

Physical maps of DNA are an essential tool in molecular biology and in
the Human Genome Project. Like geographical maps, they help in
navigating through enormously complex unfamiliar terrain. In this talk
we discuss some algorithmic problems which arise in the construction
of physical maps. Our analysis uses tools from graph theory and
complexity.

We introduce several models and analyze the computational difficulty
of constructing the best map under each of these models. Simple,
error-free models of the problem have computationally easy
solutions. More realistic models, allowing errors and incomplete
information, turn out to be intractable. However, we shall show that
by imposing more realistic biological constraints the problem becomes
polynomial.

If time allows, we shall also discuss some heuristic approaches, and
describe an ongoing mapping project (joint with Y. Shiloh, TAU school
of medicine) of a segment of Chromosome 11 containing the
Ataxia-Telangiectasia gene(s).

Parts of the talk are joint work with M. C. Golumbic (Bar-Ilan) and H.
Kaplan (Princeton)

Program

DIMACS Homepage

Contacting the Center

Document last modified on March 28, 2000.