TY - GEN
T1 - Efficient computation of palindromes in sequences with uncertainties
AU - Alzamel, Mai
AU - Gao, Jia
AU - Iliopoulos, Costas S.
AU - Liu, Chang
AU - Pissis, Solon P.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - 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.
AB - 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.
KW - 10.1007/978-3-319-65172-9_52
UR - http://www.scopus.com/inward/record.url?scp=85028325142&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028325142&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-65172-9_52
DO - 10.1007/978-3-319-65172-9_52
M3 - Conference contribution
AN - SCOPUS:85028325142
SN - 9783319651712
T3 - Communications in Computer and Information Science
SP - 620
EP - 629
BT - Engineering Applications of Neural Networks - 18th International Conference, EANN 2017, Proceedings
A2 - Iliadis, Lazaros
A2 - Likas, Aristidis
A2 - Jayne, Chrisina
A2 - Boracchi, Giacomo
PB - Springer Verlag
T2 - 18th International Conference on Engineering Applications of Neural Networks, EANN 2017
Y2 - 25 August 2017 through 27 August 2017
ER -