Prefix-Free Parsing (PFP) enables efficient indexing of repetitive text collections through dictionary-based storage of distinct factors and the corresponding factor positions in the text. The parsing method of PFP differs from LZ78 compression as it separates factors at occurrences of predefined trigger strings, ensuring that the parse is prefix-free. This prefix-free property of PFP makes it suitable for compressed indexing applications such as the construction of the Burrows-Wheeler Transform. Recent work has also introduced a recursive PFP technique, in which the parse of the initial PFP is further compressed with an additional round of prefix-free parsing. In this paper, we provide a theoretical analysis of the minimal size of any prefix-free parse. We show that for a PFP of a string of length$n$, the sum of the lengths of the parse string and the number of nodes in the trie of dictionary strings must be at least$2 \sqrt{n}$. We generalize this result by demonstrating that if prefix-free parsing is applied recursively$k$times, the combined size of the dictionary tries at each level and the final parse must be at least$(k+1) \cdot n^{1 /(k+1)}$. We also provide a family of strings and corresponding trigger strings that achieve this lower bound, demonstrating its tightness and a polynomially large separation between PFP and several other popular compressibility measures. Finally, we illustrate that optimal PFP - that is, with optimal trigger string selection - is robust against one-bit catastrophes for some strings where LZ78 is not. This demonstrates that the optimal PFP size cannot be guaranteed to be within a multiplicative ratio polynomially smaller than$n^{1 / 8}$relative to the LZ78 size.

Time series data can often be represented as a string T[1..n] over an integer alphabet Σ. A standard approach for indexing such strings is the compressed suffix tree, which supports efficient exact pattern matching using 𝒪(n log |Σ|) bits of space. However, when |Σ| is close to n, as is often the case for time-series data, this yields little to no space savings over the classical Θ(n log n)-bit suffix tree. In this work, we study a different parameter that is often much smaller than |Σ|: the maximum absolute difference between consecutive values in T, denoted by Δ. Although representing T in 𝒪(n log Δ) bits is straightforward, supporting efficient pattern matching within this space bound remains challenging. By leveraging succinct data structure techniques, particularly the FM-index, we obtain a compressed index occupying n log Δ + 𝒪(n) bits. Given a query pattern P[1..m], the index answers counting queries in 𝒪(m log Δ) time and reporting queries in 𝒪(m log Δ + occ ⋅ log n ⋅ log Δ) time, where occ denotes the number of occurrences of P in T. In addition, the structure supports suffix array and inverse suffix array queries in 𝒪(log n ⋅ log Δ) time. Our construction is conceptually simple. We show that the local-difference bound induces a strong form of locality in the Burrows-Wheeler Transform (BWT), allowing the transformed text to be decomposed into regions that each use only a small local alphabet of size 𝒪(Δ). This makes it possible to adapt the classical FM-index so that its space usage depends on Δ rather than the overall alphabet size, while still supporting efficient pattern matching queries.

Representing genetic variations among a population of individuals in the form of a genome graph, and using the graph as a reference instead of the genome of a single individual, are central techniques in the fast-emerging area of pangenomics. A fundamental problem in pangenomics is to align a DNA sequence simultaneously against all reference genomes through sequence-to-graph alignment. The sequential approach to the problem uses dynamic programming and takes$O(m\vert E\vert)$time, where$m$is the length of the DNA sequence that is aligned and$\vert E\vert$is the number of edges in the genome graph. In this paper, we present ParSGA, the first parallel algorithm for the sequence-to-graph alignment problem. Prior works on parallelization only addressed the embarrassingly parallel problem of mapping numerous DNA sequences independently, but each sequentially, to the genome graph. In contrast, ParSGA aligns a single sequence in parallel, which is required in cases involving long or ultra-long DNA sequences, or in applications involving successively mapping and incorporating DNA sequences into an evolving graph, or to improve available parallelism for multiple sequence-to-graph alignments even further. ParSGA is work-optimal, and its design provides a high degree of parallelism. On a 128 -core AMD Epyc processor, ParSGA achieves$81 \times$speedup compared to serial execution of itself, and$43 \times$speedup compared to the sequential algorithm, when aligning 250bp reads to human Chromosome 1 variation graph. In the popularly used billion cell updates per second (GCUPS) metric, ParSGA achieves 6.14 GCUPS. The C++ implementation of ParSGA is available at https://github.com/ParBLiSS/ParSGA.

