RNA-seq aligner for long reads

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.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