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

摘要

该文源于DNA序列杂交先后顺序的工程计算问题.在杂交先后顺序(SHB)问题中,人们试图想通过首先确定在一个很长的DNA字符串S中出现的k-长子串来了解整个原始的字符串S,通过研究k-长子串的重叠模式来重新构造原始的字符串S.该文将SHB问题转化为具体的图论问题.根据图及其线图的关系,部分解决了上述SHB问题的等价形式,即在有向线图顶点的入度和出度不超过2的情形下,用遍历理论为SHB问题建立了数学模型,从而能在多项式时间内找到有向线图的哈密顿路或圈.文章最后,指出了须进一步研究的问题.