摘要
基于最佳匹配问题的问题解空间,采用荧光标记的策略,给出了一种新的最佳匹配问题的DNA表面计算模型,该模型首先将问题解空间的DNA分子固定在固体载体上,然后通过进行相应的生化反应来求得最佳匹配问题的所有解.与已有的最大匹配问题的DNA表面计算模型相比,新模型在检测边的过程中不需要使用观察法,且边的排列顺序不影响解空间的生成过程.因此,新模型具有更好的性能.
Using the method of fluorescence labeling, a new DNA algorithm of the perfect matching problem based surface is presented in this paper. By fixing the DNA molecules of the solution space on the solid carrier, all solutions of the perfect matching problem by the biochemical actions can be acquired. Compared with other surface-based DNA algorithms for maximal matching problem, this algorithm can precisely get the edges existing in any perfect matching without using observation, and the edge order hasn't influence on the solution generating process. Therefore, the new algorithm can get better performance.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2005年第7期1241-1246,共6页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60272051)
湖南省自然科学基金项目(03JJY3908)
关键词
DNA计算
解空间
最大匹配
最佳匹配问题
DNA computing
solution space
maximum matching
perfect matching problem
