Julkaisu arvostetussa STOC-konferenssissa 2014
Laitoksella postdoc-tutkijana toimivan Djamal Belazzouguin tutkimus hyväksyttiin julkaistavaksi arvostetussa ACM Symposium on the Theory of Computing (STOC) -konferenssissa. Tutkimus sisältää optimaaliset tilatiiviit satunnaisalgoritmit tiivistetyn loppuosataulukon sekä tiivistetyn loppuosapuun muodostamiseen. Tilatiivis muodostamisalgoritmi käyttää muistia vain samaa suuruusluokkaa kuin syöte sekä tuloste; tässä yhteydessä myös tuloste (tiivis tietorakenne) käyttää samaa suuruusluokkaa tilaa kuin syöte (merkkijono).
Tutkimuksella on useita sovelluskohteita. Uusia algoritmeja voidaan käyttää muun muassa ESA 2013 konferenssissa esiteltyjen kaksisuuntaiseen Burrows-Wheeler muunnokseen perustuvien indeksien muodostamiseen, ja sitä kautta ratkaisemaan sekvenssijoukkojen analyysiin liittyviä ongelmia, kuten kahden sekvenssin maksimaalisten uniikkien ja yhteisten osajonojen etsintä (engl. maximal unique matches, MUMs). Monet suositut vertailevan genomiikan ohjelmistot käyttävät MUMs ongelman ratkaisua ankkureina genomien laajuisten linjausten muodostamiseen.
Laitoksella työskentelee parhaillaan ryhmä opiskelijoita yllä mainittujen sekvenssianalyysi-algoritmien toteutuksen parissa kevään 2014 ohjelmistotuotantoprojektissa.
Artikkelin käsikirjoitus on luettavissa ArXiv-kokoelmassa.