PSBH中的组合优化问题及其计算方法

A RECONSTRUCTION ALGORITHM TO SOLVE POSITIONAL SEQUENCING BY HYBRIDIZATION

本文介绍了具有部分位置信息的SBH杂交测序（Positional Sequencing by Hy-bridization,简称PSBH）实验所产生的一个重构DNA片断的组合优化问题,并讨论了该问题最优重构的计算问题.通过对PSBH提供的谱集及其位置信息的分析处理,我们获得了若干判定最优重构片断头尾的分支定界准则以及确定其非头尾位置最可能出现k-tuple的动态规划计算方法,并由此给出了该PSBH问题的一个新重构算法.该算法允许PSBH谱集含有一般杂交实验中常常可能出现探针错配所产生的正错误,并且仅仅假设PSBH的谱集、位置信息和位置长度是已知的,所以我们的算法具有更一般的适应性和实用性.此外,由于我们给出的算法能够极大地利用PSBH的谱集和位置信息所蕴含的信息确定最优重构片断头尾及其中间位置最可能出现的k-tuple,极大地减少了PSBH重构中的随意性,所以我们的算法也是有效的,模拟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.