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 -