PaperlayerView exact revision on arXiv

Source-linked AI summary

Prefix-Free Parsing for Building Big BWTs

Christina Boucher, Travis Gagie, Alan Kuhnle, Ben Langmead, Giovanni Manzini, Taher Mun

arXiv:1803.11245v4cs.DS

TL;DR

Genomic databases are growing beyond practical memory capacity, limiting analysis despite their high compressibility. This paper uses prefix-free parsing to construct BWTs from a dictionary and parse, and reports up to 10x speedup over the SACA-K-based baseline.

  • Problem

    Growing genomic databases limit analysis because of their size, even though their similarity makes them highly compressible.

    Source: §1 · pp. 1–2

  • Method

    Prefix-free parsing produces a dictionary and parse from which the BWT can be built using workspace proportional to their total size and time linear in the uncompressed text length.

    Source: §1 · pp. 2–3

  • Results

    Prefix-free parsing was up to 10x faster than the standard baseline that computes the BWT via SACA-K, while requiring roughly the same time on large salmonella genome sets.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The authors conclude that the method opens the possibility of constructing BWTs for terabyte-scale datasets such as GenomeTrakr and MetaSub.

    Source: §6 · p. 20

    The indexing demonstration supports counting only; suffix-array samples are excluded because their construction would require LF mapping for every text character and the entire BWT in memory.

    Source: §5 · p. 17

Abstract

from arXiv · show

High-throughput sequencing technologies have led to explosive growth of genomic databases; one of which will soon reach hundreds of terabytes. For many applications we want to build and store indexes of these databases but constructing such indexes is a challenge. Fortunately, many of these genomic databases are highly-repetitive---a characteristic that can be exploited to ease the computation of the Burrows-Wheeler Transform (BWT), which underlies many popular indexes. In this paper, we introduce a preprocessing algorithm, referred to as {\em prefix-free parsing}, that takes a text $T$ as input, and in one-pass generates a dictionary $D$ and a parse $P$ of $T$ with the property that the BWT of $T$ can be constructed from $D$ and $P$ using workspace proportional to their total size and $O (|T|)$-time. Our experiments show that $D$ and $P$ are significantly smaller than $T$ in practice, and thus, can fit in a reasonable internal memory even when $T$ is very large. In particular, we show that with prefix-free parsing we can build an 131-megabyte run-length compressed FM-index (restricted to support only counting and not locating) for 1000 copies of human chromosome 19 in 2 hours using 21 gigabytes of memory, suggesting that we can build a 6.73 gigabyte index for 1000 complete human-genome haplotypes in approximately 102 hours using about 1 terabyte of memory.

1 Introduction

Rapidly growing, highly repetitive genomic databases are difficult to index because current techniques struggle to process their scale. The paper presents prefix-free parsing as a one-pass way to reduce the resources needed to construct BWTs and evaluates its use in BWT and index construction.

1 Introduction

  • Genomic databases are large and highly repetitive, yet their size limits analysis and repeated scans, motivating indexes that fit in RAM.BWT-based indexes are popular, but current techniques struggle to process more than a few terabytes of raw data per day because of external-memory challenges.Source: §1 · pp. 1–2
  • Prefix-free parsing divides text into overlapping variable-length phrases, using rolling-hash window matches to delimit phrases in a one-pass linear-time parse.Window length w and modulus p affect dictionary size and parse length; parallel windows can speed parsing before results are merged.Source: §1 · p. 2
  • Up to 10x lower peak memory than SACA-K, with roughly the same time on large Salmonella genome sets.The comparison uses a standard baseline that computes the BWT by first computing the suffix array.Source: §1 · pp. 2–3
  • Prefix-free parsing produces a dictionary and parse that are often much smaller than the input, making internal-memory BWT construction more feasible.The paper describes BWT construction from the dictionary and parse alone, with workspace proportional to their total size and time linear in the uncompressed text length.Source: §1 · pp. 2–3
  • The authors demonstrate run-length compressed FM-index construction for datasets of up to 500 sequences and project a 6.73-gigabyte index for 1,000 complete human genomes in about 102 hours using about 1.1 terabytes of memory.The indexes described support counting, not locating.Source: §1 · p. 3

2 Review of the Burrows-Wheeler Transform

The section motivates text indexing through suffix-based structures, then explains how the suffix array and BWT support pattern search. The LF mapping connects BWT characters to sorted text characters, enabling FM-index searches.

