Biochemické algoritmy: Výběr automobilů na DNA počítači

Jak jsme již informovali v CW 15/2002, další algoritmický problém se stal řešitelným prostřednictvím DNA počítače...


Jak jsme již informovali v CW 15/2002, další algoritmický problém se stal
řešitelným prostřednictvím DNA počítače. Leonard Adleman, muž, který stál u
zrodu prvních DNA počítačů v polovině 90. let, se po problému obchodního
cestujícího zaměřil úlohu spočívající ve výběru automobilů. Detaily použitého
algoritmu si Adleman zatím nechal pro sebe, nicméně rámcově je zvolený postup
následující.
Nejprve stručný popis problému: Zákazník si vybírá automobily podle celé řady
kritérií (barva, cena, velikost, značka...) a může formulovat dosti
komplikované podmínky ("červený nesmí být trabant, leda kdyby byl prostorný a
levnější než částka x"). Prodejce je navíc limitován tím, že ne všechny modely
v "mřížce" existují například jeden model je k dispozici pouze za jedinou cenu,
navíc na skladě nemusí být aktuálně ani barevná kombinace každé značky apod.
Při řešení problému nepracujeme se žádnými velkými čísly, ale musíme testovat
souběžně velkou řadu podmínek. DNA počítač se svým masivním paralelismem se nám
právě k tomuto účelu velice dobře hodí.
Pro konkrétní demonstraci algoritmu si představte jeho zjednodušenou verzi:
Každý automobil je charakterizován barvou, velikostí a značkou. Na skladě máme
všechny možnosti. Zákazník klade podmínky typu "červený trabant pouze velký".
Řešení bude probíhat následujícím způsobem: Připravíme si řetězce nukleotidů,
které charakterizují barvu, totéž uděláme pro velikost a značku. Přitom řetězec
"značka" bude vždy končit určitou sekvencí nukleotidů. Všechny řetězce "značka"
budou mít tuto sekvenci společnou, zbytek bude odlišný podle konkrétního typu.
Řetězce typu "barva" budou všechny začínat částí komplementární s koncem
"značky" a končit jiným společným řetězcem který samozřejmě bude komplementární
se začátkem řetězce "velikost".
Po smíchání nukleotidů v jediné zkumavce se komplementární báze spárují na
protilehlá vlákna, a tak dostaneme směs všech možností, tj. všechny řetězce
typu "značka-barva-velikost" (konkrétně např. trabant--konec značka-začátek
barva-červená-konec barva-začátek velikost-velký).
Podmínku "trabant pouze velký" pak řešíme následujícím způsobem: Ke směsi
přidáme nukleotidy komplementární s trabantem, ty se připojí k volnému místu
(řetězec "trabant" měl díky párování bází zakryté oba konce, ale zatím měl
volnou část vlákna uprostřed). Přidané nukleotidy komplementární s trabantem
jsme nějak označili, např. železem. Nyní odsajeme magnetem magnetické molekuly,
tj. vybrali jsme "trabant" toto je zcela obecný postup, kdy si pro označení
vybereme nějakou vlastnost, podle které pak budeme molekuly snadno dělit.
Podobným principem rozdělíme "velké" a "malé". Například ke směsi přidáme
řetězec komplementární s "malé", který bude označen nějakou velmi těžkou
molekulou. Poté rozdělíme směs podle hmotnosti/hustoty.
DNA počítače pracují pouze statisticky. Je možné, že v párování bází dojde k
chybě, výsledek proto budeme muset zkontrolovat, abychom zjistili, zda vyhovuje
zadaným podmínkám. Pokud odhalíme chybu, vezmeme z roztoku další molekulu v
řadě. Přebytek reagujících částí by měl teoreticky zajistit, aby nám žádná
molekula žádného typu "neuplavala" zcela.
Popsaný způsob je plně postačující, pokud hledáme "alespoň jedno řešení". V
opačném případě budeme muset brát molekulu po molekule, ale vlastně si nikdy
nebudeme úplně jistí, zda jsme nalezli řešení všechna.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.