Pregled bibliografske jedinice broj: 948610
Približni algoritam za brzo računanje poravnanja dvaju dugačkih nizova
Približni algoritam za brzo računanje poravnanja dvaju dugačkih nizova, 2018., diplomski rad, preddiplomski, Fakultet elektrotehnike i računarstva, Zagreb
CROSBI ID: 948610 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
Približni algoritam za brzo računanje poravnanja dvaju dugačkih nizova
(Approximate Algorithm for Computing Alignment Between Two Long Sequences)
Autori
Sodić, Filip
Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, preddiplomski
Fakultet
Fakultet elektrotehnike i računarstva
Mjesto
Zagreb
Datum
03.07
Godina
2018
Stranica
36
Mentor
Šikić, Mile
Ključne riječi
MinHash, Jaccard, Winnowing, Predstavnik, Skiciranje, Poravnanja dugih očitanja
(MinHash, Jaccard, Winnowing, Minimizer, Sketching, long read mapping)
Sažetak
Globalno poravnanje genoma važan je problem genomike. Zbog duljine genoma, računanje optimalnog puta poravnanja točnim algoritmima dinamičkog programiranja računalno je neizvedivo. Cilj ovog rada predstavljanje je i implementacija heurističkog algoritma poravnanja temeljenog na tehnikama traženja predstavnika i procjene Jaccardovog koeficijenta sličnosti skiciranjem. U poglavlju 2 dan je popis pretpostavki neophodnih za rad algoritma te popis pojmova za pomoć pri njegovom razumijevanju. Poglavlje 3 iznosi formalnu definiciju problema, a konkretan algoritam razvijen za njegovo rješavanje opisan je poglavljem 4. Implementacijski specifični detalji nevažni za opis algoritma na visokoj razini navedeni su u poglavlju 5. Rezultati i učinkovitost implementiranog algoritma istraženi su u poglavlju 6. Konačno, poglavlje 7 ukratko izdvaja najbitnije ideje rada.
Izvorni jezik
Hrvatski