Error correction of long reads is an important initial step in genome assembly workflows. For organisms with ploidy greater than one, it is important to preserve haplotype-specific variation during read correction. This challenge has driven the development of several haplotype-aware correction methods. However, existing methods are based on either ad-hoc heuristics or deep learning approaches. In this paper, we introduce a rigorous formulation for this problem. Our approach builds on the minimum error correction framework used in reference-based haplotype phasing. We prove that the proposed formulation for error correction of reads in de novo context, i.e., without using a reference genome, is NP-hard. To make our exact algorithm scale to large datasets, we introduce practical heuristics. Experiments using PacBio HiFi sequencing datasets from human and plant genomes show that our approach achieves accuracy comparable to state-of-the-art methods. The software is freely available at https://github.com/at-cg/HALE.

Measuring sequence similarity and compressing texts are among the most fundamental tasks in string algorithms. In this work, we develop near-optimal quantum algorithms for the central problems in these two areas: computing the edit distance of two strings [Levenshtein, 1965] and building the Lempel-Ziv factorization of a string [Ziv & Lempel, 1977], respectively.

We revisit the Contextual Pattern Matching Problem, defined as follows: preprocess a text T[1, n], so that given a query consisting of a string P and a length P, the occurrences of all distinct strings XPY where |X|=|Y|=P can be reported. This problem was introduced by Navarro, who presented an O($\overline{r}\log(n/\overline{r}))$ space data structure, where $\overline{r}$ is the maximum of the number of runs in the BWT of the text $\mathrm{T}[1,n]$ and its reverse. His solution reports all c contextual occurrences in $O(|P|+c\log n)$ time. However, the only known bounds on $\overline{r}$ are $\overline{r}=O(r\log^{2}n)$ where r is the number of runs in the BWT of T, making it desirable to avoid using structures with space dependent on $\overline{r}$. We demonstrate that this is possible without a significant sacrifice in query time by providing an $O(r\log(n/r))$ space solution that answers queries in $O(|P|+c\log P\cdot\log(n/r))$ time.

Decomposing a network flow into weighted paths has numerous applications. Some applications require any decomposition that is optimal w.r.t. some property such as number of paths, robustness, or length. Many bioinformatic applications require a specific decomposition where the paths correspond to some underlying data that generated the flow. For real inputs, no optimization criteria guarantees to uniquely identify the correct decomposition. Therefore, we propose to report safe paths, i.e., subpaths of at least one path in every flow decomposition. Ma, Zheng, and Kingsford [WABI 2020] addressed the existence of multiple optimal solutions in a probabilistic framework, i.e., non-identifiability. Later [RECOMB 2021], they gave a quadratic-time algorithm based on a global criterion for solving a problem called AND-Quant, which generalizes the problem of reporting whether a given path is safe. We give the first local characterization of safe paths for flow decompositions in directed acyclic graphs (DAGs), leading to a practical algorithm for finding the complete set of safe paths. We evaluated our algorithms against the trivial safe algorithms (unitigs, extended unitigs) and the popularly used heuristic (greedy-width) for flow decomposition on RNA transcripts datasets. Despite maintaining perfect precision our algorithm reports significantly higher coverage ($\approx 50\%$ more) than trivial safe algorithms. The greedy-width algorithm though reporting a better coverage, has significantly lower precision on complex graphs. Overall, our algorithm outperforms (by $\approx 20\%$) greedy-width on a unified metric (F-Score) when the dataset has significant number of complex graphs. Moreover, it has superior time ($3-5\times$) and space efficiency ($1.2-2.2\times$), resulting in a better and more practical approach for bioinformatics applications of flow decomposition.

Given a text T[1,n] over an alphabet Σ of size σ, the suffix array of T stores the lexicographic order of the suffixes of T. The suffix array needs Θ(nlog n) bits of space compared to the n log σ bits needed to store T itself. A major breakthrough [FM - Index, FOCS'00] in the last two decades has been encoding the suffix array in near-optimal number of bits (≈ log σ bits per character). One can decode a suffix array value using the FM-Index in log^{O(1)} n time. We study an extension of the problem in which we have to also decode the suffix array values of the reverse text. This problem has numerous applications such as in approximate pattern matching [Lam et al., BIBM' 09]. Known approaches maintain the FM - Index of both the forward and the reverse text which drives up the space occupancy to 2nlog σ bits (plus lower order terms). This brings in the natural question of whether we can decode the suffix array values of both the forward and the reverse text, but by using nlog σ bits (plus lower order terms). We answer this question positively, and show that given the FM - Index of the forward text, we can decode the suffix array value of the reverse text in near logarithmic average time. Additionally, our experimental results are competitive when compared to the standard approach of maintaining the FM - Index for both the forward and the reverse text. We believe that applications that require both the forward and reverse text will benefit from our approach.

