Jak se DNA naučila počítat

PAVEL HOUSER  |  Věda
paralelizace

Deoxyribonukleová kyselina je molekulární paměť disponující úžasnou kapacitou. Lze ji ale použít také přímo pro provádění výpočtů, a to jak v živých organismech, tak v počítačích.

NP ÚPLNÉ PROBLÉMY

Představte si, že máte přečíst nějaký seznam. Nyní dostanete druhé zadání, dvakrát delší seznam. Jak se změní čas potřebný k řešení úlohy? Vzroste také dvojnásobně, jak jinak. Tomu, jak se změnou velikosti vstupu změní doba potřebná k řešení, se říká „výpočetní složitost“. U některých úloh roste doba řešení

v závislosti na vstupu velmi rychle. Významnou kategorii představují z hlediska výpočetní složitosti tzv. NP úplné úlohy, které je zjednodušeně řečeno velmi obtížné vyřešit, ale když už nějaké řešení máme, lze poměrně snadno ověřit, zda je správné. To je právě to, co se nám pro DNA počítače hodí. Mimochodem povaha NP úplných problémů patří k sedmi největším úlohám současné matematiky a za řešení je vypsána

odměna milion dolarů. Matematik Keith Devlin v knize Problémy pro třetí tisíciletí přitom tvrdí, že tento problém by podle něj mohl (jako jediný ze sedmi „nej“) vyřešit i amatér s dobrým nápadem.

PARALELIZACE

Je-li cílem přečíst dlouhý seznam, můžeme úlohu jednoduše rozdělit na dvě menší: prostě seznam rozpůlíme a dáme ho studovat dvěma lidem. Teď si ale představte, že úkolem je třeba odmocnit nějaké hodně velké číslo. Pomůže nám nyní, že úlohu mohou řešit dva lidé? A pokud ano, jak jim práci vůbec „rozdělit“? V informatice se tomuto procesu říká paralelizace – využíváme při něm třeba systém s více procesory, nějaký cluster více počítačů nebo třeba různé počítače komunikující spolu prostřednictvím internetu (například známý projekt hledání mimozemských civilizací SETI@home). DNA počítače nabízejí opravdu masivní paralelismus, kdy vedle sebe můžeme nechat probíhat řadu reakcí. Úlohu je ale nutné do této podoby nějak převést – třeba obrovská čísla nemůžeme reprezentovat řetězci DNA o daném počtu nukleotidů, protože bychom se s nimi vůbec nemuseli vejít do známého vesmíru. J

Jak vlastně DNA „počítá“? Živé organismy využívají mj. unikátní schopnost DNA se replikovat – to znamená, že se ke každému vláknu DNA samovolně vytváří jeho komplementární, „zrcadlový“ otisk. Dvě takto komplementární vlákna pak drží pohromadě ve známé dvojšroubovici (pomocí vodíkových vazeb mezi dusíkatými bázemi – adenin drží proti thyminu a guanin proti cytosinu), mohou se ale i rozplést a kopírovat dále. Toto splétání a rozplétání vláken DNA pak reprezentuje výpočty i v rámci DNA počítače. DNA vlákna navíc můžeme různě střihat či na sebe navazovat pomocí enzymů. Je to tedy obdoba mechanického počítače na principu kuličkového počitadla, ovšem systém rychlý, miniaturní a disponující masivním paralelismem; to znamená, že vedle sebe může ve zkumavce probíhat v jednom okamžiku obrovské množství reakcí. Nakonec dostaneme směs různých řetězců, z nichž správné řešení nějak „oddělíme“ (třeba je nejlehčí, obsahuje nějakou magnetickou značku apod.) a přečteme.

Obchodní cestující

Představte si, že jste obchodní cestující, který musí projet x městy. Začne v bodě A a končí v bodě X, pořadí mezi tím může být libovolné, ovšem podmínkou je navštívit všechna města, každé navštívit právě jednou a přitom urazit co nejkratší vzdálenost. To je jedna z podob úlohy zvané Problém obchodního cestujícího. Jak bude vypadat řešení na DNA počítači?

Připravíme si sadu nukleových kyselin (molekul, sekvencí nukleotidů ve stylu ATTAGCCTAAGGC), které budou odpovídat jednotlivým městům.

Jiné sekvence budou reprezentovat cesty mezi uzly. Cesta mezi bodem A a B bude mít na začátku báze komplementární s koncem sekvence města A, na svém konci báze komplementární se začátkem řetězce reprezentujícího bod B. Délka úseku mezi komplementárními částmi cesty pak bude odpovídat vzdálenosti mezi body. Bude to taková stavebnice z příček.

