摘要
改进的DNA粘贴模型在解决SAT问题时所需的寡核苷酸片段数量有显著降低,对改进的粘贴模型做了进一步的改进,建立了图最大独立集的一种改进的DNA粘贴模型。首先将图的独立集问题转化为可满足性问题,然后利用本文改进的粘贴模型给出了图的最大独立集的DNA算法。最后通过一个实例给出算法实现并求出了最大独立集。
The number of short oligonucletides needed in solving satisfiability problem is decreased obviously with the modified DNA sticker model. In this paper, the model was modified again and a modified DNA sticker model for maximum independent set of graph was built. First, we converted maximum independent sets of graph to satisfiability problem, then, the DNA algorithm for maximum independent sets of graph was given based on our modified sticker model. The biochemical procedures were illustrated through an instance and the maximum independent sets of the graph were got consequently.
出处
《山东科技大学学报（自然科学版）》
CAS
2008年第4期57-59,98,共4页
Journal of Shandong University of Science and Technology(Natural Science)
基金
国家自然科学基金项目(60503002)
中国博士后科学基金项目(20060400344)
关键词
DNA计算
粘贴模型
NP完全问题
图的最大独立集
DNA computing
sticker model
NP-complete problem
maximum independent set of graph
