Physical Mapping: Models, Complexities, and Algorithms

物理映射：模型、复杂性和算法

• 批准号: 0311413
• 负责人: Li Sheng
• 金额: $ 9万
• 依托单位: Drexel University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-07-01 至 2007-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0311413&HistoricalAwards=false
• 关键词: Physical; Mapping; Models; Complexities; Algorithms

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.

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