La computació basada en ADN és una rama emergent de la computació que utilitza ADN, coneixements en bioquímica i eines de biologia molecular en lloc de la tecnologia computacional tradicional in silico. La recerca i el desenvolupament en aquesta àrea implica coneixements teòrics, experimentals i aplicacions de la computació basada en ADN. Tot i que aquest camp es va iniciar originalment com la demostració de l'aplicació computacional per Leonard Adleman l'any 1994, avui en dia s'ha ampliat a molts altres àmbits. En són exemples el desenvolupament de noves tecnologies d'emmagatzematge, modalitats d'obtenció d'imatges a escala nanomètrica, controladors sintètics i xarxes de reacció, etc.
Història de la computació del ADN i la programació molecular miniatura|Fotografia d'en Leonard Adleman, considerat pare de la computació basada en ADN.|284x284px Leonard Adleman, de la Universitat de Southern California (USC) va ser el primer en desenvolupar aquest camp l'any 1994. Adleman va demostrar la utilitat del ADN, almenys de forma teòrica, per resoldre problemes. Adleman va ser capaç de resoldre el problema del camí Hamiltonià de set punts. Des dels experiments inicials de Leonard Adleman hi ha hagut avenços i vàries màquines de Turing s'ha provat que es poden construir.
Aquest camp s'ha estes en varies àrees. L'any 1995 Eric Baum va proposar la idea de la memòria basada en ADN. Basant-se en la seva alta densitat, un fragment petit de ADN podia emmagatzemar una gran quantitat de dades. Aquest descobriment va permetre estendre l'horitzó de la computació basada en ADN en el de la tecnologia de memòria, tot i que les demostracions in vitro no es van realitzar fins al cap d'una dècada.
El camp de la informàtica basada en ADN es pot classificar com un subcamp del camp de la nanociència de l'ADN, un camp que va ser iniciat per Ned Seeman aproximadament una dècada abans de la demostració de Leonard Adleman. Cap als anys 80 la idea original de Ned era construir estructures arbitràries basant-se en la capacitat de auto-formació ascendent per aplicacions en cristal·lografia. Aquesta idea va transformar-se en el camp de l'autoensablatge estructural de l'ADN, que actualment està molt sofisticat. Una estructura autoensablada es pot formar i tenir una alçada de nanòmetres fins a micròmetres, tal com s'ha demostrat l'any 2018.
L'any 1994, el grup del Prof. Seeman va demostrar que es podien formar estructures entramades utilitzant només una col·lecció petita de component d'ADN. Mentre que la demostració d'Adleman mostrava la possibilitat de crear ordinadors basats en ADN, el disseny va ser arbitrari perquè el número de nodes en el gràfic creix i, per tant, el nombre de components d'ADN requerits també creixerien exponencialment. Així, els informàtics i els bioquímics van començar a explorar el camp de l'autoensamblatge amb l'objectiu d'utilitzar una col·lecció petita d'ADN com a peçes per a crear combinacions creixents arbitràries. Cap als anys 90, altres conceptes van ser explorats de forma teòrica com utilitzar la cristalografia basada en ADN, la capacitat dels sistemes basats en ADN, memories i discs d'ADN i nanorobots basats en ADN.
L'any 2003, el grup de John Reif va demostrar que es podia crear nanorobots caminadors basats en ADN similars als robots caminadors que seguien una línia. Van utilitzar biologia molecular com a font d'energia pel caminador, que gràcies a això es podia moure per una seqüència d'àcids nucleics. Des d'aquesta inicial demostració, una gran varietat de caminadors basats en ADN s'han desenvolupat.
Aplicacions, exemples i desenvolupaments recents miniatura|189x189px|Esquema representatiu d'un camí hamiltonià en una xarxa de 6 vèrtexs. miniatura|328x328px|Esquema representatiu de la resolució del problema de camins hamiltonians amb ADN. L'any 1994 Leonard Adleman va presentar el primer prototip d'ordinador basat en ADN, anomenat TT-100 (Test Tube amb 100 microlitres). El tub d'assaig contenia 100 microlitres de líquid saturat d'ADN i va ser capaç de resoldre una versió simple del problema del circuit Hamiltonià. En l'experiment, el circuit es va implementar com si fos un problema d'un venedor ambulant que havia de vendre a diferents ciutats. Cada fragment d'ADN representava cada ciutat que el venedor havia de visitar. Cada fragment o ciutat, era capaç d'intereccionar amb altres fragments o ciutats i crear unions que representaven els camins interurbans. Aquests fragments eren creats i mesclats en el tub d'assaig; en segons, els fragments més petits formaven fragments més grans que representaven les diferents rutes. Amb posteriors reaccions químiques els fragments que representaven les rutes més llargues s'eliminaven. Els fragments resultants eren la solució al problema del venedor ambulant; els diferents camins entre ciutats. Tot i que el problema es pogués resoldre, l'experiment durava una setmana i les limitacions tècniques per avaluar els resultats feien que no es pogués aplicar a la pràctica. Tot i així, el problema es podria resoldre, i això ja és una prova de concepte.
Problemes combinatoris Els primers resultats dels problemes van ser obtinguts per Leonard Adleman (NASA JPL).
L'any 1994 soluciona un camí Hamiltonià en un gràfic de 7 punts. L'any 2002 soluciona un problema NP-complet i un problema 3-SAT (problema de satisfacibilitat booleana) amb 20 variables.
Tres en ratlla L'any 2002, J.Macdonald, D. Stefanovic i M. Stojanovic van crear un ordinador basat en ADN capaç de jugar al tres en ratlla contra un humà. La calculadora consisteix en 9 bits que corresponen a 9 quadrats en el joc, conformant el taulell. Cada bin conté un substrat i vàries combinacions d'enzims d'ADN. El substrat està compost d'una cadena de DNA que en un extrem té unit un component fluorescents mentre que a l'altre extrem té unit un grup repressor. El component fluorescents només s'activa si les molècules del substrat estàn fragmentades per la meitat. Els enzims d'ADN simulen funcions lògiques. Per exemple, el constructe no estarà plegat si s'introdueixen dos cadenes d'ADN que reprodueixen la funció lògica AND.
Per defecte, es considera que l'ordinador juga en primer lloc i a la casella central del tauler. Els jugadors humans comencen amb 8 cadenes d'ADN diferents que corresponen a les 8 caselles restants del taulell. Per jugar en una casella determinada i, l'humà introdueix la cadena corresponent al resultat de i. Les cadenes d'ADN interactuen amb enzims de DNA que es troben en cada casella, i aquests, tallen la cadena introduida, alliberant el component fluorescent. La casella, per tant, esdevé fluoresent, indicant en quina casella s'està jugant. Els enzims d'ADN són disposats i dividits en les caselles de tal manera que s'assegura que tota persona que jugui contra l'ordinador té la possibilitat de guanyar i/o quedar en empat amb l'ordinador, com succeeix en el tres en ratlla original.
Xarxa neural basada en computació Kevin Cherry i Lulu Qian, ambdós de Caltech, van desenvolupar una xarxa neural artificial basada en ADN capaç de reconèixer fins a 100-bits de dígits escrits a mà. Per aconseguir-ho, van programar amb anterioritat un ordinador amb una col·lecció de pesos representats per la variació de concentracions de molècules de pes, que posteriorment van ser afegides al tub d'assaig que contenia l'entrada de les cadenes de DNA.
Millora de la velocitat amb computació localitzada basada en caché Un dels reptes de la computació basada en ADN és la velocitat. Tot i que l'ADN és un substrat biologicament compatible i presenta avantatges com que pot ser utilitzat en camps on la tecnologia basada en silice no pot, la velocitat de computació és molt lenta. Per exemple, un circuit d'arrels quadrades utilitzat com a marcador va ser completat en 100 hores. S'han proposat alternatives que utilitzen enzims per tal de crear circuits més ràpids i compactes. Chatterjee et al. van demostrar que es podia augmentar la velocitat de computació creant circuits d'ADN localitzats. Aquest concepte va ser posteriorment estudiat i desenvolupats per altres grups. La idea va ser proposada en el camp de l'arquitectura d'ordinadors i s'ha adaptat en aquest camp. En l'arquitectura d'ordinadors, es coneix molt bé que si les instruccions executades en cadena es carreguen en el caché, inevitablament això ens permetrà augmentar la velocitat de computar. Aquesta idea és el principi de localització. La raó és que no hi ha necessitat d'introduir les instruccions dins i fora de la memòria principal, que és el que enlentiria el procés. En computació amb ADN, les cades d'ADN responsables per la computació són fixades a la placa d'assaig com un substrat que assegura la proximitat física amb les portes de computació. Aquestes tècniques de computació han demostrat tenir potencial en disminuir el temps de processament en ordres de magnitud.
Computació renovable o reversible La recerca posterior en computació de DNA ha conduit a la producció de la computació reversible de DNA; apropant un pas més a la tecnologia basada en silice utilitzada en ordinadors. En particular, John Reif i el seu grup a la Universitat de Duke va proposar dos tècniques dierents per reutilitzar els complexos d'ADN. El primer disseny utilitza portes d'ADN bicatenari, mentre que el segon utilitza els complexos d'ADN en forquilla (Hairpin structures). Tot i que ambdós dissenys tenen alguns problemes, com pèrdues de reaccions, els dos dissenys suposen un avenç molt important en el camp de la informàtica basada en ADN. Altres grups han intentat solucionar el problema de la pèrdua de reacció de les portes d'ADN bicatenari.
Mètodes Hi ha múltiples mètodes per construir un dispositiu computacional basat en ADN, cadascun amb els seus avantatges i inconvenients. La majoria es basen en les portes lògiques bàsiques (AND, OR, NOT) i la lògica digital bàsica de l'ADN. Algunes de les diferents bases inclouen els enzims d'ADN, els desoxioligonucleòtids, els enzims i l'intercanvi de toeholds.
Mecanismes de desplaçament de cadena miniatura|Esquema de reacció de desplaçament de cadena mitjançat per toeholds. En aquest exemple la cadena vermella s'uneix a la cadena verda per la seva regió toehold de cadena senzilla (regió 1). Seguidament es produeix un procés de migració en rama en la regió 2: la cadena blava és desplaçada i s'allibera del complexe. Reaccions com aquestes es fan servir per reconfigurar dinàmicament o assemblar nanoestructures d'àcids nucleics. A més a més, les cadenes vermella i blava poden ser utilitzades com a senyals en una porta lògica molecular. |348x348pxL'operació més fonamental a la computació basada en ADN i la programació molecular és el mecanisme de desplaçament de cadena. Actualment hi ha dues formes per dur a terme aquest mecanisme:
Desplaçament de cadena mitjançat per toeholds (TMSD) Desplaçament de cadena operat per polimerasa (PSD)
Intercanvi de toeholds A part dels esquemes de desplaçament de cadena simples, els ordinadors d'ADN també s'han construït fent servir el concepte d'intercanvi de toeholds. En aquest sistema, una cadena d'ADN input s'uneix a un sticky end, o toehold, en una altra molècula d'ADN. Això permet la creació de components lògics modulars com les portes AND, OR i NOT i amplificadors de senyal, els quals poden ser enllaçades arbitràriament en ordinadors grans. Aquesta classe d'ordinadors d'ADN no requereix enzims o cap capacitat química de l'ADN.
Xarxes d'interacció química (CRN)