Implementacija učinkovitog algoritma za izgradnju poboljšanog sufiksnog polja

završni rad

• Naslov (engleski): Implementation of the efficient enhanced suffix-array construction algorithm
• Autor: Hana Jurić Fot
• Mentor: Mirjana Domazet-Lošo (mentor)
• Član povjerenstva: Mirjana Domazet-Lošo (predsjednik povjerenstva)
• Član povjerenstva: Mario Brčić (član povjerenstva)
• Član povjerenstva: Mihael Kovač (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-06-30, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U bioinformatici se često javlja potreba za pretraživanjem velikih nizova (DNA i proteinskih sljedova) različitim podnizovima. Kako bi se taj problem riješio u razumnom vremenu, potrebno je koristiti efikasne strukture indeksiranja teksta, kao što su sufiksno stablo i sufiksno polje, koje se mogu izgraditi u linearnom vremenu. Sufiksno polje samo po sebi ima neke nedostatke u odnosu na sufiksno stablo pa se zato često proširuje i nadograđuje. Algoritam gSAIS nadogradnja je popularnog SAIS algoritma za izgradnju sufiksnog polja koja omogućuje izgradnju sufiksnog polja nad kolekcijom nizova.

Sažetak (engleski)

In bioinformatics there is often need to search large strings (DNA and protein sequences) with different substrings. In order to solve this problem in reasonable time, it is necessary to use efficient text indexing structures, such as suffix trees and suffix arrays, which can be built in linear time. The suffix array itself has some disadvantages compared to the suffix tree and is often expanded and upgraded. The gSAIS algorithm is an upgrade of the popular SAIS suffix array construction algorithm that allows the construction of a suffix array over a collection of strings.

• Ključne riječi: bioinformatika; sufiksno polje; SAIS; gSAIS
• Ključne riječi (engleski): bioinformatics; suffix array; SAIS; gSAIS
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:739644
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-07-13 10:09:38