Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Towards a Robust Biocomputing Solution of Intractable Problems
Año:2008
Áreas de investigación
  • Inteligencia artificial
Datos
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
Esta actividad pertenece a memorias de investigación
Participantes
  • 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)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Grupo de Inteligencia Artificial (LIA)
  • Departamento: Inteligencia Artificial
S2i 2021 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)