Revista Art-emis
Căutând calculatoare în celula biologică (3) PDF Imprimare Email
Acad. Gheorghe Păun   
Joi, 13 Noiembrie 2014 21:37

Acad. Gheorghe PăunDiscurs de recepţie la Academia Română - 24 octombrie 2014

Totul începe cu Turing

Într-un anume sens şi într-o anume măsură, întreaga istorie a informaticii (teoretice) este legată de biologie, a căutat şi a găsit surse de inspiraţie în aceasta. Am menţionat deja că Turing, în 1935-1936, când a introdus maşina care-i poartă numele, a încercat să simuleze modul uman de a calcula. După un deceniu, McCullock, Pitts, Kleene au fundamentat teoria automatelor finite plecând de la modelarea neuronului şi a reţelelor de neuroni. Ceva mai târziu, acelaşi punct de plecare a condus la ceea ce astăzi este numit calcul neural.Interesant este că începuturile acestei discipline pot fi identificate în lucrări nepublicate ale aceluiaşi Alan Turing. Avem aici un episod interesant, care poate ilustra influenţa psihologiei şi sociologiei asupra ştiinţei, vorbind despre lideri de grup neinspiraţi şi despre cercetători interesaţi mai mult în cercetarea lor decât în publicarea rezultatelor. Anume, în 1948, Turing a scris o scurtă lucrare, intitulată „Intelligent machinery”, care a rămas nepublicată până în 1968, deoarece şeful său de la National Physical Laboratory din Londra, ironic, pe nume sir Charles Darwin, nepotul celebrului naturalist omonim, a scris pe colţul lucrării „schoolboy essay”, eseu şcolăresc, oprind publicarea. „Această lucrare a fost primul manifest al inteligenţei artificiale. În lucrare [...], matematiciAnul britanic nu numai că a pus bazele conecţionismului, dar a şi introdus, într-un mod strălucitor, multe dintre conceptele care ulterior au devenit centrale în inteligenţa artificială, în unele cazuri după ce au fost reinventate de alţii...”. [1] Printre altele, lucrarea lui Turing introduce două tipuri de reţele de „neuroni” conectaţi aleatoriu, ca un pas înspre crearea unei maşini inteligente, una dintre trăsăturile cheie ale acestor reţele fiind aceea de a învăţa, de a se antrena în vederea rezolvării de probleme. Este calcul neural avant la lettre, cu ideile redescoperite ulterior, fără referire la Turing. Detalii despre „maşinile neorganizate” ale lui Turing pot fi găsite şi în C. Teuscher[2], şi C. Teuscher[3], De asemenea, se pot afla mai multe despre manuscrisele nepublicate ale lui Turing şi despre eforturile recente de valorificare a lor din alte surse.[4]

Acelaşi Turing, în acelaşi an, 1948, a propus şi „căutarea genetică sau evolutivă”, primele idei ale calculului evolutiv de mai târziu, domeniu care sintetizează acum mai multe ramuri (re)lansate de-a lungul anilor: programare evolutivă (L.J. Fogel, A.J. Owens, M.J. Walsh), algoritmi genetici (J.H. Holland), strategii evolutive (I. Rechenberg, H.P. Schwefel), toate trei iniţiate în anii 1960, şi programarea genetică (J.R. Koza, anii 1990). Primul experiment de „optimizare prin evoluţie şi recombinare” pe calculator a fost efectuat în 1962, de către Bremermann.[5] N-ar fi cu totul surprinzător dacă printre manuscrisele lui Turing s-ar descoperi şi idei legate de calculul cu A.D.N. - să ne amintim că Turing a murit în iunie 1954, iar articolul din Nature, în care J.D. Watson şi F.H.C. Crick descriau structura dublu catenară, elicoidală, a moleculei de ADN fusese publicat cu un an înainte.[6] Merită menţionate alte două concepte care fac carieră în informatică şi care ne dau dreptul să spunem că „totul începe cu Turing”. Turing însuşi şi-a pus problema şi a propus căi prin care... se poate calcula mai mult decât Turing, imaginând maşini Turing cu oracol, subiect iarăşi popular în computabilitatea de azi. De asemenea, el poate fi considerat precursor nu numai al inteligenţei artificiale, ci şi al domeniului numit viaţă artificială: în ultimii săi ani, Turing a fost interesat de morfogeneză, de modelarea evoluţiei de la genele unui ovul fertilizat la structura unui animal.

Un exemplu încurajator: algoritmii genetici

