Paper Info
Title
On-line weighted pattern matching.
Abstract
A weighted sequence is a sequence of probability distributions over an alphabet of size σ. Weighted sequences arise naturally in many applications. We study the problem of weighted pattern matching in which we are given a string pattern P of length m, a weight threshold 1z, and a weighted text X arriving on-line. We say that P occurs in X at position i if the product of probabilities of the letters of P at positions i−m+1,…,i in X is at least 1z. We first discuss how to apply a known general scheme that transforms off-line pattern matching algorithms to on-line algorithms to obtain an on-line algorithm that requires O((σ+log⁡z)log⁡m) or O(σlog2⁡m) time per arriving position; with the space requirement however being O(mmin⁡(σ,z)). Our main result is a new algorithm that processes each arriving position of X in O(z+σ) time using O(m+z) extra space.
Year
DOI
Venue
2019
10.1016/j.ic.2019.01.001
Information and Computation
Keywords
Field
DocType
Weighted sequence,Position weight matrix (PWM),Uncertain sequence,On-line pattern matching,String matching automaton
Discrete mathematics,Combinatorics,Probability distribution,Pattern matching,Mathematics,Alphabet
Journal
Volume
ISSN
Citations 
266
0890-5401
0
PageRank 
References 
Authors
0.34
16
4
Name
Order
Citations
PageRank
Panagiotis Charalampopoulos1299.41
C. S. Iliopoulos2526.67
Solon P. Pissis328157.09
Jakub Radoszewski462450.36