DNA计算机中二叉树存储结构分析

时间:2022-10-14 12:02:51

DNA计算机中二叉树存储结构分析

摘要:DNA计算机是未来计算机发展的重要方向,其优势十分明显,本文以顺序二叉树为思路的双链DNA分子法为例,介绍的是DNA计算机存储结构的基本理论和具体操作方式。

关键词:DNA计算机;二叉树模型;DNA双链;顺序存储

中图分类号:TP384 文献标识码:A 文章编号:1007-9599 (2011) 21-0000-02

Analysis of DNA Computer Storage Structure in Binary Tree

Li Dongling,Mao Zimin

(Shangqiu Polytechnic,Shangqiu 476000,China)

Abstract:DNA computer is an important direction for future development of computer,the advantages are clear,this paper binary sequence double-stranded DNA molecules for the idea of law as an example,the DNA computer storage structure of the basic theory and the specific mode of operation.

Keywords:DNA computer;Binary tree model;DNA double-strand;Sequential storage

一、DNA计算机技术

所谓的DNA计算机的核心技术就是利用有机分析作为信息处理的媒介,替代传统的数字开关元件来完成计算。因为就当前一些棘手的网络处理问题而言传统的计算机已经不能满足需求,同时在制造工艺上已经不能超越材料极限,因此研究人员试图将此类问题交给更加先进的计算机来完成,即将计算机元件过渡到分级量级,量子计算机和DNA计算机就此成为了研究的方向,而DNA计算机则引起优势成为了研究的热点。具体看:

(一)计算可以高度并行。与遗传学算法等智能计算方法的隐并行性不同,DNA计算机是真正实现了底层机制的并行。运算的速度相当快,在一周的运算量将相当于所有计算机从问世以来的计算量。

(二)容量巨大。以单位为1ml的DNA溶液为例,其存储了1万亿亿的二进制数据,此种海量的存储模式可以超过当前所有计算机的存储量。

(三)能耗低。DNA计算机是一种生物化的设备,其能耗相当于一台计算机计算同样数据所消耗的十亿分之一。

(四)DNA资源丰富。从生物计算的角度看,很多的有机体中都可以获得所需要的DNA分子用于计算机应用。

从目前研究的成果看,DNA计算机的重点有两个方面:一方面是对DNA计算机的自然计算模式进行解读;一方面是对DNA计算机不同于传统计算机的数据结构进行分析和操作,以到达可靠控制的目的。传统的计算机有完善的计算理论作为技术支持,可以保证计算的准确性和可靠性,而DNA计算机的读写方式与传统计算机的可重复操作不同,依靠的是分子的连接、插入、剪切、粘结、删除等过程,以此完成数据的存储和转化。因此DNA计算机要得到实际应用,就必须向电子计算机一样来解决DNA中的信息组织问题,这就需要合理的数据结构来有效的将DNA分子组织起来,并完成DNA计算机对信息的处理。所以数据结构就成了DNA计算机发展的一个重要研究课题。下面就将针对DNA计算机中二叉树存储结构进行介绍。

二、DNA计算的二叉树存储结构分析

(一)二叉树的基本内涵。DNA计算机的研究中,二叉树储存结构的形成是在DNA计算机中引入传统计算机的二叉树数据结构,根据DNA计算机的理论基础和特征,分析分子材料的操作的并行机制,以此提出具有良好可行性的二叉树信息结构框架。在数据结构的研究中二叉树是一种特殊的树形结构,是一种节点的有限几何:1)空间二叉树;2)由一个根节点和两颗不相关的书组成,其相互不相交的左子树和右子树组成,左右两边的子树又分别形成一颗二叉树。二叉树的特点就是每个节点至多有两颗子树,即二叉树的存在度不会大于2的节点,同时二叉树可以分为左右两个子树,其次序是不能任意对调的。完全二叉树是指对于深度为K的二叉树,每层的节点数目应满足于层数相关的特定范围,1)第i层上的节点个数都是2i-1;2)第K层从右边起的连续缺若干的节点。

二叉树存储的结果方式主要有顺序和链式两种,顺序结构的二叉树是按照二叉树的结构对二叉树的节点进行编号,用一组完整的地址连续的存储单元按照次序从上至下,从左至右的存储完全二叉树的节点元素;链式结构则是利用一个指定的链来表示存储一颗二叉树,二叉树中的每一个节点都可以利用链表中对应的链节点来储存。而所谓的DNA计算方式就是以有机分子为数据,利用生物酶和生化操作方式对信息进行处理,实际上是一种新型的计算模式。因此利用不同的DNA分子的特征可以对二叉树顺序在存储结构和链式存储结构中进行拓展性研究。下面就以顺序结构为例进行介绍。

(二)双链DNA实现顺序存储结构。在DNA计算机中二叉树顺序存储结构可以利用双链DNA的分子进行表示,其结构如下图1、2:

1.双链DNA分子所代表的DNA计算机中的二叉树使用的是DNA中的不同氮碱基来表示,并利用不同的组合来诠释二叉树的不同组件的编码方式。在表示二叉树的DNA双链由P_L、E_Ⅰ、S_Ⅰ、E_Ⅱ、S_Ⅱ、二叉树节点元素、S_Ⅲ、E_Ⅲ、P_R部分组成。

