Affiliations: Department of Informatics, King’s College London, UK. {mai.alzamel, jia.gao, csi, chang.2.liu}@kcl.ac.uk
Correspondence:
[]
Address for correspondence: Department of Informatics, King’s College London, Bush House, Strand Campus, 30 Aldwych, London WC2B 4BG, UK
Note: [*] A preliminary version of this article (with Solon P. Pissis as a co-author) has appeared in [1].
Note: [†] Partially supported by the Onassis Foundation and fully supported by Saudi Ministry of Education.
Note: [‡] Also works: Department of Computer Science, King Saud University, Riyadh, SA.
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.
