One subspecialty of computational biology that has seen minimal participation by computer scientists is disease gene hunting. This may be because it is hard to get data and the problems appear to be more statistical than combinatorial. Nevertheless, successful disease gene hunting depends on carrying out various difficult computations on family trees also known as pedigrees, which can be usefully viewed as graphs. When the families come from an inbred population the pedigree graphs are directed acyclic graphs, but not trees, and the computations get more interesting from an algorithmic perspective. I will explain a variety of combinatorial problems that arise in analyzing pedigree graphs to find the approximate chromosomal location of disease causing genes. Three of these problems can be cast as special cases of minimum vertex feedback set, single sorce shortest paths, and Steiner tree, which are well known to algorithmicists. Other pedigree graph problems may not be special cases of well-known algorithms problems, but I hope to convince you that algorithmicists may contribute to better solutions.

Includes joint work with Richa Agarwala (NIH), Leslie Biesecker (NIH), Ann Becker (Technion), and Dan Geiger (Technion).

Contact: Vincenzo Liberatore (liberato@umiacs.umd.edu)

The Capital Area Theory Symposia is an NSF sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department and UMIACS. NSF support under grant CCR-9732907 is gratefully acknowledged

ÿ