Computación basada en ADN

Computación basada en ADN

La Computación basada en ADN consiste en usar moléculas de ADN en vez de procesadores basados en silicio. Las ventajas de la computación por ADN se basan en dos características fundamentales:

  • El gran paralelismo de las hebras de ADN. Muchos de los problemas considerados intratables, pueden ser resueltos haciendo una búsqueda exhaustiva sobre todas las soluciones posibles. Sin embargo, a la fecha (2008), la dificultad consiste en el hecho que tal búsqueda es demasiado grande como para poder ser realizada usando la tecnología actual. Por otro lado, la densidad de información almacenada en hebras de ADN y la facilidad de construir muchas copias de ellas puede convertir esas búsquedas en una posibilidad real.
  • La complementariedad de Watson-Crick. La complementariedad es algo que viene gratis en la naturaleza. Cuando se unen dos hebras (en condiciones ideales) se sabe el opuesto a cada miembro, no hay necesidad de verificarlo.

Contenido

Historia

Probablemente la primera vez que fue mencionada la computación sub-microscópica fue en la charla Hay Espacio de sobra allí abajo, por el físico Richard Feynman.

Leonard Adleman, de la Universidad del Sur de California en inició el estudio en este campo, en 1994[1] . Adleman probó la utilidad, al menos teórica, del uso del ADN para resolver problemas. En particular, logró resolver el Problema del camino Hamiltoniano de 7 nodos. Desde los primeros experimentos de Adleman, se han realizado numerosos avances, y se ha probado que se pueden construir varias Máquinas de Turing[2] .[3]

Esta es una tecnología todavía en etapas bastante tempranas, por lo cual su uso existe más que nada como una opción teórica. Todavía usar computación convencional es una opción más eficiente que usar este método.

Modelo de Stickers

Consideremos por ejemplo un modelo de computación con ADN conocido como sticker model. Este modelo usa dos tipos básicos de hebras simples de ADN, llamadas hebras memoria y hebras sticker. Una hebra memoria tiene n bases de largo y contiene k sub-hebras no superpuestas, cada una de largo m. Así que, n\geq mk. Aunque no es necesario, se supondrá para la explicación, que cada sub-hebra sigue otra consecutiva (sin ninguna otra base entre medio). Cada sub-hebra representa exactamente una variable booleana, un bit. Las subhebras deben ser suficientemente diferentes unas de otras. Cada sticker es de largo m y complementario a una y sólo una sub-hebra.

Una sub-hebra está prendida o apagada, dependiendo de si tiene unido su sticker o no. Si tiene su sticker pegado, está prendida (es verdadera o 1), en el otro caso está apagada (falso o 0).

Es importante crear las hebras memoria de tal forma que un sticker no pueda pegarse entre dos sub-hebras. Hay que considerar también que no todas las cadenas son posibles, por lo que al hacer un experimento real hay que buscar un óptimo.

Ejemplo de una molécula de ADN del modelo de stickers. Los stickers de abajo son los complementarios de los de arriba.

Tanto en el experimento de Adleman, como en la solución de Richard J. Lipton del problema de satifacibilidad, no hay una hebra larga de la cual partir, sino que hebras cortas que se van uniendo paso a paso, dejando un sobrante para que se pueda pegar otra hebra en cada paso. La densidad de información en ambos casos (con hebras largas o cortas), es básicamente la misma \frac{1}{m} bits por base. Aunque el máximo teórico es dos bits por base, una densidad tan alta deja cualquier computador molecular basado en separación peligrosamente propenso a errores.

Operaciones

El elemento básico es un tubo test, o simplemente tubo, el cual es un multiconjunto de hebras memorias. Las operaciones válidas son: merge (combinar), separate (separar), set (encender), y clear (apagar).

  • La operación merge es mezclar 2 tubos en uno. Así las memorias de dos tubos de entrada con sus stickers pegados sin perturbaciones se combinan para formar el multiconjunto unión de ambos.
  • La operación separate produce, dado un tubo de entrada N, y un entero i, 1\leq i\leq k, dos tubos nuevos, +(N,i) y -(N,i). El tubo +(N,i) (respectivamente -(N,i)) consiste en todos las hebras memoria en el tubo original N, donde la i-ésima sub-hebra está prendida (respectivamente apagada).
  • Para un tubo dado N y un entero i, 1\leq i\leq k, la operación set produce un nuevo tubo test set(N,i), donde la i-ésima sub-hebra de cada hebra memoria está encendida. (Esto es, se le adhiere el sticker apropiado si la i-ésima subhebra estaba apagada, y se deja sin cambios si ya tenía uno).
  • Finalmente para un tubo dado N y un entero i, 1\leq i\leq k, la operación clear produce un nuevo tubo test clear(N,i), donde la i-ésima sub-hebra de cada hebra memoria está apagada, es decir, un eventual sticker fue removido de ella.

