Monte karlo metode I primene u bioinformatici master rad

UNIVERZITET U BEOGRADU

MATEMATIČKI FAKULTET

SMER: RAČUNARSTVO I INFORMATIKA

MONTE KARLO METODE I PRIMENE U BIOINFORMATICI

-MASTER RAD-

Mentor: Student:

Prof. dr Gordana Pavlović-Lažetić Marija Đurić

Beograd, 2017.

Sadržaj

2.1 Monte Karlo metoda i najčešće primene 7

2.2 Različiti pristupi rešavanja problema 9

2.3 Markovljevi lanci 13

3.1 Uvod 18

3.2 Metropolis algoritam 19

3.3 Matematička formulacija Metropolis - Hestingovog algoritma 21

3.4 Specijalni Metropolis algoritmi 24

3.4.1 Slučajno kretanje 24

3.4.2 Metropolizovan nezavisni uzorkivač 25

4.1 Uvod 28

4.2 Gibsov algoritam uzorkovanja 29

4.3 Primeri Gibsovog uzorkivača 32

4.4 Specijalni primeri Gibsovog uzorkivača 35

4.4.1 Uzorkovanje po nivoima 35

4.4.2 Metropolizovan Gibsov uzorkivač 35

4.4.3 Hit and run algoritam 36

5.1 Uvijanje proteina 38

5.2 Monte Karlo metoda razmene kopija 41

5.2.1. Uvod 41

5.2.2 Molekulska dinamika 42

5.2.3 Softverski paketi za simulaciju molekulske dinamike 46

5.2.4 Algoritam Monte Karlo Razmena Kopija 49

5.3 Rezultati primene MKRK na problem uvijanje proteina 53

1. UVOD

Sam princip rada Monte Karlo simulacije nastaje 1777. godine kada se Žorž Luis Lekler poznatiji kao Kompte de Bufon (Georges Louis Leclerc, Compte de Buffon 1707-1788) zapitao kolika je verovatnoća da drvce dužine bačeno na rešetku razmaka ( > ) padne na jednu od linija rešetke. Došao je do sledećeg rezultata [1]:

=

Koristeći ovo rešenje, matematičar Laplas (Pierre-Simon Laplace,1749-1827) je došao do jedinstvenog načina određivanja broja π. Neka je Bufonov eksperiment izveden bacanjem drvceta puta i neka označava koliko puta je drvce palo na liniju, tada je verovatnoća jednaka:

=

Iz ovih jednakosti se lako određuje broj :

Formalno, Monte Karlo simulaciju razvili su tokom 1940. godine dvojica američkih naučnika Stanislav Ulam (Stanislaw Ulam, 1909-1984) i Džon fon Nojman (John von Neumann, 1903-1957) u Los Alamos Nacionalnoj laboratoriji dok su sarađivali na projektu Menhetn (eng. Manhattan). Simulaciju su koristili da bi odredili slučajnu difuziju neutrona i nazvali su je Monte Karlo, prema gradu u Monaku i njegovim mnogobrojnim kazinima. Projekat Menheten je bio naziv za tajni program vlada SAD, Kanade i Ujedinjenog kraljevstva čiji je cilj bio razvoj atomske bombe [2].

Danas se Monte Karlo metoda koristi u različitim oblastima, kao što su: biologija, genetika, statistika, itd. Metode Monte Karlo se primenjuju posebno u slučajevima kada bi eksperimenti sa sistemom koji proučavamo bili dugotrajni ili dovodili do oštećenja sistema. Problemi koji se sreću u raznim oblastima se mogu “prevesti” ili svesti na matematičke probleme: rešavanje sistema linearnih jednačina ili nejednačina, računanje integrala (jednostrukih ili višestrukih), rešavanje diferencijalnih jednačina, rešavanje parcijalnih diferencijalnih jednačina, itd.

