Molecular beacon-based DNA computing model for maximum weight clique problem

Given an undirected graph with weights on the vertices, the maximum weight clique problem requires to find the clique of the graph which has the maximum weight. The problem is a general form of the maximum clique problem. In this paper, we encoded weight of vertex into a unique fixed length oligonucleotide segment and employed sticker model to solve the problem. The proposed method has two distinct characteristics. On one hand, we skipped generating initial data pool that contained every possible solution to the problem of interest, the key point of which is constructing the solution instead of searching solution in the vast initial data pool according to logic constraints. On the other hand, oligonucleotide segments were treated as variables which stored weights on vertices, no matter what kind of number the weights are, integer or real. Therefore, the proposed method can solve the problem with arbitrary weight values and be applied to solve other weight-related problems. In addition, molecular beacons were also employed in order to overcome shortcomings of sticker model. And we analyzed the feasibility of the proposed algorithm as well.