DNA počítače: technologie nespí

Na stránkách Zdrojáku se věnujeme především záležitostem bezprostředně spojeným s vývojem webu a webových aplikací. Pojďme se dnes vydat za hranice webu a současných počítačů a představme si technologii, kterou nepohání čipy a tranzistory – DNA počítače. Zůstanou jen hříčkou, nebo jejich masivní paralelismus pomůže řešit velmi složité úlohy?

DNA počítače stíhá v současnosti osud celé řady technologií. Na začátku zaujmou svou exotičností a mnohými přísliby. Jak jde čas, začnou se do cesty kupit překážky, vše se komplikuje a uvedení do praxe odsouvá. Potom je technologie zatracena, ovšem v tichosti – média se prostě začnou věnovat něčemu jinému, co je zrovna více sexy. Jenže, pokud má naše technologie opravdu štěstí, vývoj zatím pokračuje; obvykle opět v tichosti a namísto nějaké univerzální vize se už zkoumá konkrétní podobor. A s ještě trochou štěstí se pak dočkáme i skutečného nasazení.

DNA počítačích se začalo mluvit někdy ve druhé polovině 90. let, a zhruba v polovině prvního desetiletí tohoto století to média zase přestalo zajímat. V češtině jsme se na toto téma dočkali kromě časopiseckých článků dokonce i jedné tištěné knihy – Martyn Amos: Na úsvitu živých strojů, Mladá fronta 2008. Poněkud matoucí název měl zřejmě přispět k lepší prodejnosti, zda to ale pomohlo, to není jasné. Téma je to přece jen hodně specializované.

A nakonec ještě jedno přímé setkání s DNA počítači mohli našinci zažít. V roce 2002 se totiž jeden exemplář předváděl v CeBITu. V té době byl CeBIT ještě stále velmi významnou událostí světa IT, takže do Hannoveru jezdilo i hodně počítačovců z ČR.

Počátky oboru

prof. Len Adleman

prof. Len Adleman

Zájem o celou technologii odstartoval v polovině 90. let Leonard Adleman (ano, to je ten pán, jehož první písmeno příjmení je obsaženo v názvu zkratky šifry RSA). Napadlo ho, že pokud se dvě vlákna DNA proti sobě párují tak, že vždy jedna dusíkatá báze (část chemické struktury DNA, z hlediska vlastního informatického principu nejsou chemické detaily přirozeně podstatné) stojí proti jediné jiné – tyto dvě báze označujeme jako komplementární – mohlo by tohle rozplétání a splétání molekul reprezentovat výpočty. Příslušné páry bází spolu tvoří adenin (A) s thyminem (T) a guanin (G) s cytosinem ©. K řetězci AATGAGCT je tedy komplementární „otisk“ TTACTCGA. Adleman nekopíroval živou přírodu, ale jeho idea byla invenční: v biologických systémech totiž DNA funguje jako paměťové médium, ne jako aktivní výpočetní prvek.

Základní Adlemanovou představou bylo, že systém molekul DNA by při výpočtu vykazoval velmi masivní paralelismus. Využít by to šlo hlavně u úloh, jejichž řešení probíhá pomocí prohledávání stavového prostoru, kdy jednotlivé molekuly DNA budou odpovídat různým bodům v tomto prostoru. V zásadě stačí problém vhodně zakódovat, tj. vymyslet, jaké procesy s DNA budou odpovídat výpočtu. V pouhé zkumavce je molekul tolik, že prohledání i obrovského stavového prostoru bude hračkou. Pak už půjde jen o to hledané řešení ze směsi oddělit – ve stavovém prostoru se obvykle zajímáme o řešení nějak speciální, dejme tomu minima. Odpovídat jim bude nejkratší molekula DNA, a ta třeba nejrychleji vyplave na hladinu. Pak ji přečteme a řešení převedeme opět do jazyka původního problému. V průběhu pokusu můžeme také k řetězcům lepit DNA nějak upravenou, třeba tak, aby světélkovala, byla magnetická či radioaktivní, a tyto kousky pak použijeme pro detekci řešení. „Přívěsky“ samozřejmě nesmějí narušit funkčnost vlastního splétání a rozplétání.

