Brzo pretraživanje DNA sekvence zasnovano na kodiranju prostim brojevima (CROSBI ID 380487)
Ocjenski rad | diplomski rad
Podaci o odgovornosti
Matijaš, Lara Nastasja
Seršić, Damir
hrvatski
Brzo pretraživanje DNA sekvence zasnovano na kodiranju prostim brojevima
Pretraživanje uzorka s klasama znakova u tekstu kodiranima prostim brojevima znatno ubrzava pretraživanje. Ovaj algoritam koristi se za pretraživanje DNA. Uzorak i tekst kodiraju se kodovima dobivenim računanjem prvih σ prostih brojeva većih od duljine uzorka m. Nad tako kodiranim tekstom i uzorkom provodi se brza fourierova transformacija, te obavlja množenje tih dviju transformacija. Umnožak frekvencijske transformacije ulaznog signala odgovara konvoluciji u vremenu. Tekst i uzorak podudaraju se na i-toj lokaciji ako vrijedi: (p*t)mod(M) = 0, pri čemu je M umnožak dobivenih prostih brojeva. Dobiveni umnožak FFT-ova potrebno je inverznom fourierovom transformacijom „vratiti“ u vremensku domenu, te ispitati gornji uvjet. Cijeli program implementiran je u MATLAB-u, uz pomoć korisnički izgrađene klase podataka int_n koja omogućuje beskonačnu preciznost ulaznih brojeva (koji ovise o duljini uzorka i teksta). Provedena je FFT transformacija nad uzorkom i segmentima teksta duljine 2*m. Nakon toga obavljeno je množenje transformacija. Zbog pogreške kod zaokruživanja u funkciji FFT, dolazi do odstupanja kod nekih uzoraka rezultata. Konačni rezultat također odstupa od željenih vrijednosti te je potrebno nadograditi postojeći program za decimalne brojeve, kako bi se eliminirale pogreške.
Pretraživanje teksta s klasama uzorka; brza Fourierova transformacija; DNA pretraživanje
nije evidentirano
engleski
Fast pattern matching in DNA sequence using prime number encoding
nije evidentirano
Pattern mathing with character; Fast Fourier Transformation; DNA pattern matching
nije evidentirano
Podaci o izdanju
41
12.07.2013.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Fakultet elektrotehnike i računarstva
Zagreb