This project explores newly developed graph theoretic models and their connections to problems of molecular biology. One of the fundamental challenges in molecular biology research is to construct physical maps of a genome. In order to study a long contiguous segment of DNA, physical mapping starts by cutting DNA into relatively small fragments, called clones, at certain specific locations on the genome. The goal of physical mapping is to arrange the segments as intervals along a line (the linear chain of DNA), so that their pairwise intersections match the experimental data. To develop algorithms to construct maps, a tagged probe interval graph (TPIG) model has been introduced, which arises when some of the clones are radioactively labeled. The TPIG model is a refinement of the probe interval graph (PIG) model introduced for the DNA physical mapping.
Improvements upon the existing algorithms are sought to get linear time recognization algorithms for both PIGs and TPIGs that have predefined partition of probes and nonprobes. For the unpartitioned version, the complexity of whether or not the recognization problem is polynomial time solvable is studied. Heuristic algorithms that are robust in the presence of error will also be developed. Finally, probabilistic models are introduced and, using these models as a theoretical framework, average case analyses for selected algorithms will be investigated.
The project will also promote teaching, training, and learning. By showing students how mathematical modeling and algorithm analysis has been successfully applied to the field of biology, the PI intends to attract more students to enjoy mathematical thinking, and graph theory modeling for problems they encounter, and to appreciate the powerful and interesting aspect that mathematics and theoretical computer science can add to their work. This is also a major contribution of the PI to the new interdisciplinary bioinfomatics program that is underway at Drexel University.
