Name
Abstract | ||
|---|---|---|
A weighted string, also known as a position weight matrix, is a sequence of probability distributions over some alphabet. We revisit the Weighted Shortest Common Supersequence (WSCS) problem, introduced by Amir et al. [SPIRE 2011], that is, the SCS problem on weighted strings. In the WSCS problem, we are given two weighted strings $W_1$ and $W_2$ and a threshold $\mathit{Freq}$ on probability, and we are asked to compute the shortest (standard) string $S$ such that both $W_1$ and $W_2$ match subsequences of $S$ (not necessarily the same) with probability at least $\mathit{Freq}$. Amir et al. showed that this problem is NP-complete if the probabilities, including the threshold $\mathit{Freq}$, are represented by their logarithms (encoded in binary). We present an algorithm that solves the WSCS problem for two weighted strings of length $n$ over a constant-sized alphabet in $\mathcal{O}(n^2\sqrt{z} \log{z})$ time. Notably, our upper bound matches known conditional lower bounds stating that the WSCS problem cannot be solved in $\mathcal{O}(n^{2-\varepsilon})$ time or in $\mathcal{O}^*(z^{0.5-\varepsilon})$ time unless there is a breakthrough improving upon long-standing upper bounds for fundamental NP-hard problems (CNF-SAT and Subset Sum, respectively). We also discover a fundamental difference between the WSCS problem and the Weighted Longest Common Subsequence (WLCS) problem, introduced by Amir et al. [JDA 2010]. We show that the WLCS problem cannot be solved in $\mathcal{O}(n^{f(z)})$ time, for any function $f(z)$, unless $\mathrm{P}=\mathrm{NP}$. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-32686-9_16 | SPIRE |
Field | DocType | Citations |
Shortest common supersequence,Combinatorics,Computer science,Probability distribution,Logarithm,Binary number,Alphabet | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panagiotis Charalampopoulos | 1 | 3 | 4.12 |
| Tomasz Kociumaka | 2 | 217 | 38.57 |
| Solon P. Pissis | 3 | 281 | 57.09 |
| Jakub Radoszewski | 4 | 624 | 50.36 |
| Wojciech Rytter | 5 | 2290 | 181.52 |
| Juliusz Straszynski | 6 | 2 | 5.15 |
| Tomasz Walen | 7 | 22 | 5.41 |
| Wiktor Zuba | 8 | 1 | 5.13 |