Building genomic data structures from compressed representations using prefix-free parsing

Basic definitions

In this paper, we use 0-based indexing for all strings and arrays. The := symbol denotes an assignment or update operation, the = symbol represents mathematical equality or definition, and the · · · symbol indicates a range of values. Let T = T[0 · · · n − 1] = T[0] · · · T[n − 1] be a finite string over an alphabet Σ of size σ whose symbols can be unambiguously ordered. The symbol T[i] denotes the character at index i of T, and T[i · · · j] denotes the substring T[i] · · · T[j] if 0 ≤ i ≤ j < n or the empty string ϵ otherwise. For 0 ≤ i < n, the substring T[0 · · · i] is the (i + 1)th prefix of T, and T[i · · · n − 1] is the (n − i)th suffix of T. A prefix T[0 · · · i] is a proper prefix if 0 ≤ i < n − 1, whereas a suffix T[i · · · n − 1] is a proper suffix if 0 < i ≤ n − 1. If T₂[0 · · · m − 1] is lexicographically smaller than T₁[0 · · · n − 1], then either T₂ is a proper prefix of T₁, or there exists an index $0\le i<min(n,m)$ such that T₂[0 · · · i − 1] = T₁[0 · · · i − 1] and T₂[i] < T₁[i]. Let ${\mathrm{rank}}_c(T,i)$ be a function that returns the number of times c appears in T[0 · · · i − 1], where c ∈ Σ. Let ${\mathrm{RMQ}}_A(i,j)$ denote a range minimum query (RMQ) that returns the minimum value in the subarray A[i · · · j], for 0 ≤ i ≤ j < |A|, where |A| is the size of A.

The concept of prefix-free is crucial for understanding how the output of prefix-free parsing can be used to build other data structures, so a formal definition is provided.

For example, the multiset $\mathcal{S}=\{\mathtt{A}\mathtt{C}\mathtt{C}\mathtt{A}\mathtt{,}\mathtt{G}\mathtt{C}\mathtt{C}\mathtt{,}\mathtt{A}\mathtt{C}\mathtt{C}\mathtt{A}\mathtt{,}\mathtt{T}\mathtt{C}\mathtt{C}\mathtt{A}\mathtt{G}\}$ is a prefix-free multiset because no string $s\in \mathcal{S}$ is a proper prefix of any other string $s^{\mathrm{\prime }}\in \mathcal{S}$, as the first character of all unique strings is lexicographically different.

Prefix-free parsing

Prefix-free parsing (PFP) is a lossless preprocessing compression algorithm designed for large, repetitive texts such as genomic data sets (Boucher et al. 2019). It achieves effective compression by decomposing the text into variable-length overlapping phrases that often occur. The main advantage of the algorithm is that it enables the scalable construction of other data structures from its compressed output. To understand how the algorithm works in practice, we now turn to its details.

