Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Towards a Robust Biocomputing Solution of Intractable Problems
Year:2008
Research Areas
  • Artificial intelligence
Information
Abstract
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.
International
Si
JCR
No
Title
Lecture notes in computer science
ISBN
0302-9743
Impact factor JCR
0
Impact info
Volume
4848
10.1007/978-3-540-77962-9
Journal number
0
From page
221
To page
230
Month
FEBRERO
Ranking
Participants
  • Participante: Marc García-Arnau (Universidad Politécnica de Madrid)
  • Autor: Alfonso Vicente Rodriguez-Paton Aradas (UPM)
  • Autor: Petr Sosik (UPM)
  • Autor: Daniel Manrique Gamo (UPM)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Grupo de Inteligencia Artificial (LIA)
  • Departamento: Inteligencia Artificial
S2i 2020 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)