Výpočet ve zkumavce

Ve zkumavce pak smícháme všechny předpřipravené sekvence nukleové kyseliny. V okamžiku proběhne obrovské množství reakcí, jednotlivé řetězce se k sobě budou přibližovat, dotýkat se a zase vzdalovat. Tam, kde se ale k sobě přiblíží komplementární řetězce, vytvoří se mezi párovými bázemi potřebné vazby a obě části již zůstanou pohromadě. Nyní ve zkumavce máme směs všech možností. Pomocí dodatečných reakcí vybereme takové molekuly, které vyhovují podmínkám zadání. Tenhle postup je poměrně pracný; můžeme třeba molekuly začínající v bodě A (tj. takové, jež mají na začátku „volnou“ část odpovídající bodu A) navázat na zvláštní komplementární řetězec obsahující atom železa a ze směsi tuhle část vylovit magnetem. Jinou variantou je použití specifických enzymů, které naopak rozštípou molekuly, jež jsou s podmínkami zadání v rozporu.Všechny tyhle operace budeme muset provést několikrát – následně najdeme molekuly obsahující právě jednou bod B atd.

Směs výsledků

Tím získáme směs molekul, která přesně vyhovuje zadaným podmínkám. Tyto molekuly se však liší cestami mezi body. Námi hledaná cesta je právě ta nejkratší, a protože délka „nekomplementárních“ částí cest odpovídá délce skutečné, musíme získat nejkratší molekulu. Taková molekula by např. měla být také nejlehčí, jednotlivé řetězce nukleové kyseliny se podle své velikosti liší i v dalších fyzikálních vlastnostech (bod tání, chování v gravitačním poli nebo v elektromagnetickém poli). Směs tedy opět nějak rozdělíme a „přečteme“ správné řešení. Protože přesnosti DNA přece jen tak docela nedůvěřujeme, přečteme raději molekul více a zjistíme, zda jsou shodné. Pokud ne, ověříme již klasickou cestou, jaké řešení je správné.

Hmotnostní bariéra

Na přelomu tisíciletí se výzkum rozštěpil na několik projektů; někteří z vědců se spokojili s jednoúčelovými zařízeními řešícími NP úplné problémy (jako byl ten Adlemanův – algoritmus byl určen pro jediný typ úlohy), jiní se snažili sestavit DNA počítač v podobě konečného automatu, cílem dalších byl obecný Turingův stroj. Badatelkou, která se v této oblasti výrazně angažovala, byla Laura F. Landweberová, v současnosti působící na Princetonu. Na rozdíl od Adlemana to byla původní profesí bioložka. Komunita vědců zkoumajících DNA počítače je dnes plná jak informatiků, tak molekulárních biologů. Objevily se ale i překážky. Ukázalo se, že samotná technologie sice některé problémy klasických počítačů svým masivním paralelismem překonává, ale na jiné sama naráží. Velkou překážkou se ukázala být „hmotnostní bariéra“.

U řešení složitějších problémů se narazilo na obtíže se syntézou dostatečně dlouhých řetězců DNA, které by mohly reprezentovat zadání úlohy; tento postup byl časově náročný, drahý i relativně chybový. U dlouhých řetězců narůstá chybovost i během výpočtu – párují se totiž i tehdy, když si neodpovídají úplně přesně. Složitější problémy pak také vedly k tomu, že namísto zkumavek v původních Adlemanových pokusech by bylo třeba reakci provádět v objemných reakčních nádobách; právě zde by hrozilo, že kombinatorická exploze u klasických počítačů bude vystřídána explozí hmotnostní. Samozřejmě se může stát, že při určitém zadání a uspořádání pokusu převýší hmotnost směsi potřebné k řešení hmotnost známého vesmíru, nemusí však vůbec dojít k tak extrémním případům. Úplně stačí, když bude směs tak objemná, že nebude možné rozumně zajistit dokonalé promíchání – předpoklad masivního paralelismu. A nakonec, i když se promíchání zajistit podaří, budeme mít před sebou třeba přílišný objem, abychom z něj dokázali s rozumnou úspěšností oddělit molekulu kódující řešení (na rozdíl od klasického programu, který oznámí výsledek, u DNA počítače pouze víme, že řešení „někde je“).

