共查询到19条相似文献,搜索用时 125 毫秒
1.
求解Ramsey数的困难在于需要搜索的解空间太大,而传统的电子计算机无法在有效的时间和存储空间上进行求解.由于DNA计算具有巨大的并行性和高密度存储能力等优点,文中研究了Ramsey数的DNA计算模型.针对传统的Ramsey数DNA计算模型存在的DNA序列量过多和序列过长的不足,利用DNA分子的特性以及生物操作将非解尽可能较早地消除,提出了并行型Ramsey数DNA计算模型,并以R(3,10)为例,给出了具体的求解步骤. 相似文献
2.
DNA计算是一种模拟生物分子的结构并借助于分子生物技术进行计算的新模式。它引入了崭新的数据结构和计算方法,为解决NP完全问题提供了全新的途径。由于DNA计算具有信息处理的高并行性、低能耗及高存储密度等优点,对传统的基于计算安全的密码体系提出了挑战。DNA密码便是近年来伴随着DNA计算的研究而出现的密码学新领域。用DNA分子作为信息载体,以实现数据隐藏、认证、加密等安全技术。在简要回顾DNA计算原理的基础上,详细分析了基于DNA的一次一密方案以及Boneh用DNA计算机破解DES的方法;最后探讨在DNA计算中的信息安全技术。 相似文献
3.
基于粘贴和2-臂DNA模型的层次聚类算法 总被引:1,自引:0,他引:1
为了充分利用DNA分子在生物计算中的高度并行性和强大的存储能力,将DNA计算引入层次聚类实现对数据集的全局搜索。提出了粘贴模型与2-臂DNA分子相结合的混合模型求解最近邻层次聚类的DNA算法。针对二维数据空间,算法首先基于最小生成树思想产生图的边的所有组合链;其次筛选含n-1条边的链,基于边附着顶点,并选择包含全部顶点的复合链;再将复合链末尾连接相应边的权值片段,电泳出最短链;最后通过荧光分析法读解,得到最终的聚类结果。与已有文献同类算法对比表明,该算法在保持多项式操作时间下,更充分考虑连接边的长度,并将读解步骤数限定为常数步。 相似文献
4.
DNA计算原理及系统分析 总被引:3,自引:2,他引:3
DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法,它开创了以化学反应作为计算工具的先例,具有广阔的应用前景。DNA计算的两个主要特点是计算的高度并行性和巨大的信息存储容量。该文简要介绍了DNA计算的原理及其数学计算的基本思想;对DNA计算的特点及其系统进行了分析。比较了DNA计算机与图灵机的异同;最后对DNA计算的发展前景进行展望。 相似文献
5.
基于生化反应的生物智能计算是现阶段计算领域研究的热点,DNA计算是通过DNA分子之间的生化反应来进行计算的一种计算模式,凭借运算巨大的并行性和海量存储的优势,DNA计算在解决复杂运算问题方面的计算能力显而易见。设计了一种利用DNA计算来求解图的最小生成树的计算模型,采用一种特殊的编码方式来对顶点,边和权值进行编码,并且描述了MSTP解的计算过程。 相似文献
6.
7.
8.
9.
DNA计算机中广义表数据结构的设计与实现(英文) 总被引:1,自引:0,他引:1
类似于电子计算机,数据结构能帮助DNA计算机合理、高效地组织要处理的信息.文中提出了DNA计算机中广义表的一种设计方法.首先,讨论了k-臂 DNA分子的结构及其在DNA计算中的应用.接着,在讨论了广义表存储结构的同时.给出了广义表两种节点的k-臂 DNA编码的形式描述.最后详细描述了DNA计算机中广义表主要操作的实现算法.这些操作包括初始化空的广义表,创建包含指定元素的广义表和遍历广义表的元素.文中的方法可推广到DNA计算机上其它非线性数据结构. 相似文献
10.
11.
提出了一种基于DNA计算的粘附子模型的并行乘法算法,该算法首先将两个二进制数相乘转变成根据被乘数对乘数进行一系列的移位相加。将被乘数与乘数编码在同一条存储链上,通过组合、分离、设置、清除等四种运算计算出积的值。由于表示输出的DNA链的结构与表示输入的DNA链的结构相同,因此表示输出的DNA链无需做任何改变,就能在后面的运算中重复使用。该算法不仅能用于整数乘法中,还可以很方便地推广到包含小数的乘法运算及多个因数参与的乘法运算中。该算法的突出优点是充分发挥了DNA计算内在的并行计算性,如果参与乘法运算的因数的个数相等,则计算多组乘法运算与计算一组乘法运算所需的时间相同,并且多组乘法运算能从同一个试管内开始。 相似文献
12.
旅行商问题的闭环DNA算法 总被引:1,自引:0,他引:1
旅行商问题TSP是NP完全问题,在工程实践中有着广泛的应用,利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式,与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA 计算模型及其改进;随后提出了一种基于改进的闭环模型求解TSP问题的算法,并对算法的实验过程进行了详细的描述;最后运用该算法解决了一个小规模的TSP问题算例,结果表明,该算法能在较低的时间复杂度内有效地解决TSP问题。 相似文献
13.
DNA计算机:原理、进展及难点(Ⅱ)计算机"数据库"的形成--DNA分子的合成问题 总被引:3,自引:4,他引:3
基于生化反应机理的DNA计算机模型引起了科学领域内许多不同学科学者们的关注与兴趣.DNA计算已经成为国际科学研究前沿领域内的一个新热点.DNA计算机的研制需要诸如生物工程、计算机科学、数学、物理、化学、信息科学、微电子技术、激光技术以及控制科学等许多学科的共同协作攻关.作者以系列文章的形式拟对DNA计算机的基本原理、研究进展、DNA计算的模型以及当前研究中的难点给予研讨.该文属第二篇,重点讨论DNA计算机研制中DNA分子的合成问题.DNA分子的合成问题不仅是DNA计算中生物操作过程首先要处理的问题,而且是DNA计算机研制中必须要解决的问题,因为最终实用化的DNA计算机应是一种全自动化的.如何将DNA分子的合成过程与编码、其它生化操作自动地衔接起来是全自动化DNA计算机当前研究的关键难题.若要解决这个问题,人们必须很熟悉有关DNA分子合成的基本原理以及合成技术.这也是该文的动机. 相似文献
14.
15.
DNA计算机与传统电子计算机相比具有高度并行性、容量大、速度快等特点。它也是以加、减、乘、除等简单算术运算和异或等逻辑运算为基本运算单元。在自装配加法的基础上,设计了DNA自装配乘法模型,算法的时间复杂度为[O(1)],空间复杂度为[O(n)],并给出实例验证了算法的有效性。该算法具有编码简单、效率高、通用性强等优点。 相似文献
16.
DNA计算机具有超强的并行运算能力和巨大的数据存储能力,被认为有望解决电子计算机所面临的瓶颈问题。微流控技术提供了一个可实现自动化操作、通用型DNA计算机的支持平台。借助于微流控技术,将DNA计算相关的生化反应有机地集成在芯片平台上加以实现,进一步提高了DNA计算的可靠性、减少了实验过程的手工操作和反应时间。在介绍DNA计算机的基本概念和微流控技术基础上,围绕微流控DNA计算机的原理、模型和应用等关键问题,分析了微流控DNA计算机的体系结构及设计方法,讨论了微流控DNA计算机未来可能的发展方向。 相似文献
17.
DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法.算法由初始解空间生成算法Init()、冗余解删除算法IllegalRemove()和并行搜索器ParallelSeacher()共3个子算法组成.与同类算法的性能比较分析表明:本算法在保持多项式生物操作复杂性的条件下,将求解n维精确覆盖问题的DNA链数从O(2n)减少至O(1.414n),从而将DNA计算机在试管内可求解的精确覆盖问题集合的基数从60提高到120,改进了相关文献的研究结果. 相似文献
18.