摘要
Inspired by the potential computational capability of 3-Dimensional (3D) DNA structure,this paper presents a graph structure constructed by k-armed (k = 3or 4) branched junction DNA molecules to explore the possibility of solving some intractable problems. In the 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 connec-tivity of this graph can be determined. Furthermore,the amount of potential solutions can be reduced by a theorem of graph theory.
Inspired by the potential computational capability of 3-Dimensional (3D) DNA structure, this paper presents a graph structure constructed by k-armed (k = 3 or 4) branched junction DNA molecules to explore the possibility of solving some intractable problems. In the 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, the amount of potential solutions can be reduced by a theorem of graph theory.
基金
Supported by the National Natural Science Foundation of China (No.30370356 and No.60574041).