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