Abstract: To determine the connectivity of a graph, a three dimensional DNA graph structure and the detailed procedures of the algorithm are presented. In this paper, we propose a graph structure constructed by k-armed (k=3 or 4) branched junction DNA molecules. In our proposed procedure, vertex building blocks consisting of 3, 4-armed branched junction molecules are selectively used to form different graph structures. After separating these graph structures by gel electrophoresis, the connectivity of this graph can be determined. Furthermore, based on evolutionary algorithm enumerating all the potential solutions is avoided.

Key words: Evolutionary Algorithm, 3-Dimensional DNA structure, Connectivity, DNA computing

摘要： 针对求连通度这一难解问题，论文提出了三维DNA图结构进化算法。在本文中我们提出了一种由k-臂DNA分子构建的图结构。在所述方法中3，4臂DNA分子的顶点构造块被选择性地用来构建一些不同的图结构。然后通过凝胶电泳分离，图的连通度便可确定。并且通过引入进化算法的思想，避免了解空间的穷举。

关键词: 进化算法, 三维DNA结构, 连通度, DNA计算