Menú

Máquinas inspiradas en la naturaleza viva (II)

4 de abril de 2007

Atención: Esta anotación es la continuación de Máquinas inspiradas en la naturaleza viva (I)

Hace algunas semanas estuve escribiendo un poco acerca de la problemática actual en la computación, las limitaciones de los ordenadores tradicionales y la necesidad de superar esas limitaciones para resolver problemas de la vida real. Como decía, la existencia de problemas NP-Completos que no son posibles de resolver en tiempo polinomial en una computadora convencional, ha llevado a los investigadores a diseñar nuevos modelos de computación que en un futuro puedan superar estas barreras de eficiencia. Muchos de vosotros seguramente habrá leído sobre la computación cuántica y cómo con ella se ha consigue (teóricamente) romper algunas claves de encriptación.
Efectivamente, la computación cuántica es un modelo de computación no convencional. Sin embargo, yo quería hablar otros dos modelos, menos conocidos, que entran dentro de la denominada Computación Natural: La Computación Molecular basada en ADN (Adleman, 1994) y la Computación con Membranas (Gh. Paun, 1998).

Computación Molecular basada en ADN

En 1953 James Watson y Francis Crick presentaron su modelo de ADN de doble hélice. En él se describía la composición de los cromosomas como una doble hélice, donde cada una de ellas estaba a su vez compuesta por una cadena de aminoácidos. Este estudio les supuso el Premio Nobel.

ADN40 años después, Leonard Adleman, inventor de la criptografía RSA de la que hablábamos un poco en artículo anterior, estaba leyéndose el trabajo de estos dos físicos. Observó que en la mitosis de la célula, cuando se produce la replicación del ADN, interviene una enzima, la polimerasa. Al fijarse en cómo esta enzima creaba una copia perfecta de la información genética, se maravilló con el parecido que tenía ésta en su forma de actuar con una máquina de Turing de doble cinta (estas cosas siempre me hacen pensar en si las matemáticas se inventan o se descubren…). Inmediatamente se puso a trabajar en la elaboración de un experimento que utilizara el ADN para realizar cálculos computacionales. En 1994 publicaría este experimiento en una revista científica (la revista Science, creo), en el que resolvía una instancia del problema del Camino Hamiltoniano (un problema NP-Completo) con 7 vértices. Hay que aclarar que tanto el problema como la solución se encontraban codificados apropiadamente en cadenas de ADN, donde el alfabeto está formado por las posibles bases nitrogenadas: Adenina, Citosina, Timina y Guanina.
¿Cómo es posible construir un modelo computacional basado en ADN? Bueno, si nos abstraemos lo suficiente podemos llegar a ver que para construir un modelo computacional necesitamos dos cosas: Un soporte para almacenar información y la posibilidad de realizar operaciones sobre esa información. Y esto es lo que Adleman descubrió y aprovechó para construir su modelo, formado principalmente por tubos (recipientes) que contenían multiconjuntos de agregados (datos), y las operaciones de extraer de un tubo, meclar dos tubos y detectar alguna sustancia en un tubo. Con este modelo, su experimento consistió, resumiendo mucho, en:

  1. Generar aleatoreamente el conjunto de secuencias de vértices, donde cada una es un posible camino.
  2. Eliminar, por filtrado, las codificaciones que no correspondan con los caminos que empiecen y acaben por los vértices de los que parte el problema
  3. Eliminar, también por filtrado, todas las secuencias no compuestas por los n vértices del grafo.
  4. Eiminar todas las secuencias que contengan algún vértice repetido.
  5. Si el tubo final, resultado de todos los filtrados anteriores, sigue conteniendo secuencias de ADN, devolver sí. En caso contrario, devolver no.

Y bueno, por último, quería contar qué es lo que cambia en este modelo con respecto a un modelo de computación tradicional: La clave está en el paralelismo masivo. El hecho de que en un tubo se estén realizando millones de operaciones simultáneas por segundo, hace posible que problemas NP-Completos se puedan resolver en tiempos polinomiales. Es por ello que la computación basada en ADN haya tenido tanto éxito, porque constituye una huída hacia adelante en la investigación para la resolución de problemas de la vida real que con máquinas convencionales no pueden ser resueltos.

Continuará…

3 Comentarios en Máquinas inspiradas en la naturaleza viva (II)

  1. Avatar de <a href='http://www.notenones.com' rel='external nofollow' class='url'>despierto</a>

    despierto dice:

    7/4/2007, 02:14

    El año pasado asistí a un seminario sobre computación basada en ADN y promete mucho, aunque el aparato matemático y formal que hay detrás es bastante pesado.
    A mi me encantó cuando, como se explica en la entrada, nuestro profesor expuso el problema del viajante de comercio y o reformuló en términos de computación con ADN transformando un problema NP-Completo en un problema O(1)!!! BRUTAL.
    Al final será cierto que NP=N y quién sabe si N es igual a 1 😀

  2. Avatar de jacortez

    jacortez dice:

    27/1/2009, 17:23

    hola pana super interesante y me ayudo mucho a entender el experimento de los tubos de ensayo gracias por su aporte a la educación…………

  3. Avatar de <a href='http://hotmail' rel='external nofollow' class='url'>patricia</a>

    patricia dice:

    24/9/2009, 22:39

    bueno nada de lo que esta aki me sirve por que ustedes estudien mas y tendran una pagina fabulosa asi que no sirven ustedes no sirven xD

Leave a comment