DAD计算中的遍历理论模型及算法  

Transversal Theoretic Model with Its Algorithm in DNA Computing

作　　者：李书超[1] 许进[1] 刘光武[1] 李维德[2] 

机构地区：[1]华中科技大学控制科学与工程系 [2]兰州大学数学系,兰州730000

出　　处：《计算机工程与应用》2003年第13期19-21,28,共4页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(编号:60103021);教育部科学技术重点研究项目(编号:02139)

摘　　要：该文源于DNA序列杂交先后顺序的工程计算问题。在杂交先后顺序(SHB)问题中,人们试图想通过首先确定在一个很长的DNA字符串S中出现的k-长子串来了解整个原始的字符串S,通过研究k-长子串的重叠模式来重新构造原始的字符串S。该文将SHB问题转化为具体的图论问题。根据图及其线图的关系,部分解决了上述SHB问题的等价形式,即在有向线图顶点的入度和出度不超过2的情形下,用遍历理论为SHB问题建立了数学模型,从而能在多项式时间内找到有向线图的哈密顿路或圈。文章最后,指出了须进一步研究的问题。This work grews out of a computational problem that arises in a technology called DNA sequencing by hybrdization(SBH).In sequencing,by hybridization,one attempts to lean the entire sequence of a long DNA string S by first determining which k-length substrings occur in S.Through investigating the overlap patterns of the k-length substrings,one can reconstruct the original string.Our method in this paper is to transform the SHB problem into the graph theory problem,which is concrete and clear.With the relationship between graph and its line-graph,writers exploit the mathematical model of transversal theory for SHB.They set up the algorithm to obtain the optimal solution for the Hamiltonian path(or tour ),which is for the case that every node's out-degree and in-degree no less than2,it is also the equivalent form for the BSH problem.The paper analyzes the complexity for the algorithm,at the end it gives problem for further explorting.

关 键 词：DNA计算 杂交先后顺序 遍历理论 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]