La computación consiste en una secuencia de operaciones merge, separate, set y clear. Las entradas y salidas (Input, Output) son tubos test. Para leer la salida, una hebra memoria debe ser aislada del tubo y determinar que stickers tiene adheridos o sino, determinar si el tubo de salida no tiene hebras memoria.

La entrada inicial (tubo) será una biblioteca de hebras memoria. En particular una biblioteca (k,l), 1\leq l\leq k consiste en memorias con k sub-hebras, de las cuales las últimas k-l están apagadas, mientras las primeras l están prendidas o apagadas en todas las combinaciones posibles. En binario sería w0kl, con w una cadena binaria arbitraria de tamaño l. En el tubo inicial, las primeras l hebras de la memoria representan la entrada, y el resto se para uso intermedio y salida.

El paradigma computacional asociado con el modelo sticker es resolver problemas difíciles buscando exhaustivamente en todas las combinaciones posibles de largo l. Todos las 2l posibles entradas son analizadas en paralelo. Este paradigma es la esencia de la computación de ADN en general.

Aplicaciones

El 2002, investigadores del Instituto Weizmann de Ciencias en Rehovot, Israel, crearon un computador programable, compuesta de enzimas y moléculas de ADN.[4] El 28 de abril de 2004, Ehud Shapiro, Yaakov Benenson, Binyamin Gil, Uri Ben-Dor, y Rivka Adar del Instituto Weizman anunciaron en la revista Nature que habían construido un computador basado en ADN.[5] Aunque era sólo un autómata finito determinístico, de dos estados, al unirlo con un módulo de entrada y salida, fue capaz de diagnosticar actividad cancerígena y liberar drogas para su tratamiento.

Ejemplo de Aplicación

Se muestran a continuación los pasos seguidos por Adleman para resolver el problema del camino Hamiltoniano.

Se tiene un grafo direccionado G con n vértices vi. Existen aristas conectando algunos vértices. Se denota la arista que conecta al vértice vi con vj como ei→j.

Para simplificar el ejemplo, y sin pérdida de generalidad, se considera que se comienza en el vértice v1 y se termina en el vértice vn

Los pasos son:

  1. Generar caminos aleatorios.
  2. Seleccionar aquellos que comiencen con v1 y terminen con vn.
  3. Seleccionar sólo aquellos caminos que cuenten con exactamente n vértices.
  4. Seleccionar sólo aquellos caminos que tengan cada vértice una sola vez.
  5. Si queda algún camino en la muestra, responder SI, de otra forma responder NO.

La forma en que Adleman lo solucionó usando ADN se muestra a continuación.

A cada vértice vi del grafo se le asigna un oligonucleótido si de un largo de 20 pares base. Éstos se generan al azar, cuidando de que ninguno sea idéntico a otro.

A su vez, a cada arista ei→j se le asigna un oligo Ei→j, compuesto de una forma particular; se forma un segundo oligo tomando la segunda mitad del vértice de partida y la primera mitad del vértice de llegada. El oligo que se le asigna a la arista es el complemento de esta hebra.

El primer paso se lleva a cabo mezclando muestras de grandes cantidades de oligos representando vértices y aristas, y se agrega una solución de ADN ligasa para generar una gran cantidad de caminos aleatorios. Gracias a la composición de los oligos, se asegura que se respete la estructura del grafo, y gracias al tamaño de la muestra es probable que el camino Hamiltoniano buscado esté presente.

Para ejecutar el segundo paso, se lleva a cabo un proceso de RCP usando como cebadores los oligos correspondientes a sn y el complemento de s0. Notar que estos dos cebadores representan los complementos de los extremos de las cadenas que interesan, que son las que comienzan con s0 y comienzan con sn. Así se asegura la replicación de los caminos válidos para el siguiente paso solamente.

El tercer paso se efectúa usando electroforesis. Este proceso separa las moléculas en función de su tamaño, dejando las más cortas a un lado y las más largas al otro lado de la matriz. Se seleccionan sólo las moléculas presentes en el rango de largo apropiado para el próximo paso.

El cuarto paso se lleva a cabo mediante un proceso de purificación de proteinas. Se separan las hebras de los caminos, como también las hebras para cada vértice. Se asocian las hebras simples de los vértices con partículas magnéticas. Luego se asocia cada hebra simple de los caminos del paso cuatro con estas partículas, mientras que los caminos que no se logran asociar, por la ausencia de algún vértice, son removidos junto con la solución. Se efectúa este proceso para cada vértice en el camino.