U ovom radu će pored objašnjenja Monte Karlo metoda biti predstavljena i opisana njihova primena na problem uvijanja proteina kao jedan od važnih problema proteomike i bioinformatike. Prvo poglavlje ovog rada je posvećeno predstavljanju najčešćih primena Monte Kralo metoda kao i nekih njenih osnovnih tehnika, kao što su uzorkovanje odbacivanje, uzorkovanje po značajnosti i Markovljevi lanci. U trećem i četvrtom poglavlju su opisana dva najvažnija Monte Karlo algoritma, Metropolis-Hestingov algoritam i Gibsov uzorkivač, kao i neke njihove varijacije. Poslednje poglavlje sadrži objašnjenje Monte Karlo algoritma razmene kopija i rezultate primene ovog metoda na problem uvijanja proteina.

2. OSNOVE MONTE KARLO METODE

2.1 Monte Karlo metoda i najčešće primene

Monte Karlo metodu predstavlja grupa algoritama čija je suština ponavljanje slučajnih pokušaja u cilju dobijanja numeričkih rezultata. Često se koristi za rešavanje fizičkih i matematičkih problema, posebno u slučajevima kada je nemoguće koristiti druge matematičke metode. Monte Karlo metoda se najčešće koristi za rešavanje problema optimizacije, numeričke integracije i za generisanje uzoraka kod raspodele verovatnoće.

Prilikom upotrebe statističkih metoda često se nailazi na problem izračunavanja integrala oblika:

.

Ovaj problem se može rešiti upotrebom metoda numeričke integracije, ali samo ukoliko se radi o prostoru manjih dimenzija. Za višedimenzione prostore, rešenje predstavlja upoteba Monte Karlo metode kojom se problem izračunavanja integrala svodi na proces uzorkovanja iz određene raspodele verovatnoće i izračunavanje srednje vrednosti dobijenih uzoraka. Neka funkcija zadovoljava sledeća dva uslova:

≥ 0,

sada možemo definisati odgovarajuću raspodelu verovatnoće na intervalu () sa:

Uvođenjem ove smene integral ima sledeću vrednost:

gde predstavlja očekivanu vrednost funkcije ℎ(x) izračunatu korišćenjem uzoraka iz pridružene raspodele verovatnoće, a koja se može aproksimirati na sledeći način:

gde su =1,…, nezavisno uzeti iz [15]. Kako bi izračunavanje integrala i bilo moguće potrebno je odabrati odgovarajuću funkciju raspodele iz koje se jednostavno može vršiti uzorkovanje, a u nastavku rada će biti opisane neke od osnovnih tehnika uzorkovanja, među kojima su i Markovljevi lanci.

Monte Karlo metode se najčešće koriste pri rešavanju integrala i problema optimizacije u višedimenzionim prostorima kada se oni ne mogu izračunati analitički ili za njih ne postoji efikasan numerički algoritam. Ovi problemi se mogu podeliti u dve grupe: problem izračunavanja očekivanja i problemi različitih varijacija. Objasnićemo ukratko svaki od njih [3]:

Problem izračunavanja očekivanja: Neka je X = slučajna promenljiva čije komponente mogu biti diskretene ili neprekidne i neka je raspodela verovatnoće promenljivih data preko nenormalizovane funkcije gustine Naš zadatak je da odredimo očekivanje funkcije u zavisnosti od raspodele verovatnoće. U slučaju diskretne raspodele očekivanje se računa na sledeći načih:

dok se kod neprekidne raspodele suma zamenjuje integralom što dodatno komplikuje izračunavanje. Takođe smo pretpostavili da se za svako mogu izračunati vrednosti funkcija i , ali njihovo izračunavanje u nekim slučajevima, naročito u višedimenzionim prostorima, zahteva dosta vremena, pa je naš cilj da minimalizujemo taj broj izračunavanja .

Problemi različitih varijacija: Neka problem koji želimo da rešimo ima funkciju gustine koja značajno varira na svom domenu, sa najvećom verovatnoćom u veoma malim delovima domena čije lokacije nisu poznate a priori. Zbog ove karakteristike rešenje ovakvih problema zahteva pronalaženje metoda koje će odrediti delove domena sa najvećom verovatnoćom.

U mnogim slučajevima nije moguće dobiti nezavisne uzorke iz raspodele definisane pomoću funkcije već se koriste zavisni uzorci najbliži zadatoj raspodeli dobijeni korišćenjem metode Markovljevih lanaca [3]. Razvoj ovih metoda i njihovo dalje istraživanje može doprineti pronalaženju boljih ocena očekivanja sa većom verovatnoćom tačnosti.