Înainte de a trece la calculul cu A.D.N. şi la calculul membranar, subiecte la care voi intra în mai multe detalii, să mai zăbovim puţin asupra unei ramuri a calculului inspirat din biologie care, la prima vedere, este surprinzător de eficient. Este vorba despre algoritmii genetici, folosiţi pentru rezolvarea de probleme de optimizare complexe, pentru care nu există algoritmi propriu-zişi (determinişti) sau aceşti algoritmi nu sunt eficienţi. Sloganul subînţeles poate părea derutant: atunci când nu ştii încotro să mergi, mergi la întâmplare, cu menţiunea că în cazul algoritmilor genetici „întâmplarea” este direcţionată, ea se face „ca în natură, în evoluţia speciilor”.Totul este o preluare metaforică a unor elemente din evoluţia darwiniană: să presupunem că avem o funcţie de două variabile (reprezentarea ca o suprafaţă de teren, cu văi şi dealuri, este sugestivă) căreia trebuie să-i găsim maximul (unul dintre ele, dacă există mai multe). Dacă nu putem aborda problema analitic, alegem să umblăm la întâmplare prin domeniul de definiţie, căutând maximul. Reprezentăm punctele din domeniu sub forma unor „cromozomi”, şiruri binare de lungime constantă. Alegem (la întâmplare sau prin altă metodă) un număr de puncte de plecare, calculăm valoarea funcţiei pentru ele. Trecem apoi la „evoluţie”: luăm „cromozomii” doi câte doi şi îi „încrucişăm” (crossover), adică îi secţionăm la o poziţie dată şi recombinăm fragmentele, prefixul unuia cu sufixul celuilalt şi invers. Obţinem doi „cromozomi” noi, descriind doi „indivizi” din „generaţia” următoare. Calculăm funcţia pentru noii „cromozomi”, amestecăm generaţiile şi reţinem numai o parte dintre indivizi, pe cei cu valorile mai bune ale funcţiei. Repetăm de un număr precizat de ori, alegem soluţia cea mai bună pe care am găsit-o până atunci şi ne oprim.

Nimic nu garantează că ajungem la soluţia problemei, că nu ne blocăm, de pildă, într-un maxim local, fără a mai putea ieşi din el, dar, şi aici este surpriza (plăcută), într-un număr semnificativ de aplicaţii practice, strategia funcţionează. Sigur, există nenumărate variante ale scenariului anterior, se şi spune că monografiile din domeniu sunt un fel de „cărţi de bucate”, culegeri de reţete, liste de ingrediente şi sugestii de îmbunătăţire a algoritmilor: în afară de recombinare, tot ca în evoluţie, se foloseşte şi operaţia de mutaţie locală, trecerea de la o generaţie la alta se poate face în multe feluri, populaţia de „cromozomi” se poate distribui, lucrând local, cu o comunicare de un tip sau altul între regiuni, criteriile de oprire se pot şi ele modifica şi multe altele. Sunt puse la lucru forţa brută a calculatorului, plus metafora evolutivă - cu rezultate, subliniez, neaşteptat de bune: soluţii neintuitive, greu de imaginat altfel, convergenţă rapidă la început, adesea evitând maximele locale. Iar singura „explicaţie” este cea „bio-mistică”: algoritmii genetici funcţionează atât de bine în atât de multe situaţii pentru că milenii de-a rândul natura a perfecţionat procese atât de performante în evoluţia speciilor.

Toate acestea induc, la acelaşi nivel speculativ, o concluzie optimistă: dacă algoritmii genetici sunt atât de utili, în ciuda lipsei unui argument matematic pentru aceasta, atunci să încercăm să imităm biologia şi în alte aspecte ale ei, având bune şanse ca, dacă suntem inspiraţi să extragem ideile potrivite, să obţinem sugestii fertile pentru îmbunătăţirea folosirii calculatoarelor existente şi, eventual, pentru realizarea unora şi mai performante. Acest optimism trebuie însă temperat de observaţia că un rezultat celebru al calculului evolutiv, al domeniului algoritmilor aproximativi în general, este aşa-numita no free lunch theorem (teorema „nu există prânz gratuit”), a lui David Wolpert şi William Macready(1997), care, informal, spune că oricare două metode aproximative de optimizare sunt la fel de bune, în medie, peste toate problemele de optimizare, ceea ce poate fi citit şi „la fel de puţin bune”, pentru fiecare metodă există probleme pentru care metoda nu poate da soluţii satisfăcătoare.

O coincidenţă

