可满足性问题的巨磁电阻型DNA计算模型  

The DNA Computation Model Based on Giant Magnetoresistance for SAT Problem

作　　者：肖建华[1] 许进[2] 

机构地区：[1]南开大学现代物流研究中心,天津300071 [2]北京大学信息科学技术学院,北京100871

出　　处：《计算机学报》2013年第4期829-835,共7页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2009AA01Z413);国家自然科学基金(60903105;61033003;60910002);中央高校基本科研业务费专项资金项目(NKZXB1110)资助~~

摘　　要：DNA计算是一种新的计算模式,因其海量的信息存储能力、高度的并行性及低能耗等优点而被广泛地应用于求解各类NP完全问题.文中利用免疫磁标记和巨磁电阻(GMR)效应,对生物特异性反应进行检测,构建了可满足性问题的巨磁电阻型DNA计算模型,并用实例说明了模型的有效性和可行性.与传统的荧光标记法DNA计算模型相比,巨磁电阻型DNA计算模型的输出结果是电信号形式,因而具有检测信号易处理、检测时间短、解可靠性高、无需标记和读解简单等优点.DNA computing is a new computation vista,which has been extensively used to solve various NP-complete problems because of many good characteristics,such as huge storage density,exceptional energy efficiency and massive parallelism.In the paper,the immunomagnetic mark and the GMR effect are employed to capture the specific hybridization,and a new DNA computation model based on giant magnetoresistance is proposed to solve the satisfiability problem.Furthermore,the validity and feasibility of the model is explained with an example.Compared with the traditional fluorescence-based DNA computation,the output of the GMR DNA computation is the electric signal,and has more significant advantages,such as conveniently processing information,time-saving detection,the high reliability,label-free feature,and easy solution detection.

关 键 词：可满足性问题 DNA计算模型 巨磁电阻效应 DNA计算机 

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