Efficient Computation of Palindromes in Sequences with Uncertainties *

Abstract

In this work, we consider a special type of uncertain sequence called weighted string. In a weighted string every position contains a subset of the alphabet and every letter of the alphabet is associated with a probability of occurrence such that the sum of probabilities at each position equals 1. Usually a cumulative weight threshold 1/z is specified, and one considers only strings that match the weighted string with probability at least 1/z. We provide an 𝒪(nz)-time and 𝒪(nz)-space off-line algorithm, where n is the length of the weighted string and 1/z is the given threshold, to compute a smallest maximal palindromic factorization of a weighted string. This factorization has applications in hairpin structure prediction in a set of closely-related DNA or RNA sequences. Along the way, we provide an 𝒪(nz)-time and 𝒪(nz)-space off-line algorithm to compute maximal palindromes in weighted strings. Finally, we provide an experiment of our proposed algorithm.