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 O(nz)-time and O(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 O(nz)-time and 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, Proceedings |
Editors | Lazaros Iliadis, Aristidis Likas, Chrisina Jayne, Giacomo Boracchi |
Publisher | Springer Verlag |
Pages | 620-629 |
Number of pages | 10 |
ISBN (Print) | 9783319651712 |
DOIs | |
Publication status | Published - 1 Jan 2017 |
Externally published | Yes |
Event | 18th International Conference on Engineering Applications of Neural Networks, EANN 2017 - Athens, Greece Duration: 25 Aug 2017 → 27 Aug 2017 |
Publication series
Name | Communications in Computer and Information Science |
---|---|
Volume | 744 |
ISSN (Print) | 1865-0929 |
Conference
Conference | 18th International Conference on Engineering Applications of Neural Networks, EANN 2017 |
---|---|
Country/Territory | Greece |
City | Athens |
Period | 25/08/17 → 27/08/17 |
Funding
M. Alzamel and C.S. Iliopoulos—Partially supported by the Onassis Foundation.
Keywords
- 10.1007/978-3-319-65172-9_52