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