Naslov
Mapiranje slijeda na graf
(Sequence to graph mapping)

Autori
Batić, Dominik

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

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
03.07

Godina
2019

Stranica
29

Mentor
Šikić, Mile

Neposredni voditelj
Vaser, Robert

Ključne riječi
mapiranje, graf, DNA
(mapping, graph, DNA)

Sažetak
Poravnanje dviju sekvenci jedan je od glavnih problema u bioinformatici. U svrhu rješavanja tog problema razvijeni su brojni algoritmi. Najpoznatiji algoritmi su Needleman – Wunschov algoritam globalnog poravnanja te Smith - Watermanov algoritam lokalnog poravnanja. Iako precizni dani algoritmi imaju kvadratnu memorijsku i vremensku složenost što ih čini neupotrebljivim pri poravnanju dugih sekvenci poput poravnanja očitanja na ljudski genom. S ciljem smanjenja vremenske i prostorne složenosti razvijeni su algoritmi temeljeni na heuristici. Kako bi kompaktnije prikazali podatke danas se sve više referentni genom zamjenjuje grafičkim prikazima poput de Brujin grafova. U ovom radu razmotrili smo heuristički algoritam koji poravnava očitanja na graf. Pri tome su za izradu i samo poravnanje korišteni već gotovi alati BCALM2 i GraphAligner. Algoritam predočen u ovom radu međukorak je između navedenih alata. U cilju smanjenja vremenske složenosti poravnanja on pronalazi regije grafa na koje bi se mapirala očitanja. Na taj način izdvajamo podgrafove izvornog grafa i mapiranje vršimo nad njima. Algoritam pokazuje jako dobre rezultate na potpuno linearnom grafu i neloše rezultate na SNP grafovima. Rad bi imao potencijala za primjenu na SNP grafovima uz daljnja poboljšanja

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA