最大匹配问题的分子信标计算模型  

Molecular beacon computing model of maximum matching problem

作　　者：杨静[1] 殷志祥[1] 陈明强[2] 黄凯峰[3] 

机构地区：[1]安徽理工大学理学院,安徽淮南232001 [2]安徽理工大学化学工程学院,安徽淮南232001 [3]淮南职业技术学院信息与电气系,安徽淮南232001

出　　处：《合肥工业大学学报（自然科学版）》2013年第11期1400-1403,共4页Journal of Hefei University of Technology：Natural Science

基　　金：国家自然科学基金资助项目(61170172);安徽省优秀青年人才基金资助项目(2011SQRL198)

摘　　要：目前利用DNA计算求解图与组合优化中探索和开发新的分子结构是研究的一个热点,而分子信标具有结构简单、灵敏度高、易于检测及反应迅速等优点。最大匹配问题是一个著名的NP-完全问题,文章利用分子信标给出最大匹配问题的DNA计算模型。该模型具有编码简单、耗材低、空间利用率高、操作时间短及易于检测等特点,同时拓展了DNA计算解决问题的方法和应用领域。It is a research hot topic in the exploration and development of new molecules of DNA com-puting to solve combinatorial optimization problems. Molecular beacon has the advantages of simple structure, high sensitivity, easy detection and rapid response and so on. Maximum matching problem is a famous NP-complete fully problem. In this paper, DNA computing model is given by using molec- ular beacons to solve the maximum matching problem. This model has the characteristics like simple encoding, low supplies, high space utilization ratio and short operating time and it is easy to detect. The model expands the methods of DNA computing to solve the problems and the field of application.

关 键 词：DNA计算 分子信标 最大匹配 NP-完全问题 分子信标探针 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]