Computational Problems in Physical Mapping and Sequencing

这个项目是对染色体DNA物理制图和测序中出现的一些计算问题的研究。该项目的目标是：(1)研究这些计算的某些部分的新策略，旨在提高速度和/或减少所需专家干预的数量，同时保持解决方案的质量；(2)为现有的映射和测序系统添加新功能。贯穿整个项目的一个普遍主题是在计算中考虑实验误差。对物理图谱的研究主要集中在华盛顿大学分子生物技术系使用的一种方法上，即多重完全文摘图谱。在该方法的图谱组装阶段，正在研究新的算法，以确定包含克隆载体的克隆片段，确定哪些克隆片段来自被绘制的目标DNA上的相同片段，确定成对克隆重叠的概率，以及其他相关问题。此外，该项目还包括研究物理制图中的一般放置问题，一种无需制图的测序方法，以及实验误差对分子计算的影响。主要研究人员将利用他们在算法设计和分析方面的经验，为这些生物学问题的计算方面建立一个严格的基础。这可能反过来对所使用的实验方法产生直接影响。

This project is an investigation into some computational problems that arise in the physical mapping and sequencing of chromosomal DNA. The goals of the project are (1) to investigate new strategies for certain parts of these computations, aimed at improving speed and/or reducing the amount of expert intervention required, while preserving solution quality, and (2) to add new capabilities to existing mapping and sequencing systems. A pervasive theme throughout the project is to take experimental error into account in the computations. The investigation into physical mapping concentrates largely on one method in use at the University of Washington's Department of Molecular Biotechnology, namely Multiple Complete Digest mapping. Within the map assembly stage of this method, new algorithms are being investigated for identifying the clone fragment containing the cloning vector, determining which clone fragments arise from identical fragments on the target DNA being mapped, determining the probability of pairwise clone overlap, and other related problems. In addition, the project includes investigations into a general placement problem in physical mapping, a method of sequencing without mapping, and the effects of experimental error on molecular computation. The principal investigators will use their experience in algorithm design and analysis to help establish a rigorous foundation for the computational aspects of these biological problems. This may in turn result in direct impact on the experimental methods used.