streszczenie-glowacki(1).pdf

(159 KB) Pobierz
POLITECHNIKA POZNAŃSKA
Wydział Informatyki
Instytut Informatyki
Zastosowanie metod opartych na teorii
grafów do rozwiązywania wybranych
problemów analizy sekwencji
nukleotydowych i aminokwasowych
Tomasz Głowacki
Streszczenie rozprawy doktorskiej
Promotor:
dr hab. inż. Piotr Formanowicz, profesor PP
Poznań 2013
Spis treści
1 Wprowadzenie
1.1 Wstęp
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Uzasadnienie podjęcia badań
. . . . . . . . . . . . . . . . . . . . . . . . .
2 Podstawy matematyczne i informatyczne
2.1 Wprowadzenie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Podstawowe zagadnienia biologii molekularnej i chemii
3.1 Wprowadzenie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Biblioteki oligonukleotydów antykomplementarnych
4.1 Wprowadzenie i motywacja
. . . . . . . . . . . . . . . . . . . . . . . . . .
1
1
3
5
5
7
7
8
8
5 Sekwencjonowanie łańcuchów peptydowych
11
5.1 Wstęp
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
6 Asemblacja łańcuchów peptydowych
7 Wyniki eksperymentów obliczeniowych
8 Podsumowanie
13
15
22
Bibliografia
24
i
Rozdział 1
Wprowadzenie
1.1
Wstęp
W drugiej połowie XX wieku rozpoczął się ogromny postęp we wszystkich dziedzinach
biologii molekularnej. Powstały i rozwinęły się zupełnie nowe gałęzie nauki na pograni-
czu matematyki, biologii oraz nieco później informatyki. Przykładami nowych, szybko
rozwijających się nauk jest bioinformatyka czy biologia obliczeniowa.
W biologii obliczeniowej z powodzeniem stosuje się skomplikowane modele matema-
tyczne, by przedstawić zachodzące w przyrodzie procesy lub wspomóc przetwarzanie
ogromnej ilości informacji.
Teoria grafów jest jednym z działów matematyki często wykorzystywanych do modelo-
wania zjawisk biologicznych. Warto by tu wspomnieć modele grafowe wykorzystywane w
sekwencjonowaniu DNA [4], modelowaniu drzew filogenetycznych [5], czy przewidywaniu
funkcji białek [6].
Autor niniejszej rozprawy skupia się na analizie sekwencji białek i DNA oraz proponuje
własne modele grafowe do rozwiązania zagadnień związanych z sekwencjami: rekonstruk-
cji sekwencji białkowych na podstawie eksperymentów chemicznych oraz projektowania
bibliotek sekwencji DNA o minimalnej wzajemnej zdolności do hybrydyzacji.
Jednym z ważniejszych problemów biologii obliczeniowej jest ustalanie budowy pep-
tydów [7]. Peptydy są to wielocząsteczkowe związki składające się z aminokwasów po-
łączonych w długie sekwencje. Długie peptydy, których sekwencje składają się z więcej
niż 100 aminokwasów, nazywane są białkami [15].
Znajomość budowy białek pozwala na przewidywanie ich funkcji w organizmie, a co
za tym idzie, może mocno wesprzeć przemysł farmaceutyczny w projektowaniu leków.
Pierwszym krokiem w celu określenia budowy białek jest rozpoznanie sekwencji amino-
kwasów w cząsteczce.
Brak bezpośrednich metod chemicznych do rozpoznania długich sekwencji aminokwa-
sowych rodzi naturalną potrzebę zastosowania metod informatycznych umożliwiających
odtworzenie tego rodzaju sekwencji. Odczytywanie krótkich łańcuchów peptydowych
nazywamy sekwencjonowaniem.
Współczesne metody chemii analitycznej pozwalają na określenie sekwencji pepty-
dów nieprzekraczająch 50 aminokwasów (metoda Edmana) [15]. Szybko rozwijającą się
metodą identyfikacji związków chemicznych, w tym ustalania sekwencji białek, jest spek-
trometria masowa. Wynikiem działania spektrometru jest widmo masowe przedstawiące
statystyczny rozkład jonów o różnej masie w oryginalnej cząsteczce [11]. Jednym z po-
dejść do identyfikacji białek na podstawie widma masowego jest przeszukiwanie baz da-
nych w poszukiwaniu tego widma. Takie podejście pozwala na rozpoznać jedynie znane
białko. Metody określania budowy białka bazujące jedynie na widmie masowym tj. bez
1
Wprowadzenie
2
odwoływania się do baz danych określane są jako metody de novo. W niniejszej rozprawie
analizuje się jeden z problemów sekwencjonowania i proponuje wielomianowy algorytm
do jego rozwiązania.
Jeden z rozdziałów niniejszej rozprawy poświęcony jest zagadnieniu konstruowania
bibliotek oligonukleotydów antykomplementarnych. Są to biblioteki łańcuchów DNA,
których globalna zdolność do hybrydyzacji między sobą jest minimalna. Istnieje kilka
zastosowań tego typu bibliotek. Jednym z nich są klasyczne komputery DNA, które zo-
stały zaproponowane w 1994 roku przez Adlemana [1]. Cząsteczki DNA kodują pewne
informacje, a obliczenia zachodzą dzięki reakcjom chemicznym, w których te cząsteczki
uczestniczą. Adleman zaproponował rozwiązanie problemu szukania ścieżki Hamiltona
w grafie skierowanym. W doświadczeniu zaproponowanym przez niego część łańcuchów
koduje wierzchołki grafu, pozostała część koduje łuki między wierzchołkami. Hybrydyza-
cja trzech łańcuchów odpowiadającym wierzchołkowi łukowi i kolejnemu wierzchołkowi
symbolizuje przejście w grafie z pierwszego wierzchołka do drugiego wybranym łukiem.
Obliczenia toczą się równolegle, w tym znaczeniu idea komputerów DNA przypomina do
pewnego stopnia ideę Niedeterministycznej Maszyny Turinga. Aby zwiększyć wydajność
reakcji zachodzących podczas obliczeń komputerów DNA, powinno dążyć się do mini-
malizacji prawdopodobieństwa hybrydyzacji cząsteczek, których połączenie nie koduje
powstania cząsteczki kodującej rozwiązanie danego problemu. W tym celu tworzy się bi-
blioteki oligonukleotydów antykomplementarnych. Elementy tej biblioteki umożliwiają
kodowanie instancji za pomocą oligonukleotydów w taki sposób, aby minimalizować
prawdopodobieństwo niechcianych hybrydyzacji.
Niniejsza rozprawa doktorska składa się z ośmiu rozdziałów, których zawartość jest
następująca:
- Rozdział I zawiera uzasadnienie podjęcia badań oraz wstępne założenia pracy na
podstawie których sformułowano tezę.
- Rozdział II poświęcony jest podstawom matematycznym oraz informatycznym nie-
zbędnym do zrozumienia dalszych rozważań przedstawionych w rozprawie.
- Rozdział III poświęcony jest wybranym zagadnieniom biologicznym. Opisano w
nim peptydy oraz DNA, gdyż praca skupia się na rozwiązywaniu kilku proble-
mów analizy sekwencji tych dwóch typów cząsteczek. Przedstawiono biologiczną
motywację do podjęcia badań.
- Rozdział IV dotyczy problemu budowania bibliotek oligonukleotydów antykomple-
mentarnych. W rozdziale tym zdefiniowano problem i zaproponowano algorytm do
jego rozwiązania. Rozdział ten jest również krótkim wprowadzeniem do klasycz-
nych komputerów DNA, gdyż zaproponowane metody znajdują zastosowanie przy
projektowaniu algorytmów przeznaczonych do wykonania za pomocą tego typu
komputerów.
- Rozdział V dotyczy ustalania sekwencji krótkich łańcuchów peptydowych (sekwen-
cjonowania). W rozdziale tym opisano dwa popularne podejścia do sekwencjono-
wania: degradację Edmana oraz spektrometrię masową. Przedstawiono krótką kla-
syfikację problemów drugiego typu. Zaproponowano algorytm sekwencjonowania
de novo do rozwiązania problemu sekwencjonowania opartego na danych pocho-
dzących z rzeczywistego eksperymentu spektrometrycznego.
- Rozdział VI dotyczy metod asemblacji krótkich łańcuchów peptydowych. Opisano
eksperyment biochemiczny, którego wyniki posłużyły do zdefiniowania problemów
Wprowadzenie
3
kombinatorycznych będących modelami problemów asemblacji. Przedstawiono kla-
syfikację problemów asemblacji oraz zaproponowano wielomianowy dokładny algo-
rytm do rozwiązania jednego z nich. W pracy pokazano, że przypadek asemblacji
bez błędów jest łatwy obliczeniowo. Podano formalną definicję grafów peptydo-
wych będących reprezentacją tego problemu. Dla problemu asemblacji trudnego
obliczeniowo zaproponowano metodę GRASP oraz algorytm ewolucyjny. Przed-
stawiono również heurystykę dedykowaną.
- Rozdział VII przedstawia wyniki eksperymentu obliczeniowego przeprowadzonego
dla NP-trudnego problemu asemblacji. Metody zaproponowane w rozdziale VI (al-
gorytm ewolucyjny, GRASP oraz heurystyka dedykowana) zostały zaimplemento-
wane i przetestowane. Wyniki zostały przedstawione w postaci tabel oraz wykre-
sów.
- Rozdział VIII jest podsumowaniem rozprawy. Wskazano nowe, potencjalne kie-
runki badań, które pojawiły się podczas pisania tej pracy.
1.2
Uzasadnienie podjęcia badań
W piątym i szóstym rozdziale niniejszej rozprawy autor koncentruje się na określeniu se-
kwencji białkowej. Proponowana jest metoda sekwencjonowania de novo oraz algorytmy
asemblacji pozwalające na odtworzenie długich łańcuchów peptydowych na podstawie
krótszych, pochodzących z fazy sekwencjonowania. Rozważane są różnego rodzaju błędy
pochodzące z fazy eksperymentu chemicznego, dzięki czemu analizowane metody lepiej
opisują rzeczywistość.
Znajomość sekwencji białkowych jest pierwszym krokiem do poznania ich budowy
przestrzennej oraz ich własności, co jest jednym z kluczowych zagadnień współczesnej
biologii obliczeniowej. Analiza nowych eksperymentów chemicznych, takich jak asembla-
cja przy wykorzystaniu endopeptydaz oraz sekwencjonowanie za pomocą spektrometrii
mas pociąga za sobą konieczność zdefiniowania nowych problemów kombinatorycznych,
które należy rozważyć w fazie obliczeniowej oraz konstrukcji algorytmów rozwiązujących
te problemy.
Motywacją do podjęcia badań dotyczących bibliotek oligonukleotydów antykomple-
mentarnych jest stworzenie wielomianowej metody, która pozwoli zaproponować lepsze
kodowanie instancji problemów dla komputerów DNA.
Bazując na powyższych wytycznych określono założenia wstępne pracy:
- Zaprezentowane modele i metody asemblacji oraz sekwencjonowania łańcuchów
peptydowych pozwolą na odtworzenie łańcuchów białkowych na podstawie prze-
prowadzonych eksperymentów chemicznych.
- Metoda sekwencjonowania de novo pozwoli na poznanie nowych, nieznanych se-
kwencji aminokwasowych.
- Metoda tworzenia bibliotek oligonukleotydów antykomplementarnych pozwoli na
budowanie zbiorów oligonukleotydów, których zdolność do wzajemnej hybrydyzacji
jest minimalna.
- Możliwość adaptacji wielu modeli termodynamicznych do metody tworzenia bi-
bliotek oligonukleotydów antykomplementarnych pozwoli na łatwe dostosowanie
tej metody do konkretnych wymagań.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin