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 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 language | English |
|---|---|
| Title of host publication | Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings |
| Editors | Giacomo Boracchi, Lazaros Iliadis, Chrisina Jayne, Aristidis Likas |
| Place of Publication | Cham |
| Publisher | Springer International Publishing Switzerland |
| Pages | 620-629 |
| Number of pages | 10 |
| Volume | 744 |
| ISBN (Electronic) | 978-3-319-65172-9 |
| ISBN (Print) | 978-3-319-65171-2 |
| DOIs | |
| Publication status | E-pub ahead of print - 2 Aug 2017 |