A weighted string over an alphabet of size σ is a string in which a set of letters may occur at each position with respective occur- rence probabilities. Weighted strings, also known as position weight ma- trices or uncertain sequences, naturally arise in many contexts. In this ar- ticle, we study the problem of weighted string matching with a special fo- cus on average-case analysis. Given a weighted pattern string x of length m, a text string y of length n > m, and a cumulative weight threshold 1/z, defined as the minimal probability of occurrence of factors in a weighted string, we present an algorithm requiring average-case search time o(n) for pattern matching for weight ratio z m   m, and a cumulative weight threshold 1/z, we present an algorithm requiring average-case search time o(σn) for the same weight ratio. The importance of these results lies on the fact that these algorithms work in average-case sublinear search time in the size of the text, and in linear preprocessing time and space in the size of the pattern, for these ratios.
['Carl Barton', 'Chang Liu', 'Solon P. Pissis']
Fast Average-Case Pattern Matching on Weighted Sequences