Con las muestras restantes se efectúa un proceso de RCP, al igual que el descrito anteriormente, para luego aplicar electroforesis. Se analiza la matriz para ver si quedan o no muestras, y se responde si el camino fue encontrado o no.

Véase también

Enlaces externos

Referencias

  1. Leonard M. Adleman (1994-11-11). «Molecular Computation Of Solutions To Combinatorial Problems». Science (journal) 266 (11):  pp. 1021–1024. http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf.  — La primera publicación de computación basada en ADN. Describe una solución realizada en Problema del camino Hamiltoniano dirigido.
  2. Dan Boneh, Christopher Dunworth, Richard J. Lipton, and Jiri Sgall (1996). «On the Computational Power of DNA». DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 71. http://citeseer.ist.psu.edu/boneh95computational.html.  — Describe una solución al Problema de satisfacibilidad booleana.
  3. Lila Kari, Greg Gloor, Sheng Yu (January 2000). «Using DNA to solve the Bounded Post Correspondence Problem». Theoretical Computer Science 231 (2):  pp. 192–203. http://citeseer.ist.psu.edu/kari00using.html.  — describe una solución al Problema de satisfacibilidad booleana ligado, un problema duro en promedio, NP-completo.
  4. Computer Made from DNA and Enzymes
  5. Yaakov Benenson1, Binyamin Gil, Uri Ben-Dor, Rivka Adar, Ehud Shapiro (2004-04-28). «An autonomous molecular computer for logical control of gene expression». Nature (journal) 429:  pp. 423–429. http://www.wisdom.weizmann.ac.il/~lbn/other_links/ShapiroNature2004.pdf. 

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Computación cuántica — La esfera de Bloch es una representación de un qubit, el bloque de construcción fundamental de los computadores cuánticos. La computación cuántica es un paradigma de computación distinto al de la computación clásica. Se basa en el uso de qubits… …   Wikipedia Español

  • Secuenciación de ADN — La secuenciación de ADN es un conjunto de métodos y técnicas bioquímicas cuya finalidad es la determinación del orden de los nucleótidos (A, C, G y T) en un oligonucleótido de ADN. La secuencia de ADN constituye la información genética heredable… …   Wikipedia Español

  • Cromosoma inorgánico basado en silicio — Dispositivo Inchrosil. Un cromosoma inorgánico basado en silicio (en inglés Inorganic Chromosome based in Silicon (InChroSil)) es un circuito electrónico que emula el comportamiento y la estructura del ADN orgánico, es decir, con componentes… …   Wikipedia Español

  • Computadora analógica — Computador analógico. Una computadora analógica u ordenador real es un tipo de computadora que utiliza dispositivos electrónicos o mecánicos para modelar el problema que resuelven utilizando un tipo de cantidad física para representar otra. Para… …   Wikipedia Español

  • Biocomputación — Saltar a navegación, búsqueda Biocomputación puede referirse a: La construcción y uso de biocomputadores, ordenadores que utilizan componentes biológicos o actúan como organismos vivos. En este sentido, se relaciona cercanamente con la… …   Wikipedia Español

  • Proyecto EELA — Saltar a navegación, búsqueda El proyecto EELA (E infraestructura compartida entre Europa y Latino América) busca construir un puente digital entre las iniciativas de e Infraestructuras existentes, las que están en proceso de consolidación en… …   Wikipedia Español

  • Bioinformática — Saltar a navegación, búsqueda La bioinformática, según una de sus definiciones más sencillas, es la aplicación de tecnología de computadores a la gestión y análisis de datos biológicos.[1] Los términos bioinformática, biología computacional y, en …   Wikipedia Español

  • Alineamiento de secuencias — Un alineamiento de secuencias en bioinformática es una forma de representar y comparar dos o más secuencias o cadenas de ADN, ARN, o estructuras primarias proteicas para resaltar sus zonas de similitud, que podrían indicar relaciones funcionales… …   Wikipedia Español

  • Historia de la biología — La portada del poema sobre la evolución de Erasmus Darwin The Temple of Nature muestra a una diosa que retira el velo de la naturaleza (en la persona de Artemisa). La alegoría y la metáfora han desempeñado a menudo un papel importante en la… …   Wikipedia Español

  • Raymond Kurzweil — Saltar a navegación, búsqueda Raymond Kurzweil Raimond Kurzweil Nacimi …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”