Mapiranje slijeda na graf : završni rad - Batić, Dominik (D. Batić, 2019)
Sažetak na hrvatskom: 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. Nažalost algoritam zbog prevelikih prekida u sekvencama grafa nije uspješan u mapiranju očitanja na graf.