Hmotnostní bariéra je problém závažný, ale nemusí být neřešitelný. Při stávajícím vývoji DNA počítačů se ale ukázalo, že chyběla pobídka z komerční sféry. Prostě se nenašel nikdo, kdo by výzkumníkům zadal řešení problému, na který současné klasické počítače nestačí, a nabídl jim za to potřebnou finanční odměnu. Jak vlastní DNA počítače, tak i operace s nimi jsou přitom ve větším měřítku zatím docela drahé.

Cesta k životu

Vývoj DNA počítačů se proto před několika lety začal ubírat jinými směry. Jedním bylo jejich využití k sestavování různých prostorových struktur, z DNA, „skládaček“, nanorobotických systémů nebo drátků, v nichž vnitřek dvojšroubovice DNA fungoval jako vodivý kanál. Ukázalo se, že DNA lze takto propojit s klasickou elektronikou a využít ji k sestavování objektů (navázaných na základ DNA) do přesně daného prostorového uspořádání. Kromě přirozené DNA můžeme také použít její analogy třeba s nějak modifikovanými dusíkatými bázemi, čímž získáme další možnosti, třeba uspořádání v podobě trojšroubovic. Spíše než o výpočty jde v tomto případě o molekulární stavitelství. DNA počítače míří také přímo do živých organismů. Izraelští vědci z Weizmannova institutu pod vedením profesora Ehuda Shapira začali již v roce 2004 sestavovat první DNA počítače určené k fungování v prostředí živých buněk. Po skončení běhu algoritmu měl systém v závislosti na jeho výsledku provést určitou biochemickou reakci (např. syntéza určité látky nebo její uvolnění) odpovídající výstupu. Tyto „počítače“ mohou fungovat například jako „chytré léky“ proti rakovině. DNA počítač dokáže odhalit sníženou nebo zvýšenou aktivitu určitého genu a terapie pak spočívá ve spuštění syntézy biologicky aktivní molekuly, která ničí nádorové buňky. Onemocnění je v Shapirově systému diagnostikováno v případě, že současně dva geny vykazují sníženou a dva geny zvýšenou aktivitu.

V praxi proces funguje tak, že uvolňovaná látka je původně deaktivována na řetězci DNA počítače. Splnění jedné z podmínek znamená vždy zkrácení řetězce o odpovídající část, při splnění všech podmínek se aktivuje celá účinná sekvence DNA. Podle ní se posléze syntetizuje protein, který zahubí nádorové buňky. DNA počítač tohoto druhu není ani tak výpočetní zařízení, ale funguje v živém organismu spíše jako řídicí systém; na základě toho, co zjistí, něco sám udělá. Co bude dál? To samozřejmě nikdo neví, ale možná se vrátí i časy DNA počítání. Čeká se na killer aplikaci. V současné kryptografii hraje velkou roli tzv. faktorizace, což je rozklad obrovského čísla na součin dvou prvočísel. Bezpečnost stávajících šifrovacích metod stojí a padá s tím, že tato operace je krajně asymetrická -vynásobit čísla nebo ověřit výsledek je mnohem snazší než provést rozklad obřího čísla na dvě prvočísla. Kdyby se ale něco takového efektivně podařilo na DNA počítači… Můžeme si zkoušet představit, jak takový výpočet uspořádat.

GENETICKÉ PROGRAMOVÁNÍ

Zajímavým průnikem světa genetiky a informatiky je genetické programování a řada příbuzných disciplín. Genetické programování znamená, že než abychom pracně vyvíjeli a dolaďovali program řešící daný problém, necháme program vyvíjet se samostatně. Naše programy necháváme různě náhodně měnit (obdoba mutace), vybíráme mezi nimi ty, které řeší danou úlohu nejlépe (obdoba selekce) a programy mezi sebou také můžeme kombinovat („křížit“ – obdoba sexuálního rozmnožování).

RUKOVĚŤ DNA PROGRAMÁTORA

rukověď DNA

Martyn Amos, člověk, který jako první na světě získal doktorát z DNA počítačů (na MIT), shrnuje svou vědeckou práci v knize Na úsvitu živých strojů. Popisuje zde podrobně vývoj oboru od prvních pokusů Leonarda Adlemana až po současný stav, kdy se za nejperspektivnější pokládá nasazení DNA počítačů nikoli pro klasické výpočty, ale pro řízení procesů probíhajících v živých organismech. Český překlad této knihy vydalo letos nakladatelství Mladá fronta.

Komunita vědců zkoumajících DNA počítače je dnes plná informatiků i molekulárních biologů.Samozřejmě se může stát, že při určitém zadání a uspořádání pokusu převýší hmotnost směsi potřebné k řešení hmotnost známého vesmíru.

Nejčtenější