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.

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