Řešení úloh

Adleman celý postup demonstroval na řešení úlohy obchodního cestujícího. Problém spadá do kategorie tzv. NP úplných úloh. U těchto problémů není známo, jak je řešit v polynomiálně rostoucím čase (a pravděpodobně to ani nelze), naopak správnost určitého řešení lze ale mnohem jednodušeji ověřit. Povaha NP úplných úloh je dokonce jednou ze šesti největších nerozhodnutých problémů současné matematiky (bylo jich 7, ale Poincarého domněnka už byla mezitím dokázána). Co se týče 7 největších matematických výzev, jak je seřadil Clayův ústav, doporučit lze knihu Keith Devlin: Problémy pro třetí tisíciletí (Argo a Dokořán, 2005).

Pro naše potřeby stačí si NP úplné problémy představit, jako by vykazovaly exponenciálně rostoucí složitost – s délkou vstupu tedy nakonec čas potřebný k výpočtu poroste velmi rychle nad všechny meze.

Adleman si ve zkumavce pohrál se dvěma variantami úlohy. V první z nich je třeba najít řešení problému obchodního cestujícího tam, kde spolu nejsou propojena všechna města, druhá úloha obsahuje veškeré spojnice a hledá se nejkratší cesta. Každé z měst je třeba navštívit pouze jednou.

Úlohu budeme řešit hrubou silou, to znamená, že musíme najít všechny povolené trasy a ty pak seřadit podle vzdálenosti. Leonard Adleman a Laura Landweberová sestavili následující model problému: Nejprve si připravíme sadu molekul nukleových kyselin, které odpovídají jednotlivým městům. Jiné sekvence pak reprezentovaly cesty mezi uzly.

Např. 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í částmi cesty bude odpovídat vzdálenosti mezi body.

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ě přibližují, dotýkají se a zase se vzdalují. Tam, kde se ale k sobě dostanou komplementární řetězce, vzniknou mezi párovými bázemi příslušné vazby a obě části již zůstanou pohromadě.

Stav řešení je teď následující: Máme před sebou směs všech možností-řešení. Reagující látky jsme přidali ve velkém přebytku a jednotlivé kombinace jsou zde zastoupeny ve větším počtu. Prostě se poléháme na to, že je statisticky víceméně vyloučeno, aby nějaký způsob poskládání řetězců zcela scházel.

Nyní nám zbývá najít správné řešení, tj. nějak od sebe jednotlivá vlákna a dvojvlákna oddělit dle jejich vlastností. Hypoteticky můžeme postupovat třeba následujícím způsobem:

– Ke směsi přidáme určitou látku, „činidlo 1”, které obsahuje sekvenci nukleotidů komplementárních k začátku molekuly A a má na sobě navázaný atom železa. Všechny cesty, vyhovující našemu řešení, začínají v bodě A. Vyhovující řetězce musí mít tedy začátek bodu A prázdný, bez nalepeného komplementárního řetězce „předcházející cesty”. Na toto místo se právě „přilepí” činidlo 1.

– Všechny vyhovující molekuly jsou tedy nyní označené železem. Směs vystavíme účinkům magnetického pole a látky rozdělíme na magnetické a nemagnetické.

A tak dále – pro základní představu to snad stačí. Vždy prostě ke směsi molekul DNA přidáme nějaký „operátor“, směs rozdělíme, pak od té části, co nás zajímá, činidlo oddělíme, a se zbytkem pracujeme dál podobně.

Technické podrobnosti o řešení různých typů úlohy obchodního cestujícího na DNA počítačích  naleznete např. v článku na ScienceWorldu.

Analogickými metodami získáme nakonec směs molekul, která přesně vyhovuje zadaným podmínkám. Každá z těchto molekul obsahuje sekvence kódující všechny body, a to právě jednou. Molekuly se však liší pořadím cest mezi body. Námi hledaná cesta je právě ta nejkratší a protože délka „nekomplementár­ních” částí cest odpovídá délce skutečné, musíme získat nejkratší molekulu (viz výše).

