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 proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationEngineering Applications of Neural Networks - 18th International Conference, EANN 2017, Proceedings
EditorsLazaros Iliadis, Aristidis Likas, Chrisina Jayne, Giacomo Boracchi
PublisherSpringer Verlag
Pages620-629
Number of pages10
ISBN (Print)9783319651712
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes
Event18th International Conference on Engineering Applications of Neural Networks, EANN 2017 - Athens, Greece
Duration: 25 Aug 201727 Aug 2017

Publication series

NameCommunications in Computer and Information Science
Volume744
ISSN (Print)1865-0929

Conference

Conference18th International Conference on Engineering Applications of Neural Networks, EANN 2017
Country/TerritoryGreece
CityAthens
Period25/08/1727/08/17

Funding

M. Alzamel and C.S. Iliopoulos—Partially supported by the Onassis Foundation.

Keywords

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

Fingerprint

Dive into the research topics of 'Efficient computation of palindromes in sequences with uncertainties'. Together they form a unique fingerprint.

Cite this