2.二叉树节点的元素按照二叉树的完全和非完全形态而展开设计,首先,对于完全型的二叉树其所有的元素节点都将从根节点(b1)开始,以此从左到右,从上到下机械能顺序化的编号,节点元素则用bi来进行表示,其中i作为系统的编号。上面的编号顺序,规则的将b1……bn表示的n个节点元素的顺序存放在DNA中相应的位置上;其次,对于非完全二叉树则是每个节点与其对应的完全二叉树上的节点向对应,存储在DNA双链的位置上,如相应的位置如果没有节点则为“空”,用b0代表。为了正确的实现二叉树的基本操作,在b1节点的右侧设置b0点。

3.在DNA计算机中进行操作,将引物部分设定为P_l和p_r。设计在DNA双链的左右两侧的引物,反应物的浓度是影响生物化学反应效率的直接因素。在此为了保证操作的可靠性,计算机借助分子生物学采用聚合酶的链式反应来扩展目标DNA的链的数量。

4.识别点的位置E_Ⅰ、E_Ⅱ、E_Ⅲ:首先,其中,E_Ⅰ是第一种限制性酶的识别位置,主要用在按照以上要求变化的二叉树的末尾进行追加新的节点。在第一种限制酶的活化环境下,而二叉树编码的DNA双链将从追加位置in的位置被切掉。在连接酶的生化作用下,等待插入节点的元素与从二叉树DNA双链上剪切下来的右侧片段相互反应而连接,形成一个新的DNA双链结构,从而完成新的节点的追加。其次,E_Ⅱ属于第二种限制酶的识别点,主要的作用就是删除当前二叉树中编号为最大的节点元素。在此种酶的活性条件下,DNA的双链将被切割,具体的位置在out的位置。在连接酶的促进下,detectorI片段与二叉树DNA双链中剪切下来的右侧片段进行杂交和连接,形成一个相对稳定的新的DNA链,从而完成对编号最大的节点的删除操作。通过试验检测表明限制酶所剪切下来的右侧片段,可以得知当前二叉树中编号最大的节点元素所对应的数值。第三,E_Ⅲ此种酶所标记的识别点是用于返回二叉树根节点的数值。以上的三个部分在表示二叉树的DNA双链结构中,识别的过程只能出现以此,否则就会引发错误的识别和操作。

5.S_Ⅰ、S_Ⅱ和S_Ⅲ:这三个代表的是产度合适的碱基对。碱基对是可以随机产生的,其作用就是确定:限制酶是否能够识别完成编码的二叉树的DNA双链结构的固定位置。因为选择的限制酶不同对于DNA链的识别点和剪切的位置也就存在差异。在特定的情况下,只要剪切位置是对的,这三个部分的任意一个就可省略,即设定此碱基对数量为零。

6.结构中对于新节点元素和两个detector片段的结构。在存储中为了按照对应的二叉树从根节点开始,从左至右、从上到下的顺序编号的二叉树末尾是正确的值,因此需要追加新的节点来定位,此种节点是事先设计好的元素结构,具体情况如图3中a所示。同时需要删除编号最大的节点和返回根节点的数值还需要设计两个detector片段结构来辅助标记,分别记为I、II,如图中的b、c所示。所有的这些片段都具有粘性末端,其粘性末端与等待连接的DN段末端具有互补性。这样就可以在酶的作用下完成连接。而此过程中新节点元素结构中不包括E_Ⅰ、E_Ⅱ和E_Ⅲ,如果包括则会导致操作的错误。不同的节点原则序列编码是不同的,为了方便区分不同的元素结构。而其他部分的意义和二叉树DNA双链中的部分具有相同的化学意义。

7.完成二叉树的基本操作方式:(1)Bio-BTreeInit(BT):构建一个空的二叉树;(2)Bio-BTreeAppend(BT,X):在维持原有的二叉树节点编号的同时追加一个新的元素,追加后得到的仍是与完全二叉树编号一致的新的二叉树;(3)Bio-BTreeDelete(BT,X):在对应的完全二叉树上从根节点开始按照上面所述的顺序删除最大节点元素,已获得其对应的数值;(4)Bio-BTreeEmpty(BT):判断二叉树是否为空二叉树;(5)Bio-BTreeRoot(BT,X):用X返回二叉树根节点元素。

三、结束语

从前面的分析看,DNA计算机所采用的是一致逻辑性较强的计算模式,其基本理论决定其可以利用二叉树的理论模型来完成对存储结构的设计和实现。本文所介绍的是一种顺序二叉树在DNA双链分子法中的应用,此方法通过DNA编码和仿真试验证明其具有可操作性。

参考文献:

[1]崔光照,刘玉琳,张勋才.数据存储新方向:DNA分子存储技术[J].计算机工程与应用,2006,26

[2]唐金文.静态单链表存储结构算法分析[J].曲靖师范学院学报,2003,22:3

[3]索红军.二叉树的静态二叉链表存储[J].渭南师范学院学报,2008,23:2

[4]陈军,赵恒永.数据结构中链式结构的Java实现[J].北京化工大学学报,2002,29:5

[5]陈朋.后序遍历二叉树的递归和非递归算法[J].安庆师范学院学报:自然科学版,2005,11:2

[6]李崇.基于数据结构的链表创建方法探究[J].现代电子技术,2009,2

[作者简介]李东灵(1982-),男,商丘市人,研究生,商丘职业技术学院讲师,研究方向:计算机应用与研究;毛自民(1981-),男,商丘市人,研究生,商丘职业技术学院讲师,研究方向:计算机应用与研究。

上一篇:基于知识管理理论的网络课程设计探究 下一篇:基于PHP的CMS后台管理系统的设计与实现