pd-dok(2).pdf

(17987 KB) Pobierz
Uniwersytet Warszawski
Wydział Matematyki, Informatyki i Mechaniki
Paweł Daniluk
Analiza podobieństwa struktur
przestrzennych białek przy użyciu
deskryptorów lokalnej struktury
rozprawa doktorska
Promotor rozprawy
prof. dr hab. Bogdan Lesyng
Wydział Fizyki
Uniwersytet Warszawski
Sierpień 2011
Oświadczenie autora rozprawy
Oświadczam, że niniejsza rozprawa została napisana przeze mnie samo-
dzielnie.
data
podpis autora rozprawy
Oświadczenie promotora rozprawy
Niniejsza rozprawa jest gotowa do oceny przez recenzentów.
data
podpis promotora rozprawy
Streszczenie
W niniejszej rozprawie rozważamy zastosowanie deskryptorów lokalnej struktury do
identyfikowania podobieństw, uliniawiania i klasyfikacji struktury białek. Uliniowienie
struktur rozumiane jest jako dowolne odwzorowanie pomiędzy aminokwasami badanych
struktur. Dopuszczalne są przestawienia sekwencyjne oraz odkształcenia strukturalne.
Przedstawiamy formalną definicję deskryptorów, ich podobieństwa, uliniowień i
multi-uliniowień białek złożonych z uliniowień mniejszych wycinków struktury. Rozwa-
żamy problem znajdowania optymalnych uliniowień i dowodzimy NP-zupełności jego
wariantów. Mimo teoretycznej wykładniczej złożoności obliczeniowej przedstawionych
problemów podajemy wydajne algorytmy heurystyczne. Problem obliczania optymal-
nych uliniowień sprowadzamy do wyszukiwania maksymalnej kliki, rozwiązując go przy
pomocy metody podziałów i ograniczeń, Monte-Carlo z wymianą replik oraz heurystyki
opartej na twierdzeniu Motzkina-Strausa. Do znajdowania multi-uliniowień stosujemy
algorytm ewolucyjny.
Zaimplementowane algorytmy zostały przetestowane na popularnych zbiorach uli-
niowień referencyjnych: SISY, RIPC oraz SISY-multiple i porównane z innymi pu-
blicznie dostępnymi wiodącymi metodami. Algorytm uliniawiający pary struktur na
najtrudniejszym zbiorze testowym RIPC uzyskał średnią dokładność
77%
(druga pod
względem jakości metoda osiąga dokładność
60%).
Algorytm znajdowania multi-ulinio-
wień uzyskuje wyniki na poziomie najlepszych konkurencyjnych metod. Stworzony zo-
stał również serwis internetowy (http://bioexploratorium.pl/EP) udostępniający opi-
sane metody.
Słowa kluczowe
lokalne deskryptory struktury, uliniowienia strukturalne, porównywanie struktur, NP-
zupełność, fragmenty strukturalne, przestawienia sekwencyjne, permutacje cyrkularne,
multi-uliniowienia, wyszukiwanie klik, twierdzenie Motzkina-Strausa, algorytmy ewo-
lucyjne
Klasyfikacja ACM
F.1.3 Complexity Measures and Classes, F.2.2 Nonnumerical Algorithms and Problems,
J.3 Life and Medical Sciences
Abstract
In this thesis we discuss application of local descriptors of protein structure to iden-
tifying similarities, computing alignments, and carrying out classification of protein
structures. Definition of structural alignment is expanded to cover any arbitrary map-
ping of residues. Segment swaps and structural flexibility are allowed.
We present formal definitions of descriptors, their similarity, structural alignments
and multi-alignments assembled with alignments of small structural fragments. We
consider a problem of finding optimal alignments and prove NP-completeness of its se-
veral variants. Despite their intractability we give efficient heuristic algorithms, which
can be used to solve the aforementioned problems. We apply clique searching tech-
niques to compute optimal alignments such as branch-and-bound algorithm, replica
exchange Monte-Carlo, and a heuristic based on the Motzkin-Straus theorem. We use
an evolutionary algorithm to compute multi-alignments.
Implementations have been tested on popular reference alignment sets: SISY, RIPC
and SISY-multiple and compared with other leading, publicly available methods. The
pairwise alignment algorithm achieves an accuracy of
77%
on the most difficult RIPC
set (the second best method tested achieves
60%).
The multiple alignment algorithm
achieves results on par with other leading methods. Presented methods are available
online (http://bioexploratorium.pl/EP).
Keywords
local descriptors of protein structure, structural alignment, structure comparison, NP-
completeness, structural fragments, segment swaps, circular permutations, multiple
alignments, clique searching, Motzkin-Straus theorem, evolutionary algorithms
ACM Computing Classification
F.1.3 Complexity Measures and Classes, F.2.2 Nonnumerical Algorithms and Problems,
J.3 Life and Medical Sciences
Pragnę podziękować:
promotorowi tej rozprawy prof. Bogdanowi Lesyngowi za cenne rady, stworzenie do-
skonałych warunków do pracy i nieskończone pokłady optymizmu,
Rodzicom za niezachwianą wiarę we mnie,
oraz:
mojej Żonie za miłość i niezmierzoną cierpliwość
i Łucji za to, że jest.
Wam tę pracę poświęcam.
Badania realizowane były przy wsparciu finansowym grantu MNiSW (N N301 243736)
oraz projektu Biocentrum Ochota (POIG.02.03.00-00-003/09).

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin