Molecular beacon computing model for maximum weight clique problem

摘要

Given an undirected graph with weights on the vertices, the maximum weight clique problem requires finding 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 encode weight of vertex into a unique fixed length oligonucleotide segment and employ sticker model to solve the problem. The proposed method has two distinct characteristics. On one hand, we skip generating initial data pool that contains 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 are treated like variables which store 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 the other weight-related problem. In addition, molecular beacon is also employed in order to overcome shortcomings of sticker model. Besides, we have analyzed the proposed algorithm’s feasibility.