Bit-parallel approximate string matching under Hamming distance
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2016-08-24
Department
Major/Subject
Ohjelmistotekniikka
Mcode
T3001
Degree programme
Tietotekniikan koulutusohjelma
Language
en
Pages
87
Series
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.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.Description
Supervisor
Tarhio, JormaThesis advisor
Tarhio, JormaKeywords
approximate string matching, k mismatches, bit-parallelism, circular strings, longest common substring