Prólogo
La Ciencia, a lo largo de su historia, ha experimentado una serie de
sobresaltos motivados por la consecución de unos resultados que, unas
veces, han culminado un proceso previo, generalmente largo, de gestación
y, otras, han provocado una auténtica convulsión entre los
investigadores. En todo caso, esos hitos han producido un avance
cualitativo en el conocimiento científico.
En la historia de la Computación se pueden observar unos puntos de
inflexión que han marcado de forma decisiva el devenir de la misma, y
han propiciado el desarrollo de nuevas herramientas, tanto a nivel
teórico como a nivel práctico, que han sido consideradas fundamentales.
Curiosamente, la mayoría de esos momentos críticos están asociados con
las limitaciones inherentes a la potencia de determinados métodos
y/o modelos.
El primer hito relevante que queremos destacar se produce con la
respuesta negativa a dos cuestiones planteadas por D. Hilbert, en 1928,
relativas a la consistencia y completitud de las
Matemáticas, en donde se establecen las limitaciones inherentes
al método axiomático. La Teoría de la Computación como
disciplina de estudio comienza, propiamente, con los trabajos realizados
para dar respuesta a estas cuestiones.
La posibilidad de que existan problemas abstractos que no se puedan resolver de
manera efectiva y la necesidad de dar respuesta a la tercera cuestión
formulada por D. Hilbert, en 1928, relativa a la decidibilidad de las
Matemáticas, plantea la conveniencia de formalizar el concepto de
algoritmo y de función computable. Así, en la década de los
treinta, aparecen los primeros modelos teóricos de computación y se inicia el
estudio formal del concepto de procedimiento efectivo. La existencia de
problemas que no pueden ser resueltos mediante procedimientos mecánicos
en los modelos diseñados (por ejemplo, la indecidibilidad de la lógica de
primer orden o el problema de la parada) proporciona una
limitación importante al método de formalización del concepto de
algoritmo.
En la década de los cincuenta aparecen los primeros ordenadores
electrónicos y, con ellos, surge lo que podríamos denominar
informalmente como modelos de computación práctica. En ellos se
pueden implementar los algoritmos diseñados, mediante un proceso de
traducción a un lenguaje que pueda ser interpretado por la máquina. La
existencia de problemas resolubles algorítmicamente que necesitan una
cantidad de recursos que excede las posibilidades de cualquier
ordenador electrónico, proporciona una nueva limitación, en este
caso, de la potencia de los modelos de computación práctica.
La necesidad de estudiar la mínima cantidad de recursos necesarios para
resolver un problema abstracto da origen a la Teoría de la
Complejidad. Su objetivo fundamental consiste en proporcionar una
clasificación de los problemas en función de su resolubilidad en
máquinas reales.
En el marco de la computación práctica, se plantea la necesidad de
mejorar la velocidad de cálculo y la densidad de almacenamiento de
información de los ordenadores. La aparición de máquinas paralelas
(que permiten la ejecución de varias operaciones de manera simultánea)
supone un notable avance y la miniaturización de las componentes
físicas de la máquina se convierte en un objetivo primordial.
Hacia finales de la década de los cincuenta, R. Feynman introduce el
concepto teórico de computación a nivel molecular y lo postula
como una verdadera innovación en lo que respecta a la
miniaturización. En la década de los ochenta, R. Churchhouse establece
las limitaciones físicas de la velocidad de cálculo de un ordenador
convencional y, en consecuencia, proporciona una nueva
limitación: esta vez para la computación de carácter práctico; es
decir, mediante máquinas existentes en la actualidad.
Ante esta situación surge la necesidad de buscar modelos de computación
alternativos que permitan implementar nuevas máquinas que mejoren
cuantitativamente el rendimiento de las máquinas clásicas. Es decir,
dispositivos computacionales que permitan resolver instancias de
problemas difíciles de tamaño superior al de cualquier instancia que se
pueda resolver mediante ordenadores electrónicos actuales. La
posibilidad de desarrollar modelos de computación no convencionales abre
un nuevo horizonte a la hora de amortiguar los efectos propios de las
limitaciones inherentes a la computación práctica en modelos clásicos.
La Computación Natural o Biocomputación está inspirada en el
funcionamiento de los organismos vivos y tiene como objetivo fundamental la
simulación e implementación de los procesos dinámicos que se dan en la
Naturaleza y que son susceptibles de ser considerados como procedimientos de
cálculo. Esta disciplina trata de estudiar cómo calcula la Naturaleza
y de capturar nuevos modelos y paradigmas de computación que la Naturaleza
lleva implementando desde hace millones de años.
A principio de la década de los cincuenta, J. Watson y F. Crick
descifran la estructura de las moléculas de ADN, descubren el principio
de complementariedad, demuestran que dichas moléculas codifican la
información genética de los organismos vivos y justifican la posibilidad
de usar ciertas técnicas para su manipulación. De esta manera surge la
computación biomolecular para designar al procesamiento de la
información codificada a través de macromoléculas (como el ADN, el ARN o
las proteínas).
En particular aparece la posibilidad de implementar algoritmos a través de
moléculas de ADN, debido a que éstas se pueden usar como una especie de
memoria, representando la información mediante una codificación basada en
cuatro nucleótidos, y a que es posible su manipulación por medio de reacciones
químicas controladas. En la década de los noventa, L. Adleman resuelve una
instancia de un problema matemático computacionalmente difícil,
manipulando moléculas de ADN en el laboratorio. Así la computación molecular
pasa de un plano teórico (in info) a un plano experimental (in
vitro). Es el nacimiento de la computación molecular basada en ADN.
La implementación de operaciones moleculares en el laboratorio es una
fuente de errores de mayor o menor trascendencia. Es muy posible que
esos errores se puedan reducir drásticamente a través de la
implementación in vivo de los algoritmos moleculares. Los seres
vivos poseen determinados mecanismos correctores, que no se conocen con
exactitud, y que permiten, por ejemplo, realizar copias de moléculas de
ADN con más fidelidad que la técnica de reacción en cadena de la
polimerasa (de la que se hablará en el capítulo 4) y a una velocidad
mayor. La programación de una colonia de bacterias
mediante la inserción de una serie de genes-programas de control
a través de un virus, sería un modelo computacional más robusto de tipo
paralelo y distribuido.
A nivel celular, tienen lugar una serie de procesos (reacciones químicas
y flujo de diferentes componentes químicas entre distintos
compartimentos) que se pueden interpretar como procedimientos de
cálculo. A finales de la década de los noventa, Gh. Paun introduce
un nuevo modelo de computación no determinista, de tipo paralelo y
distribuido, inspirado en el funcionamiento de las células en los
organismos vivos: el modelo de computación celular con membranas.
Este modelo puede ser adecuado para explorar la naturaleza computacional
de las células, así como para conseguir una posible implementación
artificial de sistemas que exploten dicha capacidad celular.
La computación molecular basada en ADN y la computación
celular con membranas son dos ramas importantes de la Computación
Natural, a la que también pertenecen otras disciplinas ya asentadas y
que están relacionadas directamente con los ordenadores electrónicos
como son los algoritmos genéticos, las redes neuronales
artificiales y la computación evolutiva.
Estructura del libro
Este libro tiene como objetivo principal el estudio de ciertas máquinas
moleculares diseñadas en modelos no convencionales dentro del marco de
la Computación Natural, desde el punto de vista de la potencia
computacional y de la capacidad para atacar la resolubilidad de
problemas matemáticos especialmente difíciles.
Para ello, se han elegido tres modelos de computación molecular que
poseen características dispares. Dichos modelos de computación usan
como sustrato físico (es decir, como sustancia orgánica donde se
implementan las operaciones moleculares) el ADN (ácido
desoxirribonucleico) y son descritos a través de un conjunto de
operaciones básicas susceptibles de ser implementadas en el laboratorio
con las técnicas actuales de biología molecular. Dichas operaciones, a
modo de instrucciones de un lenguaje de programación, permiten que los
procedimientos mecánicos diseñados en el modelo adquieran la forma de
programas. Los dos primeros modelos son: el modelo no restringido
de Adleman y el modelo débil de Amos, que tienen la peculiaridad
de que las operaciones primitivas no alteran la estructura interna de
las moléculas, por ello, se denominan modelos sin memoria. El
tercer modelo objeto de estudio es el modelo sticker, que admite
operaciones moleculares que alteran la estructura interna y, por ello,
se dice que es un modelo con memoria.
En este libro, a través del estudio de soluciones moleculares de
problemas numéricos NP-completos, se presenta por primera vez una
metodología que permite establecer la verificación formal de programas
en máquinas moleculares.
El libro está estructurado en capítulos, cuyo contenido vamos a tratar
de reseñar sucintamente.
En el capítulo 1 se ofrece una breve introducción histórica de la
Teoría de la Computabilidad analizándose las limitaciones y potencia de
los modelos que formalizan el concepto de procedimiento mecánico.
En el capítulo 2 se hacen unas breves consideraciones históricas de la
Teoría de la Complejidad Computacional, justificándose la necesidad
de estudiar nuevos modelos de computación como alternativa a los modelos
de computación que podríamos denominar clásicos, a fin de mejorar
la resolución cuantitativa de problemas matemáticos especialmente
difíciles desde el punto de vista de dicha Teoría.
El capítulo 3 está dedicado a la presentación de los elementos
básicos que integran los modelos de computación que se pueden enmarcar
dentro de la Computación Natural. Se hace una breve descripción
de los algoritmos genéticos, de las redes neuronales, de la
computación molecular y de la computación celular con membranas.
En el capítulo 4 se realiza una breve
introducción de la estructura química de las moléculas de ADN, y se
estudian algunas técnicas que permiten su manipulación.
Para ello, se describen algunas operaciones que se pueden realizar sobre
ellas, y que hacen posible el uso de dichas moléculas como sustrato
físico en el que se puede almacenar y procesar información.
En el capítulo 5 se estudia el primer experimento de laboratorio
que dio lugar al nacimiento de la computación molecular basada en ADN:
el experimento de L. Adleman, que resuelve una instancia del problema
HPP del camino hamiltoniano en su versión dirigida y con dos nodos
distinguidos. Además, se presenta la propuesta de R. J. Lipton, para
resolver instancias del problema SAT de la satisfactibilidad de la
lógica proposicional, usando las ideas de Adleman.
En el capítulo 6 se describen las máquinas moleculares, como
dispositivos capaces de ejecutar ciertos programas cuyas instrucciones pueden
ser realizadas en el laboratorio. Para ello, en primer lugar se describe una
máquina teórica (máquina splicing) que, en cierto sentido, es la
precursora de las máquinas moleculares. A continuación se presentan tres
modelos de computación molecular basados en ADN. El modelo no
restringido de Adleman fue el primer modelo abstracto de computación
molecular que se introdujo de manera explícita, y está inspirado en los
experimentos de Adleman y de Lipton. El modelo débil de Amos utiliza una
operación que elimina directamente una serie de cadenas del proceso
computacional. Estos dos modelos tienen la peculiaridad de que sus operaciones
moleculares primitivas no alteran la estructura interna de las moléculas de
ADN. El tercer modelo presentado, el modelo sticker, es
más interesante desde el punto de vista abstracto, ya que hace uso de las
moléculas de ADN como unidades de memoria susceptibles de ser modificadas
en tiempo de ejecución. Por ello, en el capítulo 7 se hace una
exposición exhaustiva de este último modelo, presentando una implementación
física en el laboratorio de una máquina sticker.
El capítulo 8 tiene como finalidad el análisis de la potencia
computacional de las máquinas moleculares presentadas en el capítulo 6.
Para ello, se describe una simulación de las máquinas de Turing
deterministas a través de la manipulación de moléculas de ADN, mediante
unas operaciones elementales y una codificación molecular adecuada. De
ahí que todas las máquinas capaces de realizar esas operaciones
elementales, tengan una potencia universal; es decir, la misma capacidad
computacional que las máquinas de Turing.
Cuando se diseña un programa molecular para resolver un cierto problema
de decisión, hay que demostrar que, efectivamente, dicho programa
resuelve el problema para cualquier ejemplar del mismo. En la primera
sección del capítulo 9 se asocia un sistema formal al par formado
por un programa molecular y un problema de decisión. De tal manera que
la demostración de que el programa resuelve el problema (es decir, la
verificación del programa) es equivalente a
establecer la adecuación y completitud del sistema formal asociado.
En las secciones 2 y 3 del capítulo 9 se presentan soluciones
moleculares de dos problemas clásicos NP-completos: el problema
SAT de la satisfactibilidad de la lógica proposicional y el
problema 3-COL de la coloreabilidad de un grafo no dirigido con
tres colores. Las soluciones que se describen son ejecutables en las
máquinas moleculares sin memoria introducidas en el capítulo 6, y se
establecen las correspondientes verificaciones formales mediante el uso
de una metodología sistemática que se presenta en estos modelos.
En la última sección del capítulo 9 se desarrolla una teoría de
combinatoria en el modelo débil de Amos; es decir, se describen
programas moleculares ejecutables en máquinas del citado modelo que
permiten generar todas las variaciones sin repetición, permutaciones y
combinaciones sin repetición. Además, se estudian algunas aplicaciones
interesantes de esta teoría de combinatoria para resolver cuatro
problemas relevantes NP-completos de la teoría de grafos: el
problema clique, el problema del recubrimiento de vértices,
el problema del conjunto independiente y el problema del
camino hamiltoniano en su versión dirigida y con dos nodos
distinguidos.
El último capítulo del libro está dedicado al estudio (diseño, análisis
y verificación) de soluciones moleculares en una máquina sticker, de
ocho problemas numéricos NP-completos: el problema del
emparejamiento tripartito (3-dimensional matching), el problema
subset-sum, el problema de la partición, el problema de la
mochila 0/1 (en su versión acotada y no acotada), el problema del
empaquetamiento de conjuntos
(set-packing), el problema del recubrimiento exacto y el problema
del recubrimiento minimal. Para ello, en la primera sección de
dicho capítulo se estudian distintas representaciones de los conjuntos
finitos en dichas máquinas y se resuelven algunos problemas relacionados
con esos conjuntos. En la segunda sección se resuelven los problemas
NP-completos citados a partir de las subrutinas diseñadas en el
capítulo anterior para conjuntos finitos.
Además, en este capítulos se
presenta una metodología para la verificación de programas en el modelo
sticker, en la que destaca el diseño de una función que permite
controlar, en cierto sentido, la evolución de la estructura interna de
cada una de las moléculas a lo largo de la ejecución. Esta metodología
es aplicada a las soluciones moleculares obtenidas en el modelo citado.
Aportaciones
A pesar del carácter eminentemente divulgativo del presente libro,
queremos destacar algunas de las aportaciones originales (desde el punto
de vista científico) que aparecen en el mismo.
- Formalización computacional del experimento de Lipton que resuelve el
problema SAT.
- Descripción como sistemas formales de programas
moleculares diseñados para resolver problemas de decisión.
- Diseño de soluciones moleculares de los problemas SAT, 3-COL
y HPP en los modelos no restringido de Adleman y débil de Amos.
- Estudio y desarrollo de una teoría de combinatoria molecular en el modelo
débil.
- Descripción de un método de representación de conjuntos numéricos en el
modelo sticker, usando la capacidad del modelo para identificar complejos de
memoria con funciones booleanas.
- Diseño de procedimientos moleculares en el modelo sticker que resuelven
los siguientes problemas: el problema del rellenado, el problema del
recubrimiento, el problema de la ordenación según la cardinalidad,
el problema de las familias disjuntas, y el problema del cálculo de
pesos sobre conjuntos.
- Diseño de las primeras soluciones moleculares de los siguientes problemas
{\bf NP}-completos: el problema del emparejamiento tripartito, el
problema subset-sum, el problema de la partición, el problema de
la mochila 0/1 acotado y 0/1 no acotado, el problema del
empaquetamiento de conjuntos, el problema del recubrimiento
exacto, y el problema del recubrimiento minimal.
- Presentación de una solución molecular del problema del recubrimiento
minimal, que mejora la solución dada por S. Roweis y otros.
- Desarrollo de una metodología para la verificación de programas en modelos
de computación molecular con o sin memoria.
- Aplicación de la metodología anterior a los programas diseñados en los
modelos considerados.
En 1998 comenzamos a trabajar de manera sistemática en modelos de
computación no convencionales, atraidos por las extraordinarias
perspectivas que se abrían con el experimento de Adleman a fin de
construir un ordenador molecular basado en la manipulación del ADN. Poco
después, entramos en contacto con Gheorghe Paun, reciente creador de
la Computación celular con membranas, transformando nuestra atracción en
fascinación por todo lo que estos nuevos paradigmas computacionales
podrían representar, tanto desde el punto de vista práctico
(construcción de ordenadores no basados en la manipulación electrónica
del silicio que mejoraran extraordinariamente el rendimiento de las máquinas), como desde el punto de vista teórico (al proporcionarnos
nuevos dispositivos abstractos susceptibles de ser utilizados para
atacar, desde otra perspectiva, la conjetura P =
NP).
El estudio sistemático del diseño, análisis y verificación de programas
moleculares es una tarea que se inicia en el año 2000, por
miembros del Grupo de Investigación en Computación Natural de la
Universidad de Sevilla.
Este libro es el primer texto escrito en lengua castellana dedicado a la
Computación Molecular basada en ADN (en la actualidad sólo existe otro
libro sobre este tema: DNA Computing. New Computing Paradigms de
Gh. Paun, Gr. Rozenberg y A. Salomaa, Springer Verlag,
1998, escrito en lengua inglesa y que ya ha sido traducido al japonés,
ruso y chino). Esperamos y confiamos que su contenido proporcione métodos y
técnicas que puedan ser de utilidad para estudios posteriores acerca de
dichos modelos no convencionales, en particular para el análisis de la
robustez de procedimientos complejos descritos en dichos modelos y para
la mecanización de los procesos de verificación a través de sistemas de
razonamiento automático (como ACL2, A Computational
Logic for an Applicative Common Lisp, y PVS,
Prototype Verification System).
Para finalizar, queremos hacer constar nuestro reconocimiento al
Vicerrectorado de Investigación de la Universidad de Sevilla que, a
través del II Plan Propio de Investigación, ha hecho posible la
publicación de este libro.
También queremos agradecer la colaboración especial, como
evaluadores externos del Dr. Genaro López Acedo, del Dr. José
A. Alonso Jiménez y de la Dra. Elisa Revilla Torres, por el tiempo
dedicado a la lectura crítica del texto así como por sus atinadas
observaciones. A Daniel Díaz Pernil por su aportación en el desarrollo
de la teoría de combinatoria. Y, por supuesto, estamos en deuda con
Alvaro Romero Jiménez por su paciencia en la minuciosa corrección
del texto y por sus acertadas sugerencias.
Y cómo no, debemos tener un emotivo recuerdo a nuestras familias que ha
suplido nuestra ausencia física del hogar con grandes dosis de
comprensión, con mucha generosidad y, sobretodo, con un inmenso cariño.
Mario de J. Pérez Jiménez
Fernando Sancho Caparrini
Sevilla, noviembre de 2002