2 Review of the Burrows-Wheeler Transform

  • A suffix trie indexes a collection by storing every suffix as a root-to-leaf path, with each leaf recording its starting position.For a pattern, search descends to its path and reports matching suffix positions from the subtree leaves.Source: §2 · pp. 3–4, Figure 1 · p. 4
  • Removing one-child nodes and concatenating edge labels yields a linear-size suffix tree, but representing its labels still requires access to the input.The trie can have quadratically many nodes; suffix-tree edge labels can be represented in constant space when the input is stored.Source: §2 · p. 4, Figure 2 · p. 5
  • A suffix array stores suffix starting positions in lexicographic order, enabling pattern search with two binary searches in O(m log n) time naively.The suffix tree's shape is discarded, but the input remains available for comparisons.Source: §2 · p. 4
  • The inverse suffix-array mapping Ψ advances from suffix position i to i + 1 and can support suffix extraction and pattern search.The discussion notes that Ψ can be stored using nH0(T) + o(n log σ) bits; this bound can be improved with more careful analysis.Source: §2 · p. 5
  • The LF mapping is the inverse of Ψ and partitions into σ increasing subsequences, one for each character in the alphabet.For each character, LF assigns consecutive positions based on the suffixes preceded by that character.Source: §2 · pp. 5–6, Figure 3 · p. 6
  • The BWT lists the character preceding each suffix in lexicographic suffix order; rank queries and the character-count array C implement LF-based pattern search.The section gives LF(i) = BWT.rank_BWT[i](i) + C[BWT[i]] and describes updating the suffix-array interval for a pattern.Source: §2 · pp. 6–7, Figure 4 · p. 7

3 Theory of Prefix Free Parsing

Prefix-free parsing builds a dictionary and overlapping-phrase parse in one scan, then uses them to compute the BWT in linear time with workspace proportional to their total size. Its construction exploits a prefix-free set of dictionary suffixes to order BWT characters, resolving ties with suffixes of the parse.

3 Theory of Prefix Free Parsing

  • A scan of # T $^w builds D from substrings between consecutive E′ occurrences and records their occurrences in T as the parse P.Each dictionary substring has exactly one proper prefix and suffix in E′ and no other substring in E′; consecutive parse elements overlap by w characters.Source: §3 · p. 7
  • Suffixes in S, defined as dictionary-element suffixes longer than w, form a prefix-free set and provide a unique S-prefix for every suffix of # T $^w longer than w.This unique-prefix mapping is the basis for assigning lexicographic ranks to the text suffixes.Source: §3 · pp. 8–9
  • The mapping β partially orders T′’s characters in BWT order by the ranks of the mapped S elements.The construction maps each character to the rank of an S element associated with the following suffix; appending terminators preserves suffix order, and each rank groups characters into a consecutive BWT interval.Source: §3 · p. 9
  • D and P frequencies determine BWT positions for ranks with one mapped character, while placeholders mark ranks requiring further ordering.The resulting subsequence can be interleaved with the missing characters and output using workspace proportional to the total length of P and D.Source: §3 · pp. 9–11
  • When a rank receives several distinct characters, sorting the corresponding parse suffixes orders those characters as they appear in the BWT.Lemma 7 links the order of text suffixes beginning with the same S element to the order of parse suffixes encoding their remaining parts.Source: §3 · pp. 10–11
  • The BWT of T $ can be computed from D and P in O(n) time using workspace proportional to their total length.The construction scans T once to form D and P, then sorts suffixes of dictionary elements and of P in internal memory.Source: §3 · p. 12
  • For repetitive T, D can be relatively small and, when dictionary phrases are sufficiently long, P can also be much smaller than T.If D and P fit in internal memory, the critical BWT computations can then be done in RAM after the parsing scan.Source: §3 · p. 12

4 Prefix free parsing in practice

The implementation parses text into a dictionary and parse, then reconstructs its BWT from those structures. Experiments show substantially reduced memory use, competitive or faster runtimes, and compact dictionary-plus-parse representations on repetitive datasets.

4.1 Implementation

  • A length-w window slides over the text, and a window whose Karp-Rabin hash is zero modulo p marks an overlapping phrase boundary.The first phrase receives a prepended NUL and the last phrase receives w appended NUL characters, with a special case when the text ends at a hash-zero window.Source: §4.1 · p. 12
  • The implementation deduplicates terminated phrases by hash with equality checks, then sorts the dictionary and replaces parse hashes with lexicographic ranks.It stores phrase frequencies and the parse entries as 4-byte integers, and records a character array W for later BWT reconstruction.Source: §4.1 · pp. 12–13
  • It computes the BWT of the ranked parse, stores phrase-wise inverted lists, then sorts dictionary-phrase suffixes and merges lists to produce the input BWT.For suffixes coinciding with dictionary phrases, it uses characters retrieved from W.Source: §4.1 · p. 13
  • Four threads yielded a factor-of-2 speed-up in both parsing and final BWT computation, while additional parsing threads brought no substantial improvement.The authors attribute likely constraints to shared dictionary updates and disk access; reported experimental runtimes use the single-thread algorithm.Source: §4.1 · pp. 13–14

