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