License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2017.20
URN: urn:nbn:de:0030-drops-76538
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7653/
Go to the corresponding LIPIcs Volume Portal

Procházka, Petr ; Holub, Jan

Byte-Aligned Pattern Matching in Encoded Genomic Sequences

pdf-format:
LIPIcs-WABI-2017-20.pdf (0.6 MB)

Abstract

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

BibTeX - Entry

@InProceedings{prochzka_et_al:LIPIcs:2017:7653,
  author =	{Petr Proch{\'a}zka and Jan Holub},
  title =	{{Byte-Aligned Pattern Matching in Encoded Genomic Sequences}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Russell Schwartz and Knut Reinert},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7653},
  URN =		{urn:nbn:de:0030-drops-76538},
  doi =		{10.4230/LIPIcs.WABI.2017.20},
  annote =	{Keywords: genomic sequences, pattern matching, q-gram inverted index}
}

Keywords: genomic sequences, pattern matching, q-gram inverted index
Collection: 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)
Issue Date: 2017
Date of publication: 11.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI