King's College London

Research portal

Efficient Computation of Palindromes in Sequences with Uncertainties

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

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
E-pub ahead of print2 Aug 2017

King's Authors


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.

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454