PFP(T, w, p) takes as input a text T of length n and two user-defined integers greater than 1, denoted w and p. It first transforms T into T′ where $T^{\mathrm{\prime }}:=\mathrm{\$}T{\mathrm{\#}}^w$ by prepending a $ and appending w consecutive copies of #. Both symbols are arbitrary, provided that they are lexicographically smaller than every symbol in Σ. A rolling hash is then computed over all consecutive w-length substrings of T′ in a single pass by sliding a window of length w and hashing each window. Any hash function may be used, provided collisions are rare; in practice, a Karp-Rabin hash (Karp and Rabin 1987) is preferred, as it allows for efficient updates between adjacent windows. This hash is denoted as $H_p\left(t_w\right)=H\left(t_w\right)modp$, where H is the hash function, p is the modulus, and t_w is the current substring within the window. Substrings whose hash value is zero are referred to as trigger strings. The following definition succinctly summarizes the set of w-length substrings that yield trigger strings.

Trigger strings identified by the algorithm mark phrase boundaries. As the algorithm scans T′, each trigger string signals the end of a phrase (besides the starting $). Each phrase begins at the start of the previous trigger string and ends at the end of the current one; it cannot span any other trigger string. The prepended $ and appended ${\mathrm{\#}}^w$ characters are always treated as trigger strings, ensuring that the first and last phrase begin and end with a trigger string.

PFP(T, w, p) outputs a dictionary $D_T$ and parse $P_T$. The dictionary stores only the unique phrases encountered, while the parse records the order that those phrases occur in the text. During parsing, when a trigger string is identified, the algorithm adds the newly terminated phrase to $D_T$ if it is not already present, but always appends a reference to the corresponding dictionary entry to $P_T$. After parsing, PFP lexicographically sorts the phrases in $D_T$ and updates the references in $P_T$ with the corresponding dictionary integer ranks before writing the files to disk. The combined output size depends on the repetitiveness of the text and the selection of w and p. Lucà et al. (2025) extensively tested PFP with various configurations of w and p on different biological data sets and found that, for most data sets, fixing w while increasing p leads to decreased output size, reaching a minimum when p = 50 or p = 100. Beyond that, they observed a slight increase in output size, likely due to longer dictionary phrases caused by fewer observed trigger strings. Reconstructing T from $D_T$ and $P_T$ is straightforward. The $D_T$ phrases need to be appended in the order specified by $P_T$, trimming the last w characters of each phrase to account for the overlap.

The name of the algorithm, prefix-free parsing, stems from the observation that all dictionary phrase suffixes longer than w are prefix-free with respect to one another (see Definition 1). This is formalized in Lemma 3, which we now prove. Let S be the multiset of all dictionary phrase suffixes that are longer than w. Each $s\in \mathcal{S}$ must span the end trigger string of its respective phrase, and this trigger string cannot be a prefix of s, because all suffixes are longer than w. If the suffixes in S were not prefix-free with respect to each other, then some $s\in \mathcal{S}$ would be a proper prefix of another $s^{\mathrm{\prime }}\in \mathcal{S}$. This would imply that the phrase from which s′ originates spans a trigger string that is neither a proper prefix nor a suffix of the phrase, contradicting the definition of a PFP phrase. Therefore, S must be prefix-free. Note that although S is prefix-free, it does not follow that each $s\in \mathcal{S}$ is necessarily unique, as distinct phrases may share the same suffix. An overview of the entire PFP workflow is provided in Figure 1.

Figure 1.

Overview of the PFP workflow. (1) PFP takes as input a text T and two integer parameters, the window size w and the hash modulus p. In the example, w = 2 and p ∈ Z⁺, where Z⁺ represents the set of positive integers. (2) It internally prepends the $ symbol and appends w consecutive copies of # to T. (3) The modified text is parsed by sliding a window of length w across the text; when a trigger string is encountered (highlighted in green), the current phrase terminates and the next phrase begins. During parsing, the dictionary $D_T$ and parse $P_T$ are constructed, with $D_T$ initially unsorted and $P_T$ containing temporary phrase records (*). (4) Finally, $D_T$ is sorted and the records in $P_T$ are replaced by the ranks of the corresponding dictionary phrases; the dotted box shows the multiset S of suffixes longer than w derived from phrases in $D_T$.

Open in new tabDownload PowerPointLink to figure

We illustrate PFP using a small example. Instead of the one-pass algorithm presented earlier, we present it as a two-pass approach in this example for the sake of clarity. Let w = 2 and

The multiset of suffixes S as specified in Lemma 3 would be

PFP is designed for large repetitive texts, so this small example does not fully demonstrate the algorithm’s compression capabilities. In practice, the combined representation of $D_T+P_T$ is usually much smaller than T when T is large and repetitive. However, even in this small example, PFP achieves a level of compression. The second dictionary index appears twice in the parse, indicating that the algorithm effectively eliminated storing one instance of the second dictionary phrase without penalty. In practice, PFP is fairly efficient. The algorithm uses $O\left(\right|D_T|+|P_T\left|\right)$ memory and runs in $O\left(n\right)$ time, where $\left|D_T\right|$ represents the length of all the phrases in $D_T$, $\left|P_T\right|$ is the length of $P_T$, and n is the length of T. PFP can be used as a preprocessing step to build data structures such as ${BWT}_T$, ${SA}_T$, and ${LCP}_T$. In the following sections, we will go over the construction algorithms of these data structures.

Recursive prefix-free parsing

Recursive PFP provides an additional layer of compression on the PFP output. For large repetitive data sets, the dictionary $D_T$ has been observed to grow sublinearly relative to the parse $P_T$ (Oliva et al. 2023). Recall from the Prefix-free parsing section that $D_T$ grows only when a unique phrase is encountered, whereas $P_T$ grows with every phrase. Although the output of PFP is usually much smaller than the input, it can still be too large for memory-constrained applications, prompting the development of recursive PFP.

Recursive PFP applies PFP to the parse $P_T$, producing a new dictionary $D_P$ and parse $P_P$ that fully represent it. Combined with $D_T$, these components fully represent T and form the output of recursive PFP. The key idea behind recursive PFP is that although $P_T$ grows linearly, it remains highly repetitive, as phrases typically occur in the same order in repetitive texts, making it suitable for another round of PFP. Once PFP is applied to $P_T$, it can be safely deleted. If $P_T$ is larger than $D_T$ and is compressible, then recursive PFP will produce a noticeably smaller output than PFP. The idea of recursive PFP was briefly mentioned in Gagie et al. (2019) and more recently in Oliva et al. (2023). In theory, any application using PFP outputs can also be modified to use recursive PFP outputs. See Table 1 for applications where the recursive PFP has been successfully applied. Recursive PFP enables PFP to scale to arbitrarily large repetitive data sets by applying it recursively to each successive parse, provided the parse remains sufficiently compressible.

Burrows–Wheeler transform (BWT)

The Burrows–Wheeler transform (BWT) was introduced in Burrows and Wheeler (1994) as a reversible preprocessing technique that rearranges text to make it more compressible. The ${BWT}_T$ is a special reversible permutation of the text T$, where T[0 · · · n − 1] is the original text and $ is a unique sentinel character appended to T that is lexicographically smaller than all other characters. Conceptually, the ${BWT}_T$ can be constructed by first building the ${BWT}_T$ matrix by sorting all rotations of T$ lexicographically. The last column of the ${BWT}_T$ matrix is referred to as the ${BWT}_T$. To illustrate this construction, Figure 2A shows a visualization of ${BWT}_T$ for the example introduced in the Prefix-free parsing section. However, in practice, the ${BWT}_T$ matrix is never explicitly constructed due to its quadratic space requirements.

Figure 2.

Visualization of the ${BWT}_T$, ${SA}_T$, and ${LCP}_T$ for the example introduced in the Prefix-free parsing section. For clarity, the ${BWT}_T$ matrix is shown in each subfigure to highlight the information captured by each data structure. (A) The ${BWT}_T$. In the ${BWT}_T$ matrix, only the first (C) and last (${BWT}_T$) columns are highlighted; these columns are annotated with character ranks as subscripts, although in practice these ranks are computed using an auxiliary data structure. To the left of the first column, we illustrate how the C array is populated, and to the right of the last column we show the maximal character runs in the ${BWT}_T$. Also shown is how pattern matching is performed using the C array and ${BWT}_T$. (B) The ${SA}_T$. In the ${BWT}_T$ matrix, the suffixes of T$ that prefix each rotation are highlighted. (C) The ${LCP}_T$. In the ${BWT}_T$ matrix, the longest common prefix between consecutive rotations of T$ is highlighted.

Open in new tabDownload PowerPointLink to figure

The key observation of Burrows and Wheeler is that identical characters tend to group together and create runs in the ${BWT}_T$. For example, the text used in Figure 2A contains 27 characters, yet its ${BWT}_T$ has only 13 maximal character runs. This demonstrates how the ${BWT}_T$ reorders T$ to increase its local regularity by exploiting higher-order contexts. The effect arises because the initial lexicographic sort groups together rotations with similar or identical prefixes. In particular, the start of each rotation corresponds to a suffix of T$, which explains why the prefixes of consecutive rotations reveal repeated substrings in the text. Because texts are structured for comprehensibility, only a few distinct characters typically precede any given substring, and this number decreases as the length of the substring increases. This structural property gives rise to the runs observed in the ${BWT}_T$. The presence of runs in the ${BWT}_T$ does not compress the text on its own, but the resulting structure is well-suited for compression by other algorithms. The authors suggest applying a move-to-front transformation (Bentley et al. 1986) to the ${BWT}_T$ to convert these runs into a skewed distribution of small integers, followed by Huffman encoding (Huffman 1952). This compression scheme forms the core of the Bzip2 algorithm (Seward 1996), a widely used compressor today.

Another important property of the ${BWT}_T$ is that it is reversible, allowing the original text to be recovered. This reversibility is guaranteed by the sentinel character $ appended to the text, which establishes a unique total order among the rotations of T by breaking ties that might otherwise arise during lexicographic comparison. Because all rotations of T$ are used to construct the ${BWT}_T$, every row and column of the conceptual ${BWT}_T$ matrix is a permutation of T$, as illustrated in Figure 2A. In particular, the relative order of the characters in T$ is preserved between the first and last columns because the rotations are lexicographically sorted. Moving from the last column to the first effectively steps back one character in T$. This relationship between the two columns is known as the last-to-first (LF) mapping, formally defined below.

From Definition 4, LF(i) returns the index in the first column of the ${BWT}_T$ matrix that corresponds to the character at index i in the ${BWT}_T$. The C integer array is a highly compressed representation of the first column of the ${BWT}_T$ matrix, a column whose characters are lexicographically sorted. Both the first column (C) and the last column (${BWT}_T$) are essential for LF-mapping. However, compared to the size of the ${BWT}_T$ which is the size of |T$|, the C array is significantly smaller and requires only |Σ| + 1 entries. For DNA, this means only four entries for the different nucleotides, plus one entry for the special $ character appended to the text.

The text T$ can be reconstructed from the ${BWT}_T$ by repeatedly applying LF(i), starting from the last character, $. Let T′ represent the reconstructed text. Initialize T′[n] := $ and s := 0 where n is the length of T and s is an iterator where 0 ≤ s ≤ n. For i = n − 1, …, 0, assign $T^{\mathrm{\prime }}\left[i\right]:={BWT}_T\left[s\right]$ and update s := LF(s). At the end of the loop, we will get T′ = T$, recovering the text. In other words, T$ was reconstructed in reverse using the LF-mapping property.

Ferragina and Manzini (2000) showed that the ${BWT}_T$ can be used for more than just compression purposes. In particular, they demonstrated that the ${BWT}_T$ enables efficient exact backward pattern matching within the text. This process is similar to how the original text is reconstructed. However, instead of tracking individual positions, the algorithm maintains a range in the ${BWT}_T$ corresponding to all suffixes of T that match the current query suffix. Given a pattern P[0 · · · p − 1], backward matching consists of p steps that preserve the following property: after matching the last i characters of P, the start of the search range sp corresponds to the first row of the ${BWT}_T$ matrix prefixed by P[p − i · · · p − 1] and the end of the range ep corresponds to the last such row. To extend the match to the next preceding character, LF-mapping is applied to both sp and ep, computing the new range as:

Suffix array

The suffix array (SA) was formally introduced in Manber and Myers (1993) as a space-efficient alternative to suffix trees (Weiner 1973; McCreight 1976; Apostolico 1985) for online string searches, demonstrating three to five times lower space usage. Conceptually simple, the ${SA}_T$ is an array of length |T$| where ${SA}_T\left[i\right]$ gives the starting index in the text of the (i + 1)th lexicographically smallest suffix of T$, for 0 ≤ i < |T$|. That is, the ${SA}_T$ stores the starting indices of the lexicographically sorted suffixes of T$. Figure 2B shows the ${SA}_T$ for the example introduced in the Prefix-free parsing section. Although the ${SA}_T$ is more space-efficient than the suffix tree, it still requires O(|T$|) space.

The ${SA}_T$ and ${BWT}_T$ are intrinsically linked, as both are constructed by lexicographically sorting the suffixes of the text T$. More formally, the relationship between the two data structures is as follows:

The r-index

The FM-index, which consists of the ${BWT}_T$ and ${SA}_T$, has been a foundational data structure in bioinformatics. However, a notable drawback is that the size of both the ${BWT}_T$ and ${SA}_T$ is proportional to the size of T$ (see the BWT and SA sections). For very large data sets, these data structures become too large to be practical. As a result, considerable research has focused on compressing the FM-index. The use of run-length encoding the ${BWT}_T$ has been established for some time (Mäkinen and Navarro 2005; Mäkinen et al. 2010), but sampling the ${SA}_T$ within similar space remained an open problem for much longer. The problem remained open until 2017, when Gagie et al. (2020) introduced the r-index in their preprint, solving the problem by storing ${SA}_T$ values only at the run boundaries of the ${BWT}_T$. With a few small auxiliary data structures, the missing ${SA}_T$ can be efficiently computed. This insight completed the design of the r-index, enabling it to be stored in $O\left(r\right)$ space, where r denotes the number of maximal character runs in the ${BWT}_T$. In practice, r ≪ |T$|. Despite the shift toward the r-index in recent literature, its construction is conceptually rooted in the FM-index, which serves as the architectural basis for its compressed successor.

Building the FM-index (BWT and SA) from PFP

Boucher et al. (2019) introduced the PFP algorithm as a preprocessing step for the scalable construction of large BWTs. Building on this work, Kuhnle et al. (2020) showed how to construct the ${SA}_T$ sample alongside the ${BWT}_T$. In doing so, they effectively showed how to construct the FM-index of the text from the PFP output, namely $D_T$ and $P_T$. We illustrate this process through a detailed walkthrough of the algorithm by continuing the example introduced at the end of the Prefix-free parsing section, which serves as the basis for the following discussion. Figure 3A shows the PFP output.

Figure 3.

PFP-based construction of the FM-index for the example introduced in the Prefix-free parsing section. Color denotes phrase membership in all subfigures. (A) The input text and the PFP output after parsing. See the Prefix-free parsing section for more details. (B) The partial order ${BWT}_T$ and ${SA}_T$ constructed from $D_T$ and the occurrence frequencies of $P_T$, where each unique suffix in S (derived from $D_T$) prefixes at least one ${BWT}_T$ rotation and appears in sorted order in the matrix. Suffixes that prefix multiple rotations create ambiguous entries, denoted by a bold “?” symbol. (C) Ambiguous entries are resolved using the positions, in the ${BWT}_P$, of the phrases from which those suffixes originate. (D) The total order ${BWT}_T$ and ${SA}_T$ computed after resolving all ambiguous entries. Entries that were previously ambiguous are bolded.

Open in new tabDownload PowerPointLink to figure

In the Prefix-free parsing section, we described how PFP is applied to the text $\mathrm{\$}T{\mathrm{\#}}^w$. The prepended $ and appended ${\mathrm{\#}}^w$ ensure that the text begins and ends with a trigger string. Although $ is shorter than the standard w-length trigger string, it still functions as a valid trigger because it is guaranteed to be unique within the text. This uniqueness preserves the prefix-free property (see Lemma 3). Furthermore, this use of $ is consistent with its role in the standard BWT and SA constructions, where $ is the lexicographically smallest sentinel appended to T. Establishing this consistent role of $ is crucial, as it allows us to align the lexicographically sorted rotations of the PFP modified text $\mathrm{\$}T{\mathrm{\#}}^w$ with those of the standard $FM\text{-}index$ text T$.

Structurally, T$ and $\mathrm{\$}T{\mathrm{\#}}^w$ differ in only two respects: the placement of the sentinel symbol $ and the addition of the appended ${\mathrm{\#}}^w$ characters. The placement of the sentinel, whether at the beginning or end, does not affect the lexicographic ordering of rotations, as the text is treated circularly; this is consistent with the definition of the BWT and SA, which are constructed from all cyclic rotations of the text. Similarly, appending ${\mathrm{\#}}^w$ symbols does not alter the ordering because these symbols are defined to be lexicographically smallest, ensuring the lexicographical order of the rotations is preserved. Taken together, these observations imply that the lexicographical ordering of the rotations for both texts is identical. Furthermore, all suffixes of T$ act as prefixes to rotations of $\mathrm{\$}T{\mathrm{\#}}^w$ when the sentinel is conceptually moved to the front. Therefore, the ability to lexicographically sort $\mathrm{\$}T{\mathrm{\#}}^w$ implies that T$ can also be sorted, effectively bridging the two texts.

The lexicographically sorted rotations of $\mathrm{\$}T{\mathrm{\#}}^w$ can be obtained by sorting the dictionary phrase suffixes of the multiset S. From Lemma 3, we know that the suffixes in this multiset have length greater than w and are prefix-free, meaning that the unique suffixes in the multiset can be unambiguously ordered lexicographically. Because the initial PFP segmentation is lossless and divides the text into w-length overlapping phrases, this means that each suffix in S must be a prefix to at least one rotation of the text $\mathrm{\$}T{\mathrm{\#}}^w$, as illustrated in Figure 3B. By transitivity, lexicographically ordering the unique suffixes in S induces the corresponding lexicographic ordering of T$. However, Figure 3B shows only 23 unique suffixes, whereas Figure 2B shows that T$ contains 27 suffixes, revealing a discrepancy of four suffixes. There are two reasons for the discrepancy in the counts. First, the second dictionary phrase appears twice in the parse, so each of its suffixes longer than w is a prefix to twice as many rotations as it would if the phrase appeared only once. This accounts for three of four missing suffixes. Second, as shown in Figure 3B, the 20th lexicographically smallest suffix (index 19), TAC, is shared by the first and fourth dictionary phrases. Although TAC prefixes two distinct rotations in the text, these occurrences are represented by a single entry in the sorted list of unique suffixes, accounting for the final missing suffix. This information can be derived solely from the dictionary and the frequency of each phrase in the parse. However, relying solely on this information yields only a partial ordering of the rotations, resulting in an incomplete ${BWT}_T$ and ${SA}_T$, as shown in Figure 3B. If a phrase appears multiple times, we cannot determine which phrase precedes each occurrence, making it difficult to fully resolve the ${BWT}_T$ and ${SA}_T$. Similarly, if multiple phrases share a common suffix, the ${BWT}_T$ character and ${SA}_T$ value for the rotations prefixed by that suffix become ambiguous. Computing the total order ${BWT}_T$ and ${SA}_T$ requires positional information from the parse.

Ambiguities in the partial order ${BWT}_T$ and ${SA}_T$ can be resolved by examining the ${BWT}_P$, as shown in Figure 3C. Recall that the parse lists the lexicographic ranks of dictionary phrases in textual order. Consequently, the sorted rotations of the parse correspond to the relative order of the phrases within the sorted rotations of the text. Because ambiguities in the partial order arise from identical phrase suffixes, they can be resolved by comparing the text immediately following those suffixes (the remainders of the rotations). Because PFP phrases always end at trigger strings, the remainders of the rotations correspond to the start of the next phrase in the sequence. Therefore, the lexicographical ordering of the parse rotations (captured by the ${BWT}_P$) provides the necessary information to resolve these ambiguities.

Continuing from the partial order in our running example, the first ambiguity arises because the second phrase, ACAT#, is preceded by both the first and fourth dictionary phrases. Therefore, to determine the ordering, we must identify which occurrence of the second phrase appears earliest in the ${BWT}_P$. In the parse sequence, these occurrences are followed by the fourth and fifth phrases, respectively. A visual inspection of the first column of the ${BWT}_P$ matrix confirms that the fourth phrase appears earlier than the fifth. This implies that the second phrase occurrence preceded by the first phrase is lexicographically smaller than the one preceded by the fourth phrase. In the context of resolving the ${BWT}_T$, it coincidentally does not matter because both preceding phrases end with T (after accounting for the w-length overlap); however, it does matter in resolving the ${SA}_T$ at these indices. The second ambiguity arises because the suffix TAC is shared by both the first and fourth dictionary phrases. Because it is preceded by different characters in each phrase, the order in which the phrases appear in the ${BWT}_P$ becomes significant in constructing the ${BWT}_T$. To resolve the ambiguity, we follow the same steps as before. It turns out that both phrases are followed by occurrences of the second phrase, whose order we previously determined. By transitivity, this implies that the first phrase precedes the fourth, meaning that T should precede A in the ${BWT}_T$ for these specific rotations. Finally, once the correct ordering is determined, calculating the ${SA}_T$ values is straightforward: the suffix length is subtracted from the corresponding phrase’s end position in the text to obtain the suffix’s start position. The total order ${BWT}_T$ and ${SA}_T$ can be seen in Figure 3D.

To efficiently implement these concepts, two technical optimizations are required. First, the ordering of the suffixes in S in practice is achieved by constructing the suffix array of the dictionary, denoted as ${SA}_D$. The dictionary phrases are concatenated using a unique end-of-word separator symbol [EOW], forming the string $D_T=d_1\left[\mathrm{EOW}\right]d_2\left[\mathrm{EOW}\right]\cdots d_{\left|D\right|-1}\left[\mathrm{EOW}\right]d_{\left|D\right|}\left[\mathrm{EOW}\right]$ where d_i is the ith lexicographically sorted dictionary phrase. In ${SA}_D$, any suffix containing [EOW] within its first w + 1 characters is ignored because these suffixes are shorter than or equal to w and therefore do not belong to multiset S. The [EOW] symbol is defined to be lexicographically smaller than all other characters, including the $ and # symbols added during the PFP parsing. Therefore, the first —$D_T$—suffixes in ${SA}_D$ will correspond to rotations that start with [EOW]. Notably, the [EOW] symbols will appear in the exact positional order of their occurrence in the concatenated $D_T$, because the dictionary phrases were previously sorted. This structure is beneficial, as it allows for binary search in this subsection of the ${SA}_D$ to efficiently identify the originating phrase of any suffix and calculate its length. Second, explicitly scanning the ${BWT}_P$ is inefficient. Instead of explicitly scanning the ${BWT}_P$, an auxiliary data structure called the inverted list (IL) is built. This is implemented as a single array of size $\left|P_T\right|+1$ (accounting for the parse length $\left|P_T\right|$ plus the sentinel). The array stores the ${BWT}_P$ indices of all phrase occurrences, grouped by phrase and ordered lexicographically. In this capacity, the IL array effectively acts as an interface between the first column (sorted phrases) and the last column (${BWT}_P$) of the ${BWT}_P$ matrix, enabling the efficient retrieval of phrase occurrences in the ${BWT}_P$ without the overhead of a full scan. These indices can then be used to index auxiliary data structures of size $\left|P_T\right|+1$ generated by PFP, which store the ${BWT}_T$ character and ending position of each phrase to efficiently resolve ambiguous entries in the ${BWT}_T$ and ${SA}_T$.

Longest common prefix array

The longest common prefix (LCP) array was introduced in Manber and Myers (1993) as an auxiliary structure to accelerate pattern search with the SA. For two arbitrary strings T₁[0 · · · n − 1] and T₂[0 · · · m − 1], the value of $LCP(T_1,T_2)$ falls into one of the three cases: (1) 0, if T₁[0] ≠ T₂[0], (2) $min(n,m)$, if T₁ or T₂ prefixes the other, or (3) the unique i such that T₁[0 · · · i − 1] = T₂[0 · · · i − 1] and T₁[i] ≠ T₂[i]. The ${LCP}_T$ array stores the LCP values between consecutive suffixes of T in lexicographic order. Formally, ${LCP}_T[0\cdots n]$ is defined by ${LCP}_T\left[0\right]:=0$ and for 1 ≤ i ≤ n:

Building the LCP array from PFP

Rossi et al. (2022) introduced a PFP-based FM-index construction that simultaneously computes the LCP array, allowing for a wider range of string queries that can be performed with the index. To construct the complete ${LCP}_T$ array, they first build an auxiliary structure called the SLCP, a variant of the ${LCP}_P$, where the LCP values are computed over the uncompressed form of $P_T$0, excluding the w-length overlap between phrases. Note that the 0 is a sentinel appended to $P_T$, which is why the dictionary ranks in the parse start at 1 rather than 0. More formally, $SLCP[0\cdots |P_T\left|\right]$ is defined by $SLCP[0\cdots 2]=0$ and for $2<i\le \left|P_T\right|$:

Figure 4.

Visualization of the $SLCP$ for the example introduced in the Prefix-free parsing section. The $SLCP$ represents the ${LCP}_P$ with $P_T$ decompressed and the last w characters trimmed from each phrase, effectively creating rotations starting at phrase boundaries of T. In the accompanying ${BWT}_P$ matrix, colors are used to highlight phrases within each rotation, and bolded characters emphasize the $SLCP$ values. Because the built-in overlap is removed, the last w characters of each phrase are split and colored half by the preceding phrase and half by the following phrase.

Open in new tabDownload PowerPointLink to figure

During the FM-index construction, the ${LCP}_T$ can start to be built once the lexicographic ordering of the rotations is determined. As discussed in the Building the FM-index from PFP section, the problem of sorting the rotations reduces to correctly sorting the suffixes of the $D_T$ phrases with length greater than w, which prefix all rotations. Now let α and β be the $D_T$ suffixes that prefix the rotations of ${SA}_T[i-1]$ and ${SA}_T\left[i\right]$ and let p₁, p₂ be the indices in the ${BWT}_P$ of the phrases from which α and β are derived from and let p₁ < p₂. Then, the ${LCP}_T$ can be computed as follows:

Suppose that we want to calculate ${LCP}_T\left[23\right]$ in our example. Recall that in the Prefix-free parsing section that this rotation was initially ambiguous in the partial order ${BWT}_T$ because it was prefixed by the suffix TAC, which is shared by both the first and fourth dictionary phrases. We now know that the rotation of the first phrase precedes the rotation from the fourth phrase. Because these two rotations are prefixed by the common suffix TAC, we know that the LCP value between these two rotations is at least 3. From Figure 4, we find that their remainders correspond to the third (index 2) and fourth (index 3) rotations of the ${BWT}_P$ matrix, so we need to perform an RMQ on the SLCP between the range of [2 + 1 · · · 3] and this returns 8, the only value within the range. Therefore, ${LCP}_T\left[23\right]=3-2+8=9$, which matches the value shown in Figure 2C. Note that w must be subtracted from the suffix length in this case, because the minimum SLCP value already accounts for the w-length overlap between the common suffix prefixing the rotations and the start of their remainders.

Building fundamental bioinformatic data structures

As previously discussed, the ${BWT}_T$ (Boucher et al. 2019), ${SA}_T$ (Kuhnle et al. 2020), and ${LCP}_T$ (Rossi et al. 2022) have been built from the PFP output. Boucher et al. (2019) showed that PFP enables substantially more resource-efficient construction of the run-length FM-index (RLFM-index) than Bowtie’s (Langmead et al. 2009) FM-index-based approach on large collections of human Chromosome 19 (Chr 19) sequences. Across collections of up to 1000 Chr 19 sequences, the RLFM-index was consistently at least an order of magnitude faster to build than Bowtie’s index and, once the collection exceeded 50 sequences, required an order of magnitude less peak memory. In both cases, the performance gap widened as additional sequences were added. On a 512 GB server, Bowtie exhausted all available memory after indexing just 250 sequences, whereas the PFP-based RLFM-index was successfully constructed for all 1000 sequences within the same memory constraints. Additional evidence supporting these claims is presented in the Experimental results section. Subsequently, both Kuhnle et al. (2020) and Rossi et al. (2022) further demonstrated the efficiency of PFP-based construction algorithms for large, repetitive data sets.

To further reduce both the time and memory requirements of constructing the aforementioned data structures for large data sets, recursive PFP has been applied (Oliva et al. 2023; Ferro et al. 2024) (see the Recursive prefix-free parsing section for details). Oliva et al. (2023) showed that, for extremely large collections of sequences, constructing the ${BWT}_T$ from the output of recursive PFP is more computationally efficient than the construction from standard PFP. They repeated the experiment of Boucher et al. (2019), this time scaling up to 2400 Chr 19 sequences, more than double the amount used previously. Compared with the standard PFP-based construction, the recursive PFP-based approach reduced memory usage from approximately 40 to 15 GB and halved the running time from roughly 3000 to 1500 s, demonstrating substantial improvements in both speed and memory efficiency. However, this improvement only started to become noticeable after around 500–1000 sequences. For smaller collections, the performance difference between the two methods was negligible. These empirical results are supported by the theory of recursive PFP. Ferro et al. (2024) extended this work and showed how to build the ${SA}_T$ and ${LCP}_T$ alongside the ${BWT}_T$ with recursive PFP.

Extensions and specialized indexing structures

Beyond the classical bioinformatics data structures discussed in this paper, PFP has also been used to build extensions of these structures, or components thereof, including the compressed suffix tree (CST) (Boucher et al. 2021b; Oliva et al. 2022), the extended BWT (eBWT) (Boucher et al. 2021a, 2024), the suffixient set (Cenzato et al. 2024), and the move structure (Zakeri et al. 2024, 2025). Rather than directly building the CST, Boucher et al. (2021b) show that the output of PFP can be augmented to support full suffix tree functionality. This is particularly important because the suffix tree can be viewed as a unifying conceptual framework for many string data structures, including those considered in this paper, and therefore plays a central role in bioinformatics, at least from a historical point of view. Suffix trees have a large space overhead relative to the input, and although CSTs reduce this overhead, they remain expensive to construct. Notably, the PFP-based CST construction by Boucher et al. (2021b) was shown to be more time and memory efficient than the state-of-the-art implementations in the Succinct Data Structure Library (SDSL) (Gog et al. 2014), a widely used benchmark library for compressed data structures. The eBWT extends the BWT to string collections by grouping related subsequences across different strings (Mantaci et al. 2007). The eBWT enables similarity detection and has been used as an index in metagenomic applications, helping to determine the taxonomic origin of sequencing reads (Ander et al. 2013; Guerrini et al. 2020). The suffixient set (Depuydt et al. 2023; Cenzato et al. 2024; Navarro et al. 2025) is a novel data structure that stores a small subset of integers capturing all branching points of a suffix tree. Although being new, it holds promise as a compressed index for string matching tasks in bioinformatics. The move structure (Nishimoto et al. 2022) is another new compressed data structure, based on the BWT. It has the unique beneficial properties of being stored in $O\left(r\right)$ space while still supporting $O\left(1\right)$ LF queries. Zakeri et al. (2024, 2025) implemented the data structure and showed that, in practice, its favorable locality of reference limits cache misses, leading to significant speed gains for string matching queries over other pangenomic data structures, such as the r-index.

String matching queries

Another subset of PFP research focuses on string queries enabled by data structures constructed from PFP. Many useful string matching queries can be calculated from matching statistics. Briefly, the matching statistics MS[0 · · · m − 1] describe how a read R[0 · · · m − 1] aligns to a text T[0 · · · n − 1]. For each position i in R, MS[i] returns a pair: the length of the longest prefix starting at R[i] that occurs in T, and the position of one such occurrence in T. Matching statistics have been used in PFP applications to support various string queries, including maximal exact matches (MEMs) (Rossi et al. 2022), which cannot be extended in either direction; maximal unique matches (MUMs) (Giuliani et al. 2022; Shivakumar and Langmead 2025), which occur only once in T; and pseudo matching lengths (PMLs) (Ahmed et al. 2021, 2023), an efficient approximation of matching statistics. Varki et al. (2025) used MEMs as seeds for their r-index based short-read aligner, adopting the approach popularized by BWA-MEM (Li 2013). Shivakumar and Langmead (2025) computed multi-MUMs across 300+ human assemblies using under a terabyte of memory, facilitating the visualization of novel structural insights. Ahmed et al. (2021, 2023) demonstrated that PMLs can be computed in a streaming manner fast enough to process Nanopore sequencing reads in real time, allowing for direct metagenomic classification.

Text compression and grammar induction

A further line of PFP research investigates its use as a preprocessing step to construct classical compressed representations, building on its origins in text compression. Hong et al. (2023) showed that PFP can be used to construct the LZ77 factorization, a compression algorithm that divides the text into the longest substrings matching earlier occurrences (Ziv and Lempel 1977). LZ77 is a foundational algorithm in string processing and forms the basis of many modern compression algorithms, including LZMA2 and Deflate (core algorithm of gzip). Similarly, Gagie et al. (2019) showed that PFP (called CTPH at the time) can be used to build a variant of the RePair grammar. RePair is a grammar-based compression algorithm that recursively replaces the most frequent adjacent pair of characters with a new previously unseen character until no repeats remain (Larsson and Moffat 2000). Although conceptually simple, it achieves good compression in practice. However, it requires memory proportional to the input size, making it impractical for large data sets. Gagie et al. (2019) showed that their PFP-based RePair grammars can be constructed for inputs several orders of magnitude larger than those handled by standard RePair, using a fraction of the time and memory. Kim et al. (2024) extended this work and showed that both time and memory usage could be further reduced when the grammar was built from recursive PFP, noting that these benefits were observed only for large collections of sequences, consistent with the findings of Oliva et al. (2023).