A RECONSTRUCTION ALGORITHM TO SOLVE POSITIONAL SEQUENCING BY HYBRIDIZATION
PSBH中的组合优化问题及其计算方法

The problem addressed in this paper is concerned with positional DNA sequencing by hybridization(i.e. PSBH). On the basis of analyzing the information provided by PSBH experiments, some criteria which can determine the most possible k-tuples at the ends of optimal reconstructions of the target DNA are obtained, and a dynamic programming method determining the most possible k-tuple in the middle of optimal reconstructions of the target DNA is also given. Prom this, a new algorithm for solving PSBH problem is proposed by us. This algorithm accepts additional errors in PSBH's spectrum resulting from the hybridization experiment and can greatly reduce ambiguities in the reconstruction of DNA sequencing. Therefore, the proposed algorithm can behave well, as shown in our computational experiments.