团数的DNA折纸术计算模型

The Computing Model for Clique Number Based on DNA Origami

给定简单无向图,用寡聚核苷酸片断编码图中的顶点,将这些寡聚核苷酸片断的连接作为脚手架链.根据脚手架链设计订书钉链以及订书钉链的补链.首先,利用订书钉链依次折叠脚手架链,在脚手架链不同位置处形成发夹结构.用发夹结构的组合表示编码的顶点是否在最大团中,建立数据池;再次,对补图的每条边加入对应的订书钉链对,再次折叠脚手架链来删除非解;最后,订书钉链的补链从脚手架链上置换订书钉链,打开脚手架链上的表示顶点在最大团中的发夹结构,凝胶电泳,根据脚手架链长度的变化判断所求的团数.该模型仅使用订书钉链与脚手架链杂交,结合链置换,通过凝胶电泳检测脚手架链上发夹结构的变化,因而简单、读解方便、可行性高.

Given a simple undirected graph, each vertex in the given graph was encoded by segments of ol igonucleotide, and the scaffold strand was thus designed by connecting these encoded oligonucleotide seg ments together.Staples and strands that were complement to staples were designed according to the de signed scaffold strand.Firstly,the scaffold strand was folded in turn by using staples, and hairpin struc tures were formed at different positions of the scaffold.The combination of hairpin structures represented whether the encoded vertex was in the clique or not,and the initial data pool was therefore constructed. Secondly,for each edge in the complement graph,a pair of staples were added accordingly into the data pool to delete non solutions. Finally, staples were displaced from the scaffold by their complement strands, hairpins representing that vertices in the clique were unfolded, gel electrophoresis was per formed, and the wanted clique number was therefore determined according to the variation of length of the scaffold.Since the computing model only employs hybridization, strand displacement, as well as gel e lectrophoresis,the proposed model is simple,easy for reading out solutions and applicable.