Byte-Aligned Pattern Matching in Encoded Genomic Sequences

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Byte-Aligned Pattern Matching in Encoded Genomic Sequences

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2017

Confidentiality

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

Article name in the collection

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

ISBN

978-3-95977-050-7

ISSN

1868-8969

e-ISSN

—

Number of pages

13

Pages from-to

"20:1"-"20:13"

Publisher name

Dagstuhl Publishing,

Place of publication

Saarbrücken

Event location

Boston

Event date

Aug 21, 2017

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—