Mapiranje slijeda na graf

završni rad

• Naslov (engleski): Sequence to Graph Mapping
• Autor: Dominik Batić
• Mentor: Mile Šikić (mentor)
• Član povjerenstva: Mile Šikić (predsjednik povjerenstva)
• Član povjerenstva: Krešimir Križanović (član povjerenstva)
• Član povjerenstva: Robert Vaser (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2019-07-12, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

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. Nažalost algoritam zbog prevelikih prekida u sekvencama grafa nije uspješan u mapiranju očitanja na graf.

Sažetak (engleski)

Sequence alignment remains one of the most challenging problems in the field of bioinformatics. In order to solve this problem many algorithms have been developed. One of the most well-known algorithms include dynamic programing algorithm for global alignment, introduced by Needleman and Wunsch and local alignment algorithm, introduced by Smith and Waterman. Despite their excellent alignment accuracy their time complexity of O (n^2) renders them impractical when aligning long sequences. In attempt to reduce time and space complexity new algorithms based on heuristics have been developed. In order to compactly represent data from a set of reeds reference genomes are nowadays being more and more replaced by graphical representations such as de Brujin graphs. In this paper we discussed a heuristic based algorithm for sequence to graph alignment. The algorithm uses already existing tools for compacting a de Brujin graph and mapping reeds to the said graph, named BCALM2 and GraphAligner respectively. Our algorithm steps in between those tools. To reduce time complexity of the alignment process it finds regions to which reeds map. By doing so we single out subgraphs which are then used in the alignment. Unfortunately, due to gaps that occur between regions, matching minimizers in sequences and regions fails to produce effective results.

• Ključne riječi: mapiranje; slijed; de Bruijn graf; graf
• Ključne riječi (engleski): sequence mapping; de Brujin graph; graph
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:875581
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2020-01-07 16:38:45