Efficient Computation of Palindromes in Sequences with Uncertainties

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review

4 Citations (Scopus)


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 thresholdOpen image in new window is specified, and one considers only strings that match the weighted string with probability at least Open image in new window. We provide an O(nz)O(nz) -time and O(nz)O(nz) -space off-line algorithm, where n is the length of the weighted string and Open image in new window 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 O(nz)O(nz) -time and O(nz)O(nz) -space off-line algorithm to compute maximal palindromes in weighted strings.
Original languageEnglish
Title of host publicationEngineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings
EditorsGiacomo Boracchi, Lazaros Iliadis, Chrisina Jayne, Aristidis Likas
Place of PublicationCham
PublisherSpringer International Publishing Switzerland
Number of pages10
ISBN (Electronic)978-3-319-65172-9
ISBN (Print)978-3-319-65171-2
Publication statusE-pub ahead of print - 2 Aug 2017


Dive into the research topics of 'Efficient Computation of Palindromes in Sequences with Uncertainties'. Together they form a unique fingerprint.

Cite this