基于生物芯片技术的地图四着色问题的DNA算法

基于先进的生物芯片技术、多种荧光标记技术和DNA计算理论提出了解决地图四着色问题的DNA算法,通过一个实例阐述了具体的DNA操作步骤,并对生化实验进行了计算机模拟,给出了所有可行的着色方案,证明了该算法的可行性。与已有的模型相比,该模型在解的准确性、计算复杂度以及操作的自动化方面都表现出了很强的优势。     

双编码方式求解整数规划问题的DNA算法

DNA计算是以DNA分子作为数据的一种新型计算模式,在DNA计算中首要面对的问题是编码问题。文中提出了一种双编码方法,利用这种编码方法使得在DNA计算的读解过程类似于DNA测序过程,容易实现自动化操作。基于该编码方法所建立的DNA计算模型可用于求解整数规划问题,只需有限的几次PCK反应即可读取问题的可行解。与其他DNA算法相比,该算法具有操作简单、易于实现的优点。     

DNA计算及DNA计算机的研究进展

概述了DNA计算的基本原理、DNA计算的应用和DNA计算机的研究进展及存在问题，基于DNA生化反应的计算机称为DNA计算机，由于其采用一种完全不同于传统计算机的运算逻辑与存贮方式，DNA计算机在解决某些复杂问题时具有传统计算机无法比拟的优势，目前国际上关于DNA计算和DNA分子生物计算机的研究方兴未艾，极大地推进了DNA计算机的研究过程。     

DNA芯片在最短公共超串问题中的应用

DNA芯片技术是近年来生命科学与信息科学的新兴研究领域,其突出特点在于它的高度并行性、多样化、微型化以及自动化.最短公共超串问题是计算机科学中的NP-完全问题.笔者在DNA计算和DNA芯片基础上,提出了基于DNA芯片解决最短公共超串问题的DNA计算新模型.该模型可对信息高度并行获取,并且具有操作易自动化的优点.     

DNA粘接计算模型及其应用

DNA计算是应用分子生物技术进行计算的新方法。应用形式语言及自动机理论技术研究DNA计算理论,有利于推动理论计算科学的发展。本文根据DNA分子的结构及特点给出了DNA分子的形式化描述,介绍了DNA粘接计算模型的文法结构和计算能力,并应用DNA计算方法求解3-SAT问题。     

DNA芯片在最短公共超串问题中的应用

DNA芯片技术是近年来生命科学与信息科学的新兴研究领域，其突出特点在于它的高度并行性、多样化、微型化以及自动化，最短公共超串问题是计算机科学中的NP-完全问题．笔者在DNA计算和DNA芯片基础上，提出了基于DNA芯片解决最短公共超串问题的DNA计算新模型．该模型可对信息高度并行获取，并且具有操作易自动化的优点．     

DNA传感器技术概况

DNA传感器是基于DNA分子相互作用原理设计而成的一种新型的检测技术，具有快速，简单等优点，在基因分析及其他应用领域已显示出越来越重要的价值。本文就DNA传感器近年来出现的新概念、原理、方法和应用特点进行了概述。     

DNA自组装与信息存储

脱氧核糖核酸(Deoxyribonucleic acid, DNA)作为未来数据的存储介质具有巨大的潜力.近年来,DNA自组装技术发展迅速,其中DNA折纸(origami)和DNA瓦片(tile)设计及组装技术已经实现了纳米结构的原子级精度.DNA自组装纳米结构因其具有空间可寻址性、可编程性等优点,为基于DNA自组装的信息存储提供了发展平台.文章综述了基于DNA自组装技术的两种组装模型及DNA信息存储领域的发展现状,总结了当前基于DNA单链、DNA origami和DNA tile的信息存储,概述了当前基于DNA的信息存储领域中面临的挑战,并展望了DNA自组装及其在信息存储领域的应用前景.     

最小生成树DNA算法

为了改进粘贴模型,提出了用生化实验实现求解割集的计算方法,并基于该方法给出了最小生成树DNA算法.首次将分离实验扩展为基于分离板的分离实验和基于电泳技术的分离实验,所提出的最小生成树DNA算法打破了DNA计算的计算模式——用求解割集的最小边的方法逐步产生最小生成树.用该方法求解割集利用了分离实验运算的高度并行性,最小生成树DNA算法的时间复杂度是线性的,从而降低了算法的时间复杂度.     

电力负荷的混沌预测方法

