|
|
|
|
| LEADER |
03532na a2200229 4500 |
| 003 |
HR-ZaFER |
| 008 |
160221s2019 ci ||||| m||| 00| 0 hr d |
| 035 |
|
|
|a (HR-ZaFER)ferid7100
|
| 040 |
|
|
|a HR-ZaFER
|b hrv
|c HR-ZaFER
|e ppiak
|
| 100 |
1 |
|
|a Batić, Dominik
|9 40276
|
| 245 |
1 |
0 |
|a Mapiranje slijeda na graf :
|b završni rad /
|c Dominik Batić ; [mentor Mile Šikić].
|
| 246 |
1 |
|
|a Sequence to Graph Mapping
|i Naslov na engleskom:
|
| 260 |
|
|
|a Zagreb,
|b D. Batić,
|c 2019.
|
| 300 |
|
|
|a 30 str. ;
|c 30 cm +
|e CD-ROM
|
| 502 |
|
|
|b preddiplomski studij
|c Fakultet elektrotehnike i računarstva u Zagrebu
|g smjer: Računarska znanost, šifra smjera: 41, datum predaje: 2019-06-14, datum završetka: 2019-07-12
|
| 520 |
3 |
|
|a 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.
|
| 520 |
3 |
|
|a Sažetak na engleskom: 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.
|
| 653 |
|
1 |
|a mapiranje
|a slijed
|a de Bruijn graf
|a graf
|
| 653 |
|
1 |
|a sequence mapping
|a de Brujin graph
|a graph
|
| 700 |
1 |
|
|a Šikić, Mile
|4 ths
|9 29535
|
| 942 |
|
|
|c Z
|
| 999 |
|
|
|c 51000
|d 51000
|