Înainte de a trece la calculul cu ADN, o precizare autobiografică. Eram la Graz, în Austria, în aprilie 1994, la o conferinţă, atunci când am intrat în posesia lucrării lui Tom Head, de la State University of New York din Binghamton, S.U.A.[7], ulterior prieten şi colaborator. A fost o revelaţie. Mă găseam după aproape douăzeci de ani de lucru în teoria limbajelor formale şi intuiam acum un domeniu extrem de promiţător de aplicaţii. E adevărat, ar fi trebuit să am această revelaţie mai demult, pentru că parcursesem la vremea ei lucrarea acad. Solomon Marcus „Linguistic structures and generative devices in molecular genetics”[8], dar probabil nu venise pe atunci vremea trecerii la bioinformatică, nu parcursesem cei douăzeci de ani de pregătire - pe care-i voi descrie pe scurt într-o secţiune ulterioară. Tom Head introduce în lucrarea sa o operaţie cu şiruri care formalizează operaţia de recombinare a moleculelor de A.D.N. din genetică. O numeşte splicing şi aşa îi voi spune în continuare, pentru a o distinge de recombinarea de la algoritmii genetici, cu care seamănă, fără a fi identică. Am imaginat chiar atunci, în vremea conferinţei, un fel de gramatică bazată pe această operaţie, de fapt, pe o variantă mai simplă şi mai apropiată de operaţiile cu şiruri decât operaţia lui Tom Head. Lucrarea a fost publicată în revista „Discrete Applied Mathematics” şi a consacrat versiunea de splicing pe care o propusesem. Peste puţine săptămâni, eram la Leiden, în Olanda, unde am scris o lucrare împreună cu Grzegorz Rozenberg şi Arto Salomaa, cel de-al doilea, de la Turku, Finlanda, locul unde aveam să petrec apoi mai mulţi ani, dedicaţi iniţial calculului cu A.D.N. şi apoi calculului membranar. Inspirat ca totdeauna, G. Rozenberg a titrat lucrarea noastră „Computing by splicing”. Pentru că, începând de atunci, am numit „sisteme H” mecanismele de calcul bazate pe splicing, amintind astfel de cel care a introdus (inventat sau descoperit?...) operaţia cu pricina, i-am trimis lucrarea, în manuscris, lui Tom Head. Acesta a răspuns imediat, prin telefon, întrebându-ne excitat: ştiaţi că tocmai s-a efectuat un experiment reuşit de calcul cu A.D.N.?! Nu, nu ştiam, a fost o coincidenţă - pe care o trec la coincidenţe semnificative.

Primul calcul în eprubetă

Tom Head se referea la experimentul lui Leonard Adleman, publicat chiar în toamna lui 1994 „Molecular computation of solutions to combinatorial problems”[9]. Despre posibilitatea de a folosi molecule de A.D.N. pentru a calcula s-a speculat încă din anii 1970 (Ch. Bennett, M. Conrad, chiar şi R. Feynman, cu mult citata sa frază „există foarte mult loc acolo, jos”, cu referire la fizică, dar extinsă afirmaţia şi la biologie). Adleman a confirmat această aşteptare, rezolvând în laborator problema dacă există un drum hamiltonian într-un graf (am amintit-o într-o secţiune anterioară). Problema este cunoscută ca fiind NP-completă, deci, printre cele mai grele probleme nefezabile, de complexitate exponenţială (plecăm de la premisa că nu avem P = NP), dar Adleman o rezolvă într-un număr de paşi care este liniar în raport cu mărimea grafului. E adevărat, paşi biochimici, făcând uz de un paralelism masiv, ba chiar şi de nedeterminism, toate acestea posibile datorită caracteristicilor moleculelor de A.D.N. şi biochimiei aferente. Pe scurt, milioane de cópii ale unor secvenţe simple de nucleotide, codificând nodurile şi arcele grafului, au fost puse împreună în soluţie apoasă. Prin scăderea temperaturii, aceste secvenţe au format molecule dublu catenare, corespunzătoare drumurilor în graf. Pentru că au fost folosite suficient de multe cópii ale secvenţelor iniţiale, cu mare probabilitate, au fost obţinute toate drumurile din graf. Dintre acestea, au fost selectate cele care treceau prin toate nodurile, prin proceduri obişnuite de laborator: electroforeză pe gel pentru a separa moleculele de lungime potrivită lungimii drumurilor, apoi selectare prin denaturare şi amplificare prin P.C.R. a drumurilor care treceau prin toate nodurile (deci, hamiltoniene).

Procedura presupune un număr de operaţiuni biochimice liniar în raport cu numărul nodurilor grafului. Problema este NP-completă, deci realizarea este extraordinară - iar ecoul a fost pe potrivă. Deja în anul următor, 1995, s-a organizat la Princeton o întâlnire cu titlul „DNA Computing”, care s-a transformat în conferinţă şi continuă şi astăzi. Da, dar...

