Poravnanje dugačkih RNA očitanja

undergraduate thesis

• Title (english): RNA-seq aligner for long reads
• Author: Antonio Jurić
• 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: 2016-09-12, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Poravnanje dugačkih RNA očitanja jest problem pronalska s kojeg dijela reference je nastalo dobiveno RNA očitanje. Problem se razlikuje od poravnanja DNA nizova u kojem želimo sastaviti cjelokupni genom zbog posebnih stvojstava RNA koja bitno kompliciraju cijeli proces. U ovom radu opisana je problematika poravnanja nizova RNA. Alat za poravnanje nizova GraphMap problem poravnanja nizova RNA rješava u pet faza: posljednju fazu obrađuje ovaj rad. U toj fazi pokušavamo pronaći najbolje grupe (manje dijelove očitanja) za poravnanje pojedinog očitanja. Algoritam koji je razvijen za problem odabira najboljih grupa sadrži dva algoritma koji se pokreću ovisno u ukupnom broju grupa: knapsack složenosti 𝑂(𝑁^2) te 2D logaritamsku strukturu složenosti 𝑂(𝑁⋅𝑙𝑜𝑔^2(𝑁)) gdje je N broj grupa.

Abstract (english)

Long RNA-seq alignment is problem of finding from which part of reference RNA read comes from. Problem is different from DNA alignment in which we want to compose whole genome because of special properties of RNA which make whole process more complicated. In this paper process of RNA alignment is described. Tool for alignment GraphMap solves the problem of alignment in five phases: last phase is described in this paper. In that phase we try to find best clusters (smaller parts of reads) for alignment of one read. Algorithm which is developed for problem of selecting best clusters is composed of two algorithms which are used depending on total number of clusters: knapsack with complexity of 𝑂(𝑁^2) and 2D logarithmic structure with complexity of 𝑂(𝑁⋅𝑙𝑜𝑔^2(𝑁)) where N is the number of clusters.

• Keywords: poravnanje RNA očitanja; knapsack; logaritamska struktura; GraphMap; bioinformatika
• Keywords (english): RNA-seq alignment; knapsack; logarithmic structure; GraphMap; bioinformatics
• Language: croatian
• URN:NBN: urn:nbn:hr:168:586637
• 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: 2018-02-06 09:30:45