Naslov
Brzo pretraživanje DNA sekvence zasnovano na kodiranju prostim brojevima
(Fast pattern matching in DNA sequence using prime number encoding)

Autori
Matijaš, Lara Nastasja

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
12.07

Godina
2013

Stranica
41

Mentor
Seršić, Damir

Ključne riječi
Pretraživanje teksta s klasama uzorka; brza Fourierova transformacija; DNA pretraživanje
(Pattern mathing with character; Fast Fourier Transformation; DNA pattern matching)

Sažetak
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.

Izvorni jezik
Hrvatski

Znanstvena područja
Elektrotehnika

POVEZANOST RADA