Argumente pro şi contra

A fost un pas istoric, demonstraţia că se poate. Pe un graf cu 7 noduri, însă, pentru care problema se poate rezolva printr-o simplă inspecţie vizuală. Iar la începutul anilor ’90, calculatoarele obişnuite puteau deja rezolva problema existenţei dumurilor hamiltoniene în grafuri cu câteva sute de noduri, suficient pentru aplicaţiile practice curente (între timp, au progresat mult). Iar soluţia a fost obţinută printr-o tranzacţie spaţiu-timp, numărul de molecule a fost exponenţial de mare în raport cu numărul nodurilor. Juris Hartmanis, un clasic al informaticii, după ce şi-a exprimat entuziasmul (Hartmanis compară informatica cu fizica: a doua progresează în urma experimentelor cruciale, prima în urma demonstraţiilor că ceva se poate; Adleman a produs o asemenea demonstraţie!), a calculat cantitatea de A.D.N. necesar pentru a aplica procedura lui Adleman la un graf cu 200 de noduri şi a găsit că greutatea acestuia ar fi depăşit greutatea Pământului... Cam aici este şi acum calculul cu A.D.N. din punct de vedere practic. Numeroase experimente, dar tot pe „toy problems”, multă teorie, priceperea în manevrarea moleculelor de A.D.N. în laborator a progresat foarte mult, s-au obţinut şi rezultate de interes pentru tehnologia generală de laborator (de pildă, o versiune îmbunătăţită a reacţiei de polimerizare în lanţ, P.C.R.; unul dintre inventatori este matematician, Vincenzo Manca, amintit încă de la primele pagini ale acestui text), dar pe total domeniul s-a deplasat spre nanotehnologie, aplicaţiile practice nu au apărut încă (dacă nu cumva există aplicaţii în criptografie, dar sunt clasificate). Şi totuşi, lista posibilelor avantaje ale folosirii A.D.N.-ului pentru a calcula este lungă: o foarte bună eficienţă ca suport de date, la nivelul unui bit pe o nucleotidă; eficienţă energetică; comportare paralelă şi nedeterministă, două visuri ale informaticii (cu menţiunea că nedeterminismul aduce şi probleme, de exemplu, posibile false soluţii); manevrabilitate deosebită în laborator, stabilitate, reversibilitatea unor procese.

Minunata dublă elice

Molecula de A.D.N. are caracteristici surprinzătoare la nivel informaţional şi computaţional. Să ne reamintim, formulat în termeni „sintactici”: avem două şiruri de litere A, C, G, T, cele patru nucleotide, aşezate faţă în faţă, în perechi complementare Watson-Crick, totdeauna A făcând pereche cu T şi C cu G. Cele două şiruri sunt orientate diferit unul faţă de celălalt, orientarea fiind indicată de biochimişti prin notarea unui capăt de şir cu 3’ şi a celuilalt cu 5’. Iar aici apare deja o surpriză matematico-informatică, semnalată de G. Rozenberg şi A. Salomaa în Raportul Tehnic 96-28 al Universităţii din Leiden, Olanda (octombrie 1996), „Watson-Crick complementarity, universal computations, and genetic engineering”: structura moleculei de ADN „ascunde”, codificată, puterea de calcul a maşinii Turing! Formularea este imprecisă, ea corespunde însă următoarei observaţii. Încă din 1980 s-a demonstrat (J. Engelfriet şi G. Rozenberg) că orice limbaj ale cărui şiruri pot fi recunoscute de o maşină Turing, poate fi scris ca imaginea unui anume limbaj fixat, să-l notăm cu TS(0,1), printr-un traducător secvenţial.

Limbajul anterior este aşa-numitul „twin-shuffle” peste 0, 1 (de aici notaţia folosită): „shuffle” nu este altceva decât operaţia de amestecare a literelor a două cuvinte, fără a le schimba ordinea (exact ca la amestecarea cărţilor de joc din două pachete de culori diferite). Aici, amestecăm literele a două cuvinte „gemene”, un şir de simboluri 0 şi 1 şi unul identic modulo schimbarea „culorii” acestor simboluri (le putem adăuga o bară deasupra sau semnul „prim” pentru a obţine „şirul geamăn”). La rândul său, un traducător secvenţial este cel mai simplu traducător, care are o memorie finită şi parcurge un şir de la stânga la dreapta. De remarcat că lucrăm cu patru simboluri, 0, 1 şi perechile lor, să zicem, 0’ şi 1’. Exact atâtea nucleotide avem, patru. Să mai remarcăm şi că TS(0,1) este un limbaj fixat. Dându-se un limbaj oarecare, oricare ar fi el (recunoscut de o maşină Turing dată), el se obţine plecând de la acelaşi unic TS(0,1), doar traducătorul depinde de limbaj.