Nakonec slavnostně přečteme finální řetězec a zjistíme, jakou cestu vlastně kóduje. Samozřejmě nemusíme jako jehlu v kupce sena hledat jedinou molekulu, bude jich víc, reagující látky jsme přece přidávali ve velkém přebytku.

Komplikace

Tady už asi každého napadnou možné komplikace. DNA počítače pracují přece jen statisticky (konec konců, i při kopírování DNA v živých organismech dochází k chybám – mutacím). Je možné, že něco ve směsi „zreagovalo jinak“ a naše řešení je chybné. Proto po přečtení výsledku musíme samozřejmě ověřit, zda řešení vyhovuje podmínkám úlohy. Potom je třeba ještě zkontrolovat několik dalších molekul ve „výsledku“, abychom zjistili, zda kódují stejné řešení, jako to, co jsme již dostali. Pokud máme směs molekul kódujících různá řešení, musíme mezi nimi rozhodnout. Obecně se tehdy zdálo, že DNA počítače se uplatní především tam, kde nám jde o nalezení alespoň nějakého řešení, eventuálně dopředu víme, že úloha má řešení pouze jediné.

Nicméně, nutné to není – jak jsme si již řekli ověření řešení NP úplného problému je řádově kratší. To už bychom samozřejmě provedli na klasickém počítači.

Později byl analogicky tímto způsobem vyřešen další NP úplný problém, tzv. úloha splnitelnosti (třeba – pořádáte večírek, X se chce sedět vedle Y, ale rozhodně ne vedle Z atd.). Vytvořena byla i celá řada hravých aplikací, třeba obdoba piškvorek. Situace se zdála nadějná, protože pro určité úlohy by molekuly DNA svým masivním paralelismem jasně překonávaly i současné superpočítače.

Efektivní řešení složitých NP úplných úloh by mohlo zamotat hlavu i kryptografům. Faktorizace (rozklad složeného čísla na prvočísla) sice pravděpodobně není NP úplným problémem, ale rozhodně není výpočetně složitější – takže když se zde na Rootu před několika lety spekulovalo právě o faktorizaci na DNA počítači, vlastně by namísto toho stačilo nejdřív faktorizační úlohu převést na problém splnitelnosti.

Stále ale zůstávala celá řada problémů. Předně, nikdy se nepodařilo sestavit skutečně univerzální DNA počítač. U každého problému bylo třeba vyřešit odpovídající kódování do DNA; úspěch vyžadoval spolupráci programátora a biochemika. Míra automatizace procesu byla různá. Adleman postupoval tak, že všechno skutečně míchal ručně ve zkumavkách, později se to provádělo pomocí předprogramovaných automatických manipulátorů nebo DNA rovnou reagovala v průtočných systémech, kde si obsluha jen hrála s kohoutky a různě v systému posouvala hejblátka jako na mechanickém počítacím stroji. I tohle ale šlo jen pro jeden typ úloh (obchodní cestující), u těch ostatních se bohužel nepodařilo vytvořit nějakou abstraktní vrstvu, oddělit tvorbu softwaru od znalosti hardwaru.

Paralelismus je hezká věc, ukázaly se však i problémy při práci s velkými čísly – což je normální stav, netypická byla naopak výše popsaná ukázka obchodního cestujícího s nějakými 7 městy a cestami, které reprezentovaly molekuly o řádově 20 „písmenkách“. Problém je už v tom připravit dostatečně dlouhé řetězce DNA, je to časově náročné, drahé a postup je navíc stále docela chybový. Dlouhé molekuly, poskládané spolu ve všech možných kombinacích, je obtížné promíchat, a bez toho masivní paralelismus prostě nefunguje. Směs může být také obtížné dělit, nebo celý postup musí být mnohostupňový, kdy se výstup jednoho pokusu použije jako vstup do dalšího. A do toho se zase přidává statistická povaha výpočtu, takže v každém kroku je třeba provádět ověření mezivýsledku. Popsané problémy se někdy shrnují pod název „hmotnostní bariéra“.

