Obliczenia w próbówce

10.12.2009 - Monika Demichowicz
TrudnośćTrudność

Algorytm naiwny ale skuteczny

Do znalezienia rozwiązania problemu Hamiltona, Adleman zaproponował naiwny (mało optymalny) i niedeterministyczny (tzn. zawierający w sobie pewną losowość) algorytm dla skierowanego grafu o n wierzchołkach. Oto on:

  1. Wygeneruj wszystkie możliwe ścieżki w grafie (czynnik niedeterministyczny)
  2. Odrzuć te, które nie zaczynają się w wierzchołku początkowym lub nie kończą w wierzchołku końcowym
  3. Odrzuć te ścieżki, których długość jest różna od n
  4. Wybierz te ścieżki, w których każdy z węzłów występuje co najmniej raz
  5. Jeśli pozostały jakieś ścieżki, stanowią one rozwiązanie, jeśli nie - rozwiązania nie udało się znaleźć

Poświęć chwilę na zastanowienie się, dlaczego algorytm ten działa prawidłowo. Nie jest on optymalny - bazuje na wygenerowaniu wszystkich ścieżek, a jest ich dużo bo n! dla n wierzchołkowego grafu. Sprawdzanie ich wszystkich jest  trudne, bo liczba ścieżek gwałtownie rośnie wraz z rozmiarem grafu. Algorytm ten ma jednak tę zaletę, że można go zrealizować na danych zakodowanych w DNA i dostępnych dla nich operacjach. A jak się okaże za chwilę, liczba potencjalnych ścieżek dla komputera w próbówce nie jest takim samym problemem jak dla zwykłego komputera.

Jeśli zrozumiałeś algorytm oraz zapoznałeś się z przedstawionymi operacjami na cząsteczkach DNA, możemy przystąpić do najważniejszej części - eksperymentu.

Mokra robota

Nici DNA zostały zastosowane do reprezentacji miast i dróg między nimi w następujący sposób: miasta reprezentowane były przez parami różne sekwencje DNA o określonej z góry długości. Natomiast ścieżkom między poszczególnymi miastami odpowiadały sekwencje DNA w połowie komplementarne z jednym i w połowie z drugim miastem. Do generowania odpowiednich sekwencji wykorzystuje się operację syntezy. Oto przykład – miasta oznaczone cyframi 1 i 2 oraz ścieżka między nimi.

Graf: reprezentacja DNA

 

Algorytm przeprowadzony na DNA (numery kroków obu algorytmów odpowiadają sobie nawzajem) przedstawia się w następujący sposób:

  1. Wrzuć do probówki po szczypcie DNA (w postaci stałej) reprezentującej każde z miast i każdą z możliwych dróg, dodaj wody i enzymów. Całość wymieszaj.
  2. Dokonaj replikacji nici, które zaczynają się w wierzchołku pierwszym i kończą w wierzchołku o numerze n.
  3. Za pomocą reakcji elektroforezy wydobądź ścieżki o długości wyłącznie n miast
  4. Za pomocą reakcji rozdziału opartego na powinowactwie wydobądź nici, w których wystąpiły wszystkie miasta.
  5. Jeśli w próbówce pozostały nici DNA to stanowią one rozwiązanie

 

Dlaczego to działa?

Krok 1

"Szczypta" DNA to naprawdę dużo - miliardy cząsteczek reprezentujących miasto bądź drogę. Kiedy je ze sobą zmieszamy, enzymy sprawią, że dojdzie do reakcji renaturacji (splatania) pomiędzy komplementarnymi nićmi. Operacja ta będzie niedeterministyczna, ponieważ cząsteczki łączą się ze sobą w sposób losowy.  Jest ich jednak tak dużo, że z dużym prawdopodobieństwem po zmieszaniu tego roztworu w próbówce będziemy mieć reprezentację wszystkich możliwych dróg. Dróg o różnych długościach, o różnych wierzchołkach początkowych i końcowych, również dróg z pętlami. Ale będą tam również drogi o które nam chodzi - ścieżki Hamiltona startujące w wierzchołku pierwszym, a kończące się w wierzchołku ostatnim. Wszystkie te drogi powstaną w krótkiej chwili wymieszania zawartości próbówki.

Dlaczego tak szybko? Otóż w próbówce mamy do czynienia z obliczeniami równoległymi, czyli wiele rozwiązań produkowanych jest w tym samym czasie.  Różnie fragmenty DNA łączą się przecież ze sobą niezależnie w tym samym czasie. Trzeba zaznaczyć, że w standardowych komputerach równoległość wymaga od komputera wielu procesorów i skomplikowanego oprogramowania (a więc jest kosztowna), a w obliczeniach cząsteczkowych mamy ją praktycznie za darmo. Co więcej, moc obliczeniowa DNA jest potencjalnie bardzo duża, a energia potrzebna do łączenia i rozdzielania nici stosunkowo niewielka.

Krok 2

Reakcja replikacji (namnażania) w tym przypadku dokonywana jest z użyciem specjalnych cząsteczek zwanych sondami. Sondy są  "przyczepione" do interesujacych nas końców cząsteczki - reprezentujących węzły o numerze 1 i n.  Doprowadzi to do wykładniczego zwiększania się liczby cząsteczek z właściwymi oboma końcami ścieżki, a liniowego powiększania się liczby cząsteczek z jednym właściwym końcem. Pozostałe cząsteczki nie będą replikowane. Po szeregu takich operacji ilość niewłaściwych cząsteczek w próbówce  będzie pomijalnie mała.

Krok 3

W tym kroku za pomocą reakcji elektroforezy na żelu dzielimy cząsteczki względem ich długości. Oczywiście interesują nas tylko drogi/cząsteczki o długości n (tyle ile miast) i tylko takie wybieramy do dalszych działań. Operacja ta bazuje na tym, że cząsteczka DNA ma ujemny ładunek elektryczny, a zatem przyciągana jest przez dodatnio naładowaną elektrodę. Z kolei prędkość poruszania się cząsteczki w stronę elektrody zależy od długości cząsteczki - im cząsteczka dłuższa, tym wolniej się porusza. Po określonym czasie możemy zatem sprawdzić, jak długi dystans cząsteczka przebyła (w żelu właśnie), co określa jej długość.

Krok 4

Reakcja ta polega na wrzucaniu do próbówki namagnesowanych metalowych kulek z przytwierdzonymi do nich tzw. sondami, czyli cząsteczkami będącymi komplementarnym odpowiednikiem jednego z miast. Następnie mieszanka jest ochładzana, co prowadzi do łączenia się komplementarnych nici. Cząsteczki, w których zawiera się dane miasto przyczepiają się do sondy. Następnie kulki wraz z przyczepionymi nićmi DNA przyciągane są magnesem, a reszta mieszanki jest wylewana. Dalsze operacje wykonywane są tylko na niciach, które zostały przytwierdzone do kulek – uwalniane są one przez podgrzanie mieszanki, co prowadzi do rozdzielenia nici od sond. Powtórzenie tej operacji dla każdego z miast gwarantuje otrzymanie na końcu nici, w których wystąpiło każde z miast.

Krok 5

Ponieważ w kroku 3 wyekstrahowano wyłącznie nici o odpowiedniej długości, a w kroku 4 sprawdzono obecność wszystkich n miast,  więc otrzymane ostatecznie nici stanowią rozwiązanie.

Koniec! Można zdjąć fartuch i okulary ochronne oraz poznać wreszcie rozwiązanie (a to już na następnej stronie).

 

 

5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com