Surpriza interesantă şi semnificativă este că limbajul TS(0,1) se poate obţine prin „citirea” moleculelor de ADN, în felul următor: mergem de-a lungul celor două şiruri complementare Watson-Crick, de la stânga la dreapta, avansând la întâmplare pe cele două şiruri şi asociind celor patru nucleotide A, C, G, T simboluri 0, 1, după regula: A = 0, G = 1, T = 0’, C = 1’. Ceea ce obţinem, punând la un loc toate aceste citiri, pentru toate moleculele posibile de ADN, este exact TS(0,1)! Prin urmare, orice limbaj care poate fi definit de o maşină Turing poate fi obţinut traducând aceste citiri ale moleculelor de ADN cu ajutorul celui mai simplu traducător, cel cu memorie finită. Traducătorul depinde de limbaj, el „extrage” din TS(0,1) rezultatul calculelor unei maşini Turing. Puterea este acolo, rămâne numai s-o punem în evidenţă. (Într-un anume sens, avem din nou cuplarea dintre un proces simplu, „citirea” moleculei de ADN, şi un observator de ordinul întâi, simplu, traducătorul secvenţial, ca în lucrările aminite mai devreme ale lui M. Cavaliere şi P. Leupold, cu rezultatul egalând nivelul maxim de calculabilitate, cel al maşinii Turing.) Apar în acest context două chestiuni. Vorbeam, de exemplu, despre orientarea diferită a celor două catene ale moleculei de ADN, dar mai devreme le parcurgeam pe amândouă de la stânga la dreapta. Nicio problemă, citirea şirurilor duble poate să pornească din direcţii diferite şi rezultatul este acelaşi. Doi: natura este redundantă, sunt toate cele patru nucleotide (cele patru simboluri 0, 1, 0’, 1’) necesare pentru a acoperi, în sensul anterior, puterea de calcul a maşinii Turing? Nu, trei simboluri sunt suficiente - dar nu două [10]! 

Vorbind despre calcule şi redundanţă, să ne amintim că o mare parte din ADN este „rezidual”, nu codifică gene şi nu ştim exact la ce foloseşte. Putem specula: dacă în celulă, la nivel genetic, se efectuează calcule (viruşii sunt şiruri de nucleotide, prin urmare şi recunoaşterea lor este o operaţie de analiză sintactică, deci un calcul), iar aceste calcule este de presupus că sunt complexe, de ce nu?, chiar la nivelul maşinii Turing, atunci avem nevoie de „spaţiu de lucru”, de o „bandă” care în final rămâne în mare parte goală, rezultatul este aşezat la începutul ei (în cazul benzii maşinii Turing). ADN-ul aparent fără funcţie poate fi tocmai spaţiul de lucru pentru calcule complexe, pe care nu le înţelegem încă.

- Va urma -

------------------------------------------------------
[1] B.J. Copeland, D. Proudfoot, „Alan Turing's forgotten ideas in computer science”, Scientific American, aprilie 1999, pp. 77-81.
[2] C. Teuscher, Life and Legacy of a Great Thinker, ed., Alan Turing, Springer-Verlag, 2003,
[3]E. Sánchez, A revival of Turing’s forgotten connectionist ideas: exploring unorganized machines, din Proc. Connectionist Models of Learning, Development and Evolution, Liège, Belgium, 2000 (R.M. French, J.J. Sougne, eds.), Springer-Verlag, 2001, pp. 153-162.
[5] Detalii pot fi găsite în A.E. Eiben, J.E. Smith, Introduction to Evolutionary Computing, Springer-Verlag, 2003.
[6] („A structure for deoxyribose nucleic acid”, vol. 171, aprilie 25, pp. 737-738).
[7] „Formal language theory and D.N.A.: An analysis of the generative capacity of specific recombinant behaviors”, apărută în Bulletin of Mathematical Biology, vol. 49, 1987, pp. 737-759.
[8] Solomon Marcus „Linguistic structures and generative devices in molecular genetics”, Cahiers de Linguistique Thèorique et Appliquée, vol. 11, 1974, pp. 77-104.
[9] Revista Science, nr. 226, nov. 1994, pp. 1021-1024
[10] Demonstraţii pentru toate aceste rezultate pot fi găsite în monografia (tradusă în japoneză, chineză şi rusă) Gh. Păun, G. Rozenberg, A. Salomaa, DNA Computing. New Computing Paradigms, Springer-Verlag, 1998.
footer