Byte-Aligned Pattern Matching in Encoded Genomic Sequences

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F17%3A00313052" target="_blank" >RIV/68407700:21240/17:00313052 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.4230/LIPIcs.WABI.2017.20" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.WABI.2017.20</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.WABI.2017.20" target="_blank" >10.4230/LIPIcs.WABI.2017.20</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Byte-Aligned Pattern Matching in Encoded Genomic Sequences

Popis výsledku v původním jazyce

In this article, we propose a novel pattern matching algorithm, called BAPM, that performs searching in the encoded genomic sequences. The algorithm works at the level of single bytes and it achieves sublinear performance on average. The preprocessing phase of the algorithm is linear with respect to the size of the searched pattern $m$. A simple $mathcal{O}(m)$-space data structure is used to store all factors (with a defined length) of the searched pattern. These factors are later searched during the searching phase which ensures sublinear time on average. Our algorithm significantly overcomes the state-of-the-art pattern matching algorithms in the locate time on middle and long patterns. Furthermore, it is able to cooperate very easily with the block $q$-gram inverted index. The block $q$-gram inverted index together with our pattern matching algorithm achieve superior results in terms of locate time to the current index data structures for less frequent patterns. We present experimental results using real genomic data. These results prove efficiency of our algorithm.

Název v anglickém jazyce

Byte-Aligned Pattern Matching in Encoded Genomic Sequences

Popis výsledku anglicky

In this article, we propose a novel pattern matching algorithm, called BAPM, that performs searching in the encoded genomic sequences. The algorithm works at the level of single bytes and it achieves sublinear performance on average. The preprocessing phase of the algorithm is linear with respect to the size of the searched pattern $m$. A simple $mathcal{O}(m)$-space data structure is used to store all factors (with a defined length) of the searched pattern. These factors are later searched during the searching phase which ensures sublinear time on average. Our algorithm significantly overcomes the state-of-the-art pattern matching algorithms in the locate time on middle and long patterns. Furthermore, it is able to cooperate very easily with the block $q$-gram inverted index. The block $q$-gram inverted index together with our pattern matching algorithm achieve superior results in terms of locate time to the current index data structures for less frequent patterns. We present experimental results using real genomic data. These results prove efficiency of our algorithm.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)

ISBN

978-3-95977-050-7

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

13

Strana od-do

"20:1"-"20:13"

Název nakladatele

Dagstuhl Publishing,

Místo vydání

Saarbrücken

Místo konání akce

Boston

Datum konání akce

21. 8. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—