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

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

4 Citations (Scopus)

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	https://doi.org/10.1007/978-3-319-65172-9_52
Publication status	E-pub ahead of print - 2 Aug 2017

Access to Document

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

Cite this

Alzamel, M., Gao, J., Iliopoulos, C. S., Liu, C., & Pissis, S. P. (2017). Efficient Computation of Palindromes in Sequences with Uncertainties. In G. Boracchi, L. Iliadis, C. Jayne, & A. Likas (Eds.), Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings (Vol. 744, pp. 620-629). Springer International Publishing Switzerland. Advance online publication. 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, Athens, Greece, August 25--27, 2017, Proceedings. editor / Giacomo Boracchi ; Lazaros Iliadis ; Chrisina Jayne ; Aristidis Likas. Vol. 744 Cham : Springer International Publishing Switzerland, 2017. pp. 620-629

@inbook{3dd3d839f29740c997c5e86bac917b11,

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

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

year = "2017",

month = aug,

day = "2",

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

language = "English",

isbn = "978-3-319-65171-2",

volume = "744",

pages = "620--629",

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

booktitle = "Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings",

publisher = "Springer International Publishing Switzerland",

}

Alzamel, M , Gao, J , Iliopoulos, CS , Liu, C & Pissis, SP 2017, Efficient Computation of Palindromes in Sequences with Uncertainties. in G Boracchi, L Iliadis, C Jayne & A Likas (eds), Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings. vol. 744, Springer International Publishing Switzerland, Cham, pp. 620-629. 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, Athens, Greece, August 25--27, 2017, Proceedings. ed. / Giacomo Boracchi; Lazaros Iliadis; Chrisina Jayne; Aristidis Likas. Vol. 744 Cham: Springer International Publishing Switzerland, 2017. p. 620-629.

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

TY - CHAP

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/8/2

Y1 - 2017/8/2

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

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

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

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

M3 - Other chapter contribution

SN - 978-3-319-65171-2

VL - 744

SP - 620

EP - 629

BT - Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings

A2 - Boracchi, Giacomo

A2 - Iliadis, Lazaros

A2 - Jayne, Chrisina

A2 - Likas, Aristidis

PB - Springer International Publishing Switzerland

CY - Cham

ER -

Alzamel M , Gao J , Iliopoulos CS , Liu C , Pissis SP. Efficient Computation of Palindromes in Sequences with Uncertainties. In Boracchi G, Iliadis L, Jayne C, Likas A, editors, Engineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings. Vol. 744. Cham: Springer International Publishing Switzerland. 2017. p. 620-629 Epub 2017 Aug 2. doi: 10.1007/978-3-319-65172-9_52

Efficient Computation of Palindromes in Sequences with Uncertainties

Abstract

Access to Document

Fingerprint

Cite this