King's College London

TY - JOUR

T1 - On-line weighted pattern matching

AU - Charalampopoulos, Panagiotis

AU - Iliopoulos, Costas S.

AU - Pissis, Solon P.

AU - Radoszewski, Jakub

PY - 2019/6/1

Y1 - 2019/6/1

N2 - 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 [Formula presented], 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 [Formula presented]. 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.

AB - 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 [Formula presented], 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 [Formula presented]. 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.

KW - On-line pattern matching

KW - Position weight matrix (PWM)

KW - String matching automaton

KW - Uncertain sequence

KW - Weighted sequence

UR - http://www.scopus.com/inward/record.url?scp=85059699088&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2019.01.001

DO - 10.1016/j.ic.2019.01.001

M3 - Article

AN - SCOPUS:85059699088

VL - 266

SP - 49

EP - 59

JO - INFORMATION AND COMPUTATION

JF - INFORMATION AND COMPUTATION

SN - 0890-5401

ER -