Application for Mapping Reads to a Reference With Optimized Memory Usage

U ovom radu opisan je postupak poravnanja sekvenci na referentni genom. Svaki korak postupka obilježen je jednim od algoritama koji su definirani u poglavljima rada. Početak rada prikazuje i objašnjava algoritam pronalaženja minimizera u nizu, te njihovu potrebu za daljnje poravnanje. Nadalje, uvodi se pojam poravnanja nizova i definiraju se dinamički algoritmi za izračun poravnanja: Needleman-Wunsch, Smith-Waterman, polu-globalni, te Hirschbergov algoritam. Na kraju rada opisan je postupak traženja najduljeg rastućeg podniza, te spajanja svih ranije navedenih algoritama u cjeloviti program. Uz to provedena je i usporedba rezultata ovog programa sa rezultatima minimapa2.In this paper, the sequence alignment procedure on the reference genome is described. Each step of the procedure is marked by one of the aglorithms defined in the chapters of the paper. Beginning of the paper shows and explains the algorithm for finding minimizers in a sequence. Furthermore, the notion of sequence alignment is introduced and dynamic algorithms for calculating alignment are defined: Needleman-Wunsch, Smith-Waterman, semi-global, and Hirschberg algorithm. At the end of the paper, the procedure of searching for the longest increasing subsequence, and merging of all the previously mentioned algorithms into a complete program is described. In addition, a comparison of the results of this program with the results of the minimap2 was conducted