Piiratud võimsusega regulaaravaldistele sobituvate sõnade loendamine
Nimi
Anti Alman
Kokkuvõte
Käesolev bakalaureusetöö keskendub ühe algoritmi arendamisele ja implementeerimisele. See algoritm moodustab ühe osa suuremast biomarkerite otsimise töövoost. Töövoogu arendatakse Tartu Ülikooli BIIT grupis ühe koostööprojekti raames. Algoritmi sisendiks on suur kogus andmeid erinevate bioloogiliste proovide kohta.
Andmed nende proovide kohta on esitatud kasutades lühikesi sõnu ja vastavaid esinemise sagedusi, mille kaudu on võimalik tuvastada olulisi erinevuseid proovide vahel. Lisaks on teada, et mõningatel juhtudel võib piiratud võimsusega regulaaravaldis anda palju paremat infot proovide erinevuste kohta. Samas regulaaravaldistele vastavad sagedused ei ole ette teada vaid tuleb arvutada sisendiks proove iseloomustavate sõnade ja vastavate sageduste põhjal.
Selle probleemi saab jagada kaheks osaks. Esiteks tuleb leida kõik sõnad mis vastavad ette antud regulaaravaldisele. Selle saavutamiseks kasutame suuri bitivektoreid, mida hoitakse pidevalt mälus. Teiseks tuleb arvutada regulaaravaldise sagedused regulaaravaldisele vastavate sõnade sageduste põhjal. Kiirus on siinkohal saavutatud hõreda maatrikis pidevalt mälus hoidmisega. Maatriksile vastava andmestruktuuri formaat on valitud selliselt, et maatriksi ridu saaks võimalikult kiirelt proovide veergude kaupa kokku liita.
Bakalaureusetöö tulemuseks olev algoritm on implementeeritud programeerimiskeeltes Python ja C++. Töös on toodud mõlema implementatsiooni detailid ning lõpuks on võrreldud nende kiirust sama ülesande lahendamiseks arendatud naiivse lahendusega.
Lõputöö keel
eesti
Lõputöö tüüp
Bakalaureus - Infotehnoloogia
Juhendaja(d)
Meelis Kull, Sven Laur
Kaitsmise aasta
2013