Bit-parallel approximate string matching under Hamming distance

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Tarhio, Jorma
dc.contributor.author Hirvola, Tommi
dc.date.accessioned 2016-08-26T09:08:16Z
dc.date.available 2016-08-26T09:08:16Z
dc.date.issued 2016-08-24
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/21625
dc.description.abstract In many situations, an exact search of a pattern in a text does not find all interesting parts of the text. For example, exact matching can be rendered useless by spelling mistakes or other errors in the text or pattern. Approximate string matching addresses the problem by allowing a certain amount of error in occurrences of the pattern in the text. This thesis considers the approximate matching problem known as string matching with k mismatches, in which k characters are allowed to mismatch. The main contribution of the thesis consists of new algorithms for approximate string matching with k mismatches based on the bit-parallelism technique. Experiments show that the proposed algorithms are competitive with the state-of-the-art algorithms in practice. A significant advantage of the novel algorithms is algorithmic simplicity and flexibility, which is demonstrated by deriving efficient algorithms to several problems involving approximate string matching under the k-mismatches model. A bit-parallel algorithm is presented for online approximate matching of circular strings with k mismatches, which is the first average-optimal solution that is not based on filtering. In the experiments, the presented algorithm outperforms earlier filtering methods with orders of magnitude faster search performance, especially for short patterns and large k. Finally, two bit-parallel algorithms are proposed to the longest common substring problem allowing k mismatches. The first algorithm exhibits sublinear behavior on certain strings, but is efficient only for small values of k. The second algorithm is quadratic in the worst case and scales well for large k. The proposed algorithms are faster than previous methods according to experiments on DNA data. en
dc.description.abstract Monissa tilanteissa merkkijonohahmon tarkka haku tekstistä ei löydä kaikkia kiinnostavia tekstin osia. Esimerkiksi kirjoitusvirheet tekstissä tai hahmossa voivat tehdä tarkasta hausta käyttökelvottoman. Likimääräisessä merkkijonohaussa ongelmaan on vastattu sallimalla virheitä hahmon esiintymissä tekstissä. Diplomityö käsittelee likimääräistä merkkijonohakua k:lla epätäsmäyksellä, jossa sallitaan k väärää merkkiä. Työn tärkein kontribuutio muodostuu bittirinnakkaisista algoritmeista likimääräiseen merkkijonohakuun k:lla epätäsmäyksellä. Kokeet osoittavat esitetyt algoritmit kilpailukykyisiksi parhaiden tunnettujen algoritmien kanssa. Esitettyjen algoritmien merkittävä etu on niiden algoritminen yksinkertaisuus ja joustavuus, mikä osoitetaan johtamalla uusia tehokkaita algoritmeja muihin likimääräisen merkkijonohaun ongelmiin k:lla sallitulla epätäsmäyksellä. Työssä kuvaillaan bittirinnakkainen algoritmi sirkulaaristen permutaatioiden eli kehäjonojen hakuun k:lla epätäsmäyksellä. Algoritmi on ensimmäinen seulontaan perustumaton ratkaisu tähän ongelmaan optimaalisessa keskimääräisen tapauksen ajassa. Kokeellisessa osuudessa algoritmi osoittautuu monta kertaluokkaa nopeammaksi kuin aikaisemmat seulontamenetelmät, erityisesti lyhyillä hahmoilla ja suurilla k:n arvoilla. Lopuksi työssä esitetään kaksi bittirinnakkaista algoritmia merkkijonoparin pisimmän yhteisen osajonon etsimiseen k:lla epätäsmäyksellä. Ensimmäinen algoritmi käyttäytyy alilineaarisesti tietyillä syötteillä, mutta on tehokas vain pienillä k:n arvoilla. Toinen algoritmi on neliöllinen pahimmassa tapauksessa sekä skaalautuu suurille k. Esitetyt algoritmit ovat nopeampia kuin aikaisemmat ratkaisut DNA-jonoilla ajettujen kokeiden mukaan. fi
dc.format.extent 87
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title Bit-parallel approximate string matching under Hamming distance en
dc.title Bittirinnakkainen likimääräinen merkkijonohaku epätäsmäyksillä fi
dc.type G2 Pro gradu, diplomityö fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword approximate string matching en
dc.subject.keyword k mismatches en
dc.subject.keyword bit-parallelism en
dc.subject.keyword circular strings en
dc.subject.keyword longest common substring en
dc.identifier.urn URN:NBN:fi:aalto-201608263081
dc.programme.major Ohjelmistotekniikka fi
dc.programme.mcode T3001 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Tarhio, Jorma
dc.programme Tietotekniikan koulutusohjelma fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse