Physical Mapping: Models, Complexities, and Algorithms

本计划探讨新发展的图论模型及其与分子生物学问题的联系。分子生物学研究的基本挑战之一是构建基因组的物理图谱。为了研究一长段连续的DNA，物理制图首先是在基因组的特定位置将DNA切割成相对较小的片段，称为克隆。物理映射的目标是沿着一条线（DNA的线性链）以间隔排列片段，以便它们的成对交叉点与实验数据相匹配。为了开发构建地图的算法，引入了标记探针间隔图（TPIG）模型，该模型在一些克隆被放射性标记时出现。TPIG模型是对探针间隔图（probe interval graph， PIG）模型的改进，用于DNA物理映射。对现有算法进行改进，得到了具有预先划分探针和非探针的猪和t猪线性时间识别算法。对于未分割版本，研究了识别问题是否多项式时间可解的复杂性。还将开发在存在错误时具有鲁棒性的启发式算法。最后，介绍了概率模型，并将这些模型作为理论框架，对所选算法进行平均案例分析。该项目还将促进教学、培训和学习。通过向学生展示数学建模和算法分析如何成功地应用于生物学领域，PI旨在吸引更多的学生享受数学思维，以及他们遇到的问题的图论建模，并欣赏数学和理论计算机科学可以添加到他们工作中的强大而有趣的方面。这也是PI对德雷塞尔大学正在进行的新的跨学科生物信息学项目的主要贡献。

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.