Komputer DNA

Wyobraźmy sobie, że musimy odwiedzić sześć miast, Warszawę, Przemyśl, Białystok, Wrocław, Poznań i Szczecin. Ze względu na ograniczony budżet nie możemy sobie pozwolić na kilkukrotne odwiedzenie tego samego miasta, w każdym możemy być tylko raz, a ze względu na nasz cenny czas oczywiście chcemy to zrobić jak najkrótszą drogą. Jest to tak zwany problem komiwojażera i gdybyśmy go rozwiązali, to otrzymalibyśmy graf hamiltonowski. Graf taki, wierzchołki połączone ścieżką hamiltonowską, czyli odcinkami, które łączą wszystkie wierzchołki i przez każdy z nich przechodzą dokładnie jeden raz. Problem możemy rozwiązać algorytmicznie, ale czy nie byłoby ekscytujące, gdybyśmy zastosowali do rozwiązania komputer DNA? Komputer DNA jest urządzeniem stosowananym do obliczeń, które zachodzą w oparciu o reakcje chemiczne między cząsteczkami DNA. Jednak zamiast zagłębiać się w teorię, zobaczmy na przykładzie jak taki komputer DNA może rozwiązać problem komiwojażera!

Mamy sześć miast, więc na samym początku potrzebujemy sześciu jednoniciowych fragmentów DNA. Każdy z nich jest inny i każdy z nich ma identyczną długość. Następnie, potrzebujemy kolejnych, antysensownych fragmentów DNA, które będą odpowiadały drogom pomiędzy miastami. Podobnie jak w przypadku odpowiedników miast, fragmenty te mają identyczną długość i są komplementarne do końca jednego miasta i początku drugiego. Przykładowo, jeśli Warszawa to ATTGCCCC, natomiast Przemyśl to GCTAATCG, a chcemy uzyskać fragment odpowiadający podróży z Warszawy do Przemyśla, to potrzebujemy fragment GGGGCGAT. Z kolei, gdybyśmy chcieli uzyskać fragment odpowiadający podróży z Przemyśla do Warszawy, potrzebujemy TAGCTAAC. Do mieszaniny wszystkich fragmentów DNA dodajemy ligazę DNA, która pozwala na otrzymanie dwuniciowych fragmentów DNA różnej długości. W tym, jeden fragment, który jest rozwiązaniem naszego problemu. Co dalej?

Przeprowadzamy reakcję PCR, by zreplikować jedynie te fragmenty DNA, które kończą się różnymi miastami. Może się zdarzyć, że fragment rozpocznie się i zakończy tym samym miastem. Takich fragmentów nie potrzebujemy, ponieważ nie spełniają one wymagania, by w każdym mieście pojawić się tylko raz. Jednak może to oznaczać, że będziemy replikować fragmenty takie jak Warszawa-Przemyśl-Białystok, albo Warszawa-Warszawa-Przemyśl-Białystok lub dłuższe, które zawierają wszystkie miasta, niektóre powtórzone. Stosujemy więc metody pozwalające na podział fragmentów pod względem masy (np. elektroforeza), aby oddzielić te fragmenty, które mają właściwą masę cząsteczkową, czyli zawierają sześć miast. Jednak co w przypadku jeśli wydzielimy sekwencje Warszawa-Przemyśl-Białystok-Szczecin-Przemyśl-Poznań? Hybrydyzacja pozwoli nam się upewnić, czy fragmenty odpowiadające są wszystkim miastom. Teraz nadszedł czas na sekwencjonowanie zwycięzcy. I tak oto zastosowaliśmy komputer DNA, by rozwiązał problem komiwojażera!