Computational Problems in Physical Mapping and Sequencing

点击翻译按钮获取中文摘要

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.