Efficient computation of palindromes in sequences with uncertainties

Mai Alzamel; Jia Gao; Costas S. Iliopoulos; Chang Liu; Solon P. Pissis

doi:10.1007/978-3-319-65172-9_52

Efficient computation of palindromes in sequences with uncertainties

Mai Alzamel^*, Jia Gao, Costas S. Iliopoulos, Chang Liu, Solon P. Pissis

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

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	https://doi.org/10.1007/978-3-319-65172-9_52
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

Access to Document

10.1007/978-3-319-65172-9_52

Persistent URL (handle)

Persistent link

Cite this

Alzamel, M., Gao, J., Iliopoulos, C. S., Liu, C., & Pissis, S. P. (2017). Efficient computation of palindromes in sequences with uncertainties. In L. Iliadis, A. Likas, C. Jayne, & G. Boracchi (Eds.), Engineering Applications of Neural Networks - 18th International Conference, EANN 2017, Proceedings (pp. 620-629). (Communications in Computer and Information Science; Vol. 744). Springer Verlag. https://doi.org/10.1007/978-3-319-65172-9_52

Alzamel, Mai ; Gao, Jia ; Iliopoulos, Costas S. et al. / Efficient computation of palindromes in sequences with uncertainties. Engineering Applications of Neural Networks - 18th International Conference, EANN 2017, Proceedings. editor / Lazaros Iliadis ; Aristidis Likas ; Chrisina Jayne ; Giacomo Boracchi. Springer Verlag, 2017. pp. 620-629 (Communications in Computer and Information Science).

@inproceedings{e081cb45a53c48ac89cb93681359e3cf,

title = "Efficient computation of palindromes in sequences with uncertainties",

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.",

keywords = "10.1007/978-3-319-65172-9_52",

author = "Mai Alzamel and Jia Gao and Iliopoulos, {Costas S.} and Chang Liu and Pissis, {Solon P.}",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/978-3-319-65172-9_52",

language = "English",

isbn = "9783319651712",

series = "Communications in Computer and Information Science",

publisher = "Springer Verlag",

pages = "620--629",

editor = "Lazaros Iliadis and Aristidis Likas and Chrisina Jayne and Giacomo Boracchi",

booktitle = "Engineering Applications of Neural Networks - 18th International Conference, EANN 2017, Proceedings",

address = "Germany",

note = "18th International Conference on Engineering Applications of Neural Networks, EANN 2017 ; Conference date: 25-08-2017 Through 27-08-2017",

}

Alzamel, M, Gao, J, Iliopoulos, CS, Liu, C & Pissis, SP 2017, Efficient computation of palindromes in sequences with uncertainties. in L Iliadis, A Likas, C Jayne & G Boracchi (eds), Engineering Applications of Neural Networks - 18th International Conference, EANN 2017, Proceedings. Communications in Computer and Information Science, vol. 744, Springer Verlag, pp. 620-629, 18th International Conference on Engineering Applications of Neural Networks, EANN 2017, Athens, Greece, 25/08/17. https://doi.org/10.1007/978-3-319-65172-9_52

Efficient computation of palindromes in sequences with uncertainties. / Alzamel, Mai; Gao, Jia; Iliopoulos, Costas S. et al.
Engineering Applications of Neural Networks - 18th International Conference, EANN 2017, Proceedings. ed. / Lazaros Iliadis; Aristidis Likas; Chrisina Jayne; Giacomo Boracchi. Springer Verlag, 2017. p. 620-629 (Communications in Computer and Information Science; Vol. 744).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

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 -

Alzamel M, Gao J, Iliopoulos CS, Liu C, Pissis SP. Efficient computation of palindromes in sequences with uncertainties. In Iliadis L, Likas A, Jayne C, Boracchi G, editors, Engineering Applications of Neural Networks - 18th International Conference, EANN 2017, Proceedings. Springer Verlag. 2017. p. 620-629. (Communications in Computer and Information Science). doi: 10.1007/978-3-319-65172-9_52

Efficient computation of palindromes in sequences with uncertainties

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this