图的最小顶点覆盖问题的质粒DNA计算模型

A DNA computing model for the minimal covering by plasmids

给出了图的最小顶点覆盖问题的质粒DNA计算模型及其实现算法 .算法的时间复杂性是O(q) ,编码最小覆盖问题所需的核苷酸片段种类为n ,其中n ,q分别是图的规模和边数 .在算法中 ,所用酶的种类也等于图的规模 .而且 。

A DNA computing model and algorithm for the minimal covering problems by plasmids were presented. Time complexity of the algorithm was O(q), the number of kinds of short oligonucletides needed to encode the minimal covering problem was n, where n, and q were the size and edge of the graph respectively. In the algorithm, the number of enzyme was equal to the size of the graph. There was no tangled self-annealed single-stranded DNA or PCR amplification step.