Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
2076575 | Biosystems | 2007 | 11 Pages |
Abstract
We present a P system with replicated rewriting to solve the Maximum Clique Problem for a graph. Strings representing cliques are built gradually. This involves the use of inhibitors that control the space of all generated solutions to the problem. Calculating the maximum clique for a graph is a highly relevant issue not only on purely computational grounds, but also because of its relationship to fundamental problems in genomics. We propose to implement the designed P system by means of a DNA algorithm. This algorithm is then compared with two standard papers that addressed the same problem and its DNA implementation in the past. This comparison is carried out on the basis of a series of computational and physical parameters. Our solution features a significantly lower cost in terms of time, the number and size of strands, as well as the simplicity of the biological implementation.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Modelling and Simulation
Authors
Marc GarcÃa-Arnau, Daniel Manrique, Alfonso RodrÃguez-Patón, Petr SosÃk,