允许长度估计误差的SBH最优重构问题及其算法  

A RECONSTRUCTION ALGORITHM TO DNA SEQUENCING BY HYBRIDIZATION WITH TARGET DNA LENGTH ERROR

作　　者：张继红[1] 吴凌云[2] 章祥荪[2] 

机构地区：[1]清华大学经济管理学院,北京100084 [2]中国科学院数学与系统科学研究院,北京100080

出　　处：《应用数学学报》2005年第3期385-395,共11页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(10471141);博士后科学基金资助项目

摘　　要：本文讨论了允许长度估计误差和杂交错误的更实际SBH(Sequencing by Hybridization)最优重构问题.通过对SBH谱集中k-tuple之间的相关信息的分析和最优重构性质的讨论,我们得到若干非最优解的删除法则和最优解的判定法则,并获得了一个能够极大地减少最优解重构随意性的动态规划计算方法.由此,我们给出了该SBH问题的一个新重构算法.该算法既允许SBH谱集含有一般杂交实验中可能出现的探针错配所产生的正错误,也允许目标DNA序列长度有估计误差,所以本文的算法具有更一般的适应性和实用性.模拟计算结果表明我们的算法也是十分有效的(即使在谱集有多达100%的正错误情况).The problem addressed in this paper is concerned with DNA sequencing by hybridization （i.e. SBH）, in which the estimate error of target DNA length and errors of hybridization are allowed. Based on the analysis of information provided by SBH experiments and the discussion of optimal reconstruction properties, some criterions which can delete nonoptimal solutions and determine optimal solutions are obtained,and a dynamic programming method assembling optimal reconstructions of the target DNA is also given. From this, a new algorithm for solving the SBH problem is proposed by us. This algorithm accepts additional errors in SBH＇s spectrum resulting from the hybridization experiment and the estimate error of target DNA length, and can greatly reduces ambiguities in the reconstruction of DNA sequencing. Therefore, the proposed algorithm behaves well, which is also shown in our computational experiments.

关 键 词：SBH杂交测序(Sequencing by Hybridization) 最优解 正错误 最优重构 目标DNA长度估计误差 动态规划 

分 类 号：O221.3[理学—运筹学与控制论] Q811.4[理学—数学]