4.2 Experiments

  • The dictionary and parse occupied 5 to 31 percent of uncompressed file space on the tested Pizza & Chili files.Long runs of Ns or periods can yield many phrases or a single long phrase, depending on the hash parameters.Source: §4.2 · p. 14, Table 3 · p. 14
  • For Salmonella datasets, the dictionary and parse occupied 14 to 44 percent of uncompressed space, reaching about 7 GB for 10,000 genomes with w = 10, p = 100.The authors report that the compression improved as the number of genomes increased, and that this 7 GB representation would fit in commodity-machine RAM.Source: §4.2 · p. 14
  • Peak memory fell by a factor of 4 to 10 versus simplebwt, with competitive runtime and reductions exceeding factors of 2 and 4 on 5,000- and 10,000-genome datasets.For BWT computations with w = 6, p = 20, peak memory stayed within roughly twice the original file size and was smaller than that size on the 1,000-genome dataset.Source: §4.2 · pp. 14–15

4.2.1 On the choice of the parameter w and p

  • On 1,000 Salmonella genomes, (w, p) = (10, 50) minimized peak memory while (10, 200) gave the fastest runtime; all tested settings used less than 1.1 times input-size memory and ran within a factor of two of the fastest.The memory- and runtime-optimal settings differed and depended on the input.Source: §4.2.1 · p. 15, Figure 5 · p. 15

5 Indexing

Section 5 evaluates a counting-only RLFM built using prefix-free parsing against Bowtie, then examines count-query scaling and the costs of adding SA samples.

5 Indexing

  • The counting-only RLFM uses prefix-free parsing for the BWT, then builds the F array and run-length encodes it; SA samples are excluded except where noted.During construction, characters other than A, C, G, T, or N are ignored.Source: §5 · p. 17

5.2.1 Index building

  • RLFM used about 20 GB for 1,000 chr19s, while Bowtie needed twice that for 250; prefix-free parsing's share of memory and time diminished as collections grew.The reported trends illustrate the advantage of prefix-free parsing for large, repetitive collections.Source: §5.2.1 · p. 18, Figure 6 · p. 18
  • Extrapolating chr19's 1.9% genome share, 1,000 haplotypes imply about 1.01 TB peak memory, 102 hours, and a 6.73 GB index.The authors note that parallelization could improve the time estimate; the index-size estimate excludes SA samples needed for locate queries.Source: §5.2.1 · p. 18

5.2.2 Count query time

  • Average count time rose from 750 microseconds for one sequence to 933 microseconds for 1,000, using 100,000 sampled 100-base substrings.The tested substrings were drawn from a chr19 included in every collection, so each occurred at least once.Source: §5.2.2 · p. 19, Figure 7 · p. 19

5.2.3 Including the SA sample

  • With SA sampling, index building adds back-stepping and run-length encoding; bwtscan drives peak memory, while pfbwt uses least memory above 50 sequences.pfbwt is slowest for small collections, but bwtscan becomes slowest for collections of 10 or more sequences; parsing presents no bottleneck for large collections.Source: §5.2.3 · p. 19, Figure 8 · p. 20

6 Conclusions

The conclusion presents prefix-free parsing as preprocessing for compression-aware BWT construction on large genomic databases and describes a possible streaming use during data downloads.

6 Conclusions

  • Dictionaries and parses are often much smaller than the original input and may fit in reasonable internal memory even when the text is very large.The BWT can be constructed from the dictionary and parse alone, and the paper reports experiments constructing a run-length compressed FM-index from them.Source: §6 · p. 20
  • During downloads, parsing can avoid storing the full uncompressed dataset in memory or on disk: keep the dictionary in memory and write the parse to disk as it is produced.The total space used can be less than the dataset itself.Source: §6 · p. 20
  • Server-side parsing could reduce transmission time or bandwidth, but its implementation and experimentation are left for future work.Source: §6 · p. 20

Authors’ contributions

The paper reports the authors’ roles, software availability, competing-interest status, funding, and affiliations.

Authors’ contributions

  • TG and GM conceptualized the idea and developed the algorithmic contributions; AK and GM implemented prefix-free parsing and conducted the experiments.CB and TG assisted with and oversaw the experiments and implementation; TM and BL implemented and tested the run-length compressed FM-index, and all authors contributed to writing.Source: Authors’ contributions · p. 20

Availability

Competing interests

Funding

  • Support came from NSF grant IIS 1618814, a University of Florida Informatics Institute postdoctoral fellowship, FONDECYT grant 1171058, and PRIN grant 201534HNXC.Source: Funding · p. 20

Author details

  • Author affiliations span Gainesville, Santiago, Baltimore, Alessandria, and Pisa.Source: Funding · p. 21
Loading 1803.11245v4…