Poboljšano sufiksno polje

završni rad

• Naslov (engleski): Enhanced suffix array
• Autor: Antea Hadviger
• Mentor: Mile Šikić (mentor)
• Član povjerenstva: Mile Šikić (predsjednik povjerenstva)
• Član povjerenstva: Andrej Novak (član povjerenstva)
• Član povjerenstva: Krešimir Križanović (č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: 2015-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U bioinformatici često se javlja problem pretraživanja veoma dugačkih nizova (DNA sljedova) s različitim uzorcima pretrage. Kako bi se problem riješio u razumnom vremenu, potrebno je koristiti efikasne strukture indeksiranja teksta, kao što su sufiksno stablo i poboljšano sufiksno polje. Poboljšano sufiksno polje sastoji se od običnog sufiksnog polja i dodatnih struktura (polje najduljih zajedničkih prefiksa, tablica djece). Uz manje memorijsko zauzeće, jednostavniju implementaciju i linearno vrijeme izgradnje, koristeći algoritme kao što je SA-IS, u praksi nadmašuje sufiksno stablo zadržavajući svu kompleksnu funkcionalnost.

Sažetak (engleski)

Bioinformatics problems often require pattern matching large texts (DNA sequences) with different patterns. To find a solution to these problems in a reasonable time, it is required to use efficient text indexing structures, like suffix tree or enhanced suffix array. It is made of a regular suffix array and enhanced with several additional structures (longest common prefix array, child table). With less memory consumption, simpler implementation and linear construction complexity, using SA-IS algorithm, it shows better results in practice than suffix trees while keeping all the complex functionality.

• Ključne riječi: bioinformatika; poboljšano sufiksno polje; SA-IS
• Ključne riječi (engleski): bioinformatics; enhanced suffix array; SA-IS
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:819303
• 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: 2018-02-06 09:07:25