Přišla chvíle, kdy namísto laboratorních demonstračních ukázek by stálo za to začít vytvářet v praxi použitelná řešení. Nikdo ale kupodivu nezadal poptávku, možná proto, že DNA počítačům v té době (mluvíme cca o roku 2005) nikdo nevěřil. Mezitím došlo mj. ke krachu řady biotechnologických firem a slovo DNA přestalo na kasičky investorů působit jako magický klíč. Možné je ale i to, že řešit úlohy toho typu, pro něž by se DNA počítače zvlášť dobře hodily, vlastně v komerční sféře nikdo nepotřeboval, protože jakž takž stačily nějaké heuristiky.

Co s DNA počítači dál?

DNA počítače možná zažijí renesanci, až se zpřesní naše techniky manipulace DNA, zlevní čtení (sekvenování)a zpřesní se syntéza dlouhých molekul. Ani v opačném případě ale nebylo celé úsilí vyplýtváno nadarmo. Hned několik týmů totiž pracuje na DNA strojcích, které by sice trochu počítaly, ale hlavně měly něco dělat. Připomínají všemožné nanoroboty ze scifi.

A co že by DNA měla dělat? Především syntetizovat bílkoviny, tedy to, co dělá i v lidském organismu. Umělá DNA by v živém organismu používala jen několik jednoduchých přepínačů, jimiž by se různě modifikovala. Přepínače by fungovaly na základě sledování určitých signálů z prostředí, které třeba odpovídají vzniku nádorových buněk. Jakmile tento DNA strojek vyhodnotí, že se nachází v nádorové buňce, aktivuje syntézu proteinu, která buňku zahubí. Konkrétně to třeba může být tak, že řetězec je na počátku deaktivován, při splnění různých podmínek se tato ochrana ale postupně „ukusuje“.

Podrobnosti popisuje článek: DNA počítač odhalí nádorové buňky.

Druhou nadějnou cestou DNA počítačů jsou molekulární skládačky. Zde se DNA spolu podle zadání a přepínačů nesplétají do klasických dvojvláken, ale vytvářejí v nanoměřítku konkrétní struktury, různé plošné spoje nebo krychle. Krychle z DNA sama o sobě asi moc využití nemá, ale DNA zde slouží jako lešení, které k sobě dostane další navázané látky – dala by se přirovnat k jakýmsi molekulárním prstům, které vytvoří požadované prostorové uspořádání. Třeba se tímto způsobem bude někdy vyrábět i elektronika.

Tvar příslušných struktur i to, jak se budou měnit v závislosti na dalších okolnostech, samozřejmě naprogramujeme předem. Podobně jako v předcházejícím případě „léčivého nanostrojku“ je samotný algoritmus na abstraktní rovině obvykle triviální, ale výsledky mohou být působivé. Šancí pro obor je i to, že se třeba časem objeví více chytrých lidí, kteří se s těmito technologiemi setkali již během studia a rozumí jak informatice, tak i biochemii. Oba obory se tradičně učily zcela odděleně, což omezovalo množství lidí, kteří by se DNA počítači mohli zabývat na profesionální úrovni.

Věděli jste, že nám můžete zasílat zprávičky? (Jen pro přihlášené.)

Komentáře: 13

Přehled komentářů

Almad Díky
sKopheK Re: Díky
Vodpik NP x co-NP
ps Re: NP x co-NP
Vodpik Re: NP x co-NP
Czenek Re: NP x co-NP
freon Re: NP x co-NP
_r3450n_ Radioaktivni DNA?
Martin Malý Re: Radioaktivni DNA?
Vojta Re: Radioaktivni DNA?
_r3450n_ Re: Radioaktivni DNA?
Jan Slozitost
pavel houser Re: Slozitost
Zdroj: https://www.zdrojak.cz/?p=3241