DNA并行计算中的B-树数据结构的设计与实现

Design and implementation of B-tree data structure in DNA parallel computing

DNA分子特性使得DNA计算具有极大的存储密度和高度的计算并行性。不管何种计算模型,DNA分子的选择和DNA编码都十分重要。提出了DNA计算中的B-树的数据结构设计方法。首先给出了B-树定义及其操作的形式化描述,接着介绍了本计算模型采用的3D结构DNA分子——k-arms分子结构,详细给出了一棵m阶B-树的构造步骤,最后实现了其查找、插入和删除等操作。提出了DNA分子计算的3D结构和分治策略,具有一定的可扩展性和并行性,对DNA计算的其他模型有参考价值。

The best virtues of DNA computing are the maximum density of storage and the huge parallel of computing because of the features of DNA molecules.It is important for any DNA computing model to choose some DNA molecules and code them.This paper proposed the method of designing B-tree in DNA computing.Firstly,formally described the definition of B-tree and operations.Then,described the 3D DNA molecules,k-arms DNA molecules in detail.Furthermore,proposed the approach of creating a B-tree with m sub-trees.Finally,proved the operations,such as searching,inserting and deleting.DNA molecules with 3D structure and divide-and-conquer strategy were scalable and parallel,and could be used in other DNA computing model.