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.ISAAC.2016.46
URN: urn:nbn:de:0030-drops-68166
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6816/
Go to the corresponding LIPIcs Volume Portal

Kociumaka, Tomasz ; Pissis, Solon P. ; Radoszewski, Jakub

Pattern Matching and Consensus Problems on Weighted Sequences and Profiles

pdf-format:
LIPIcs-ISAAC-2016-46.pdf (0.5 MB)

Abstract

We study pattern matching problems on two major representations of uncertain sequences used in molecular biology: weighted sequences (also known as position weight matrices, PWM) and profiles (i.e., scoring matrices). In the simple version, in which only the pattern or only the text is uncertain, we obtain efficient algorithms with theoretically-provable running times using a variation of the lookahead scoring technique. We also consider a general variant of the pattern matching problems in which both the pattern and the text are uncertain. Central to our solution is a special case where the sequences have equal length, called the consensus problem. We propose algorithms for the consensus problem parameterized by the number of strings that match one of the sequences. As our basic approach, a careful adaptation of the classic meet-in-the-middle algorithm for the knapsack problem is used. On the lower bound side, we prove that our dependence on the parameter is optimal up to lower-order terms conditioned on the optimality of the original algorithm for the knapsack problem.

BibTeX - Entry

@InProceedings{kociumaka_et_al:LIPIcs:2016:6816,
  author =	{Tomasz Kociumaka and Solon P. Pissis and Jakub Radoszewski},
  title =	{{Pattern Matching and Consensus Problems on Weighted Sequences and Profiles}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{46:1--46:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6816},
  URN =		{urn:nbn:de:0030-drops-68166},
  doi =		{10.4230/LIPIcs.ISAAC.2016.46},
  annote =	{Keywords: weighted sequence, position weight matrix, profile matching}
}

Keywords: weighted sequence, position weight matrix, profile matching
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

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