Implementacija učinkovitog algoritma za izgradnju sufiksnog polja

undergraduate thesis

• Title (english): Implementation of the efficient suffix array construction algorithm
• Author: Ivona Šarić
• Mentor: Mirjana Domazet-Lošo (mentor)
• Committee member: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Committee member: Krešimir Fertalj (član povjerenstva)
• Committee member: Vedran Mornar (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-05, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom radu objašnjeno je značenje indeksiranja genomskih sljedova. Opisane su strukture podataka sufiksno stablo i sufiksno polje te njihovo značenje u području bioinformatike. Objašnjeni su koraci SACA-K algoritma za izgradnju sufiksnog polja, odnosno za indeksiranje ulaznog niza. Implementirala sam navedeni algoritam u programskom jeziku Python te sam performanse usporedila s originalnom implementacijom izvedenom u programskom jeziku C++. Oba programska koda testirala sam na istim skupovima podataka. Vrijeme izvođenja i memorijsku potrošnju testirala sam na sintetskim podacima i genomu čovjeka.

Abstract (english)

In this thesis, the significance of genomic sequence indexing is explained. I described data structures suffix trees and suffix arrays and their meaning in the field of bioinformatics and explained the steps of the SACA-K algorithm for constructing a suffix array, i.e. for indexing an input string. I implemented the above algorithm in the Python programming language and compared its performance to the original implementation performed in the C++ programming language. I tested both programs on the same data sets. I measured the running time and memory requirements of the synthetic data set and the reference human genome.

• Keywords: SACA-K; sufiksno polje; inducirano sortiranje; vremenska složenost; prostorna složenost
• Keywords (english): SACA-K; suffix array; induced sorting; time complexity; workspace complexity
• Language: croatian
• URN:NBN: urn:nbn:hr:168:965208
• 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: 2023-01-14 21:44:50