|
Descripción
|
|
|---|---|
| Abstract An incremental approach to construction of biomolecular algorithms solving intractable problems is presented. The core idea is to build gradually the space of candidate solutions and remove invalid solutions as soon as possible. We demonstrate two examples of this strategy: a P system with replication and inhibitors for solving the Maximum Clique Problem for a graph, and an incremental DNA algorithm for the same problem inspired by the membrane solution. The DNA implementation is based on the parallel filtering DNA model featuring error-resistance of the employed operations. The algorithm is compared with two standard papers that addressed the same problem and its DNA implementation in the past. The comparison is carried out on the basis of a series of computational and physical parameters. The incremental algorithm features a dramatically lower cost in terms of time, the number and size of DNA strands, together with a high error-resistance. A probabilistic analysis shows that physical parameters (volume of the DNA pool, concentration of the solution-encoding strands) and error-resistance of the algorithm should allow to process in vitro instances of graphs with hundreds to thousands of vertices. | |
|
Internacional
|
Si |
|
JCR del ISI
|
No |
|
Título de la revista
|
Lecture notes in computer science |
|
ISSN
|
0302-9743 |
|
Factor de impacto JCR
|
0 |
|
Información de impacto
|
|
|
Volumen
|
4848 |
|
DOI
|
10.1007/978-3-540-77962-9 |
|
Número de revista
|
0 |
|
Desde la página
|
221 |
|
Hasta la página
|
230 |
|
Mes
|
FEBRERO |
|
Ranking
|
|