Name
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 it 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-65172-9_52 | Communications in Computer and Information Science |
DocType | Volume | Issue |
Journal | 744 | 3 |
ISSN | Citations | PageRank |
1865-0929 | 0 | 0.34 |
References | Authors | |
8 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mai Abdulaziz Alzamel | 1 | 14 | 6.02 |
| Jia Gao | 2 | 11 | 2.26 |
| Costas S. Iliopoulos | 3 | 0 | 1.35 |
| Chang Liu | 4 | 571 | 117.41 |
| Solon P. Pissis | 5 | 281 | 57.09 |