Mapiranje slijeda na graf

undergraduate thesis

• Title (english): Sequence to Graph Mapping
• Author: Dominik Batić
• Mentor: Mile Šikić (mentor)
• Committee member: Mile Šikić (predsjednik povjerenstva)
• Committee member: Krešimir Križanović (član povjerenstva)
• Committee member: Robert Vaser (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-07-12, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: mapiranje; slijed; de Bruijn graf; graf
• Keywords (english): sequence mapping; de Brujin graph; graph
• Language: croatian
• URN:NBN: urn:nbn:hr:168:875581
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2020-01-07 16:38:45