The Burrows-Wheeler Transform (BWT) has been an essential tool in text compression and indexing. First introduced in 1994, it went on to provide the backbone for the first encoding of the classic suffix tree data structure in space close to the entropy-based lower bound. Recently, there has been the development of compact suffix trees in space proportional to "$r$", the number of runs in the BWT, as well as the appearance of $r$ in the time complexity of new algorithms. Unlike other popular measures of compression, the parameter $r$ is sensitive to the lexicographic ordering given to the text's alphabet. Despite several past attempts to exploit this, a provably efficient algorithm for finding, or approximating, an alphabet ordering which minimizes $r$ has been open for years. We present the first set of results on the computational complexity of minimizing BWT-runs via alphabet reordering. We prove that the decision version of this problem is NP-complete and cannot be solved in time $2^{o(σ+ \sqrt{n})}$ unless the Exponential Time Hypothesis fails, where $σ$ is the size of the alphabet and $n$ is the length of the text. We also show that the optimization problem is APX-hard. In doing so, we relate two previously disparate topics: the optimal traveling salesperson path and the number of runs in the BWT of a text, providing a surprising connection between problems on graphs and text compression. Also, by relating recent results in the field of dictionary compression, we illustrate that an arbitrary alphabet ordering provides a $O(\log^2 n)$-approximation. We provide an optimal linear-time algorithm for the problem of finding a run minimizing ordering on a subset of symbols (occurring only once) under ordering constraints, and prove a generalization of this problem to a class of graphs with BWT like properties called Wheeler graphs is NP-complete.

We present the first fine-grained complexity results on two classic problems on strings. The first one is the k-Median-Edit-Distance problem, where the input is a collection of k strings, each of length at most n, and the task is to find a new string that minimizes the sum of the edit distances from itself to all other strings in the input. Arising frequently in computational biology, this problem provides an important generalization of edit distance to multiple strings and is similar to the multiple sequence alignment problem in bioinformatics. We demonstrate that for any ε > 0 and k ≥ 2, an O(n^{k-ε}) time solution for the k-Median-Edit-Distance problem over an alphabet of size O(k) refutes the Strong Exponential Time Hypothesis (SETH). This provides the first matching conditional lower bound for the O(n^k) time algorithm established in 1975 by Sankoff. The second problem we study is the k-Center-Edit-Distance problem. Here also, the input is a collection of k strings, each of length at most n. The task is to find a new string that minimizes the maximum edit distance from itself to any other string in the input. We prove that the same conditional lower bound as before holds. Our results also imply new conditional lower bounds for the k-Tree-Alignment and the k-Bottleneck-Tree-Alignment problems studied in phylogenetics.

In recent years several compressed indexes based on variants of the Burrows-Wheeler transformation have been introduced. Some of these are used to index structures far more complex than a single string, as was originally done with the FM-index [Ferragina and Manzini, J. ACM 2005]. As such, there has been an increasing effort to better understand under which conditions such an indexing scheme is possible. This has led to the introduction of Wheeler graphs [Gagie et al., Theor. Comput. Sci., 2017]. Gagie et al. showed that de Bruijn graphs, generalized compressed suffix arrays, and several other BWT related structures can be represented as Wheeler graphs, and that Wheeler graphs can be indexed in a way which is space efficient. Hence, being able to recognize whether a given graph is a Wheeler graph, or being able to approximate a given graph by a Wheeler graph, could have numerous applications in indexing. Here we resolve the open question of whether there exists an efficient algorithm for recognizing if a given graph is a Wheeler graph. We present: - The problem of recognizing whether a given graph G=(V,E) is a Wheeler graph is NP-complete for any edge label alphabet of size sigma >= 2, even when G is a DAG. This holds even on a restricted, subset of graphs called d-NFA’s for d >= 5. This is in contrast to recent results demonstrating the problem can be solved in polynomial time for d-NFA’s where d <= 2. We also show the recognition problem can be solved in linear time for sigma =1; - There exists an 2^{e log sigma + O(n + e)} time exact algorithm where n = |V| and e = |E|. This algorithm relies on graph isomorphism being computable in strictly sub-exponential time; - We define an optimization variant of the problem called Wheeler Graph Violation, abbreviated WGV, where the aim is to remove the minimum number of edges in order to obtain a Wheeler graph. We show WGV is APX-hard, even when G is a DAG, implying there exists a constant C >= 1 for which there is no C-approximation algorithm (unless P = NP). Also, conditioned on the Unique Games Conjecture, for all C >= 1, it is NP-hard to find a C-approximation; - We define the Wheeler Subgraph problem, abbreviated WS, where the aim is to find the largest subgraph which is a Wheeler Graph (the dual of the WGV). In contrast to WGV, we prove that the WS problem is in APX for sigma=O(1); The above findings suggest that most problems under this theme are computationally difficult. However, we identify a class of graphs for which the recognition problem is polynomial time solvable, raising the open question of which parameters determine this problem’s difficulty.