借助混沌分析理论介绍了电力负荷时间序列的混沌性识别技术,给出了一种基于混沌负荷序列的预测方法--基于相空间轨迹演化模式的预报模型,该方法具有预测精度高、计算速度快的优点,在短期负荷预测中可获得相当满意的结果.     

基于分子重组技术的DNA计算

DNA计算是计算科学和分子生物学相结合的新领域。目前关于DNA计算的研究主要是抽象的计算模型和简单的原理性试验。DNA剪接计算模型是以生物DNA分子重组技术为基础的文法系统。本文主要介绍DNA剪接计算模型的文法结构及计算方法,证明了DNA剪接模型可以计算所有图灵机可计算函数。     

基于DNA链置换反应的编码器逻辑运算模型研究

作为自组装DNA计算领域中一门新技术,DNA链置换反应在分子计算领域得到了广泛的应用.基于自组装DNA计算原理,设计了对应不同逻辑门的DNA分子电路.基于DNA链置换反应机理构建了编码器逻辑电路的分子计算模型.当输入DNA分子信号链时,将不同分子浓度比的DNA分子逻辑门电路混合,借助分子间的特异性杂交反应及分子间链置换反应,最终可输出信号链分子.Visual DSD仿真结果表明了本文设计的编码器逻辑计算模型的可行性与准确性.为拓展分子逻辑电路的应用做出有益的探索.     

一种广义分子计算模型在集合覆盖中的应用

在分子计算原理和传统计算机模型基础上,提出了一种新的基于图灵机的广义分子计算模型,又称广义图灵模型,该模型的具体实现不依赖于特定生物技术. 模型继承分子计算大存储高并行的特点,通过时空复杂度转换,在求解NP完全问题上具有通用性. 模型由一台基本图灵机、一个只写带和一条工作带及读写网络这3部分组成,其中只写带和工作带之间存在一种特殊拓扑映射. 通过数据规模为4的集合覆盖问题,证明该算法能在多项式时间内求解集合覆盖问题,验证了算法和模型的有效性.     

广义分子计算模型在整数问题中的应用

分子计算是一种新型的并行计算模式. 作为信息载体和计算载体的DNA,生化反应时存在不可控性. 构建具有通用性的分子计算机存在许多困难和限制. 将分子计算黏贴模型与图灵机相结合,已提出一种不依赖于特定生物技术的广义分子计算模型(generalized turing model,GTM). 对GTM模型进行扩展,通过实验说明了该广义分子计算机能够在多项式时间内求解NP完全的整数规划问题,该模型具有编码简单、错误率低等特点.     

利用发夹结构分子实现栈式结构的DNA计算模型

为使DNA计算机能像电子计算机一样解决数据的组织与存储问题, 提出了一种利用发夹结构分子实现栈式数据结构的DNA计算模型,描述了数据的存储和组织方式以及元素入栈、 出栈等操作的生物操作过程。经验证, DNA计算模型求解数据的组织问题是可行的, 有助于DNA计算机走向实际应用。     

Sticker DNA computer model ——Part Ⅰ: Theory

DNAcomputationisanewcomputationalpatternusingDNAmoleculesandsomeenzymesforessentialmaterials,whichisbasedonsomebiochemicalreactions.ThiscomputationalmethodwasfirstlyproposedbyDr.Adlemanin1994[1].ItsprominentadvantageismakingthebestofDNAmoleculeswithenormousmemorygeneticcodes,andimmenseparallelismofbiochemicalreactions.Asaresult,DNAcomputersbasedontheDNAcomputa-tionmodelwillhaveenormousmemorycapacityandegregiousoperationspeed.DNAcomputercanrunwithhighspeed,enormousinformationmemorycapab…     

Sticker DNA computer model ——Part Ⅰ: Theory

Sticker model is one of the basic models in the DNA computer models. This model is coded with single-double stranded DNA molecules. It has the following advantages that the operations require no strands extension and use no enzymes; What‘s more, the materials are reusable.Therefore it arouses attention and interest of scientists in many fields. In this paper, we will systematically analyze the theories and applications of the model, summarize other scientists‘ contributions in this field, and propose our research results. This paper is the theoretical portion of the sticker model on DNA computer, which includes the introduction of the basic model of sticker computing. Firstly, we systematically introduce the basic theories of classic models about sticker computing; Secondly, we discuss the sticker system which is an abstract computing model based on the sticker model and formal languages; Finally, extend and perfect the model, and present two types of models that are more extensive in the applications and more perfect in the theory than the past models: one is the so-called k-bit sticker model, the other is full-message sticker DNA computing model.