Parallel Algorithm caps-sa Accelerates Genomic Suffix Array Construction Through Cache-Friendly Merging

Computational biologists have developed a fast, parallel string indexing algorithm named caps-sa that accelerates suffix array and longest common prefix array construction while dramatically reducing memory cache misses on modern multicore computing architectures. When evaluated on the complete telomere-to-telomere human genome assembly known as CHM13 version two, the new method constructed both the suffix array and the associated longest common prefix array in one hundred and six seconds using forty-eight gigabytes of shared memory across thirty-two processor threads. Under identical hardware conditions, the leading alternative parallel method, parallel-dc3, required one hundred and nineteen seconds and consumed one hundred and sixteen gigabytes of system memory while constructing the suffix array alone. This performance advantage highlights how aligning high-level algorithmic sorting strategies with the physical memory hierarchies of modern multicore processors can overcome long-standing computational bottlenecks in processing massive whole-genome sequencing datasets, providing an efficient open-source foundation for next-generation genomic analysis pipelines and reference data structures.

String indexing structures represent fundamental components within computational genomics, serving as the foundational search machinery behind read-to-reference alignment tools, sequence clustering platforms, and short-read sequencing error correction workflows. Among these structures, the suffix array arranges all suffixes of an input genetic text into sorted lexicographical order, enabling rapid search capabilities across expansive biological sequences. Working in close tandem with the suffix array, the longest common prefix array records the lengths of shared prefixes between adjacent sorted suffixes, forming auxiliary index combinations such as enhanced suffix arrays that replicate the functional capabilities of traditional suffix trees while demanding substantially less physical storage. Although classic sequential algorithms can construct both arrays in linear time proportional to sequence length, the sheer expansion of genomic throughput—encompassing telomere-resolved assemblies, complex pangenomes, and extensive clinical sequencing libraries—has created an urgent operational necessity for highly parallel construction techniques capable of exploiting parallel multi-socket server hardware.

Existing efforts to parallelize suffix array construction have introduced sophisticated divide-and-conquer schemes, external memory pipelines, distributed memory routines, and GPU-accelerated algorithms, including widely cited frameworks like parallel DivSufSort and parallel DC3. However, many advanced parallel strategies introduce elaborate theoretical mechanisms to achieve sublinear worst-case execution depth, resulting in software designs that are exceptionally difficult to implement, maintain, and optimize for modern deep processor cache hierarchies. In contrast, caps-sa adopts an architecture rooted in algorithmic simplicity, combining a samplesort organizational framework with an LCP-informed merge routine to maintain exceptional memory locality. Rather than immediately drawing random pivot elements across unorganized text, the algorithm divides the input sequence into uniformly sized subarrays across assigned threads, executes localized parallel sorting across each subproblem, and subsequently applies an oversampling procedure to identify evenly spaced global pivots that divide the overall problem into balanced workloads.

Directly applying generic sorting routines to biological text is computationally prohibitive because string comparisons demand non-constant execution time proportional to the length of shared character sequences. The caps-sa architecture addresses this fundamental obstacle by restricting suffix comparisons almost entirely to an specialized merge operation that continuously leverages precalculated longest common prefix values generated recursively during sorting. When comparing two suffixes from sorted candidate lists, the merge routine inspects previously determined prefix matches alongside the existing prefix array to determine lexicographical ordering through constant-time evaluations whenever prefix lengths diverge. Direct character-by-character text comparisons are triggered exclusively when previous prefix lengths precisely match, and the algorithm immediately advances past previously verified identical characters, adding newly discovered common prefix lengths directly into the output array. This mechanism eliminates redundant character inspections across repetitive sequence segments, ensuring efficient processing without relying on large auxiliary tracking tables.

The structural execution of caps-sa proceeds through four distinct operational phases that systematically coordinate data distribution, localized sorting, pivot collation, and recursive merging. In the initial phase, an unsorted suffix array is partitioned into uniform contiguous segments of size n divided by p, which are independently sorted using parallel merge-sort routines. Next, the algorithm samples a designated factor of suffixes from every sorted segment, aggregates and sorts these sampled candidates, and selects evenly spaced global pivots to delineate final partition boundaries. During the subsequent collation phase, each sorted subarray is searched for these global pivots using accelerated binary search procedures that skip repetitive character matches, breaking each subarray into further subdivisions that correspond to global partition targets. In the final phase, all corresponding sub-arrays designated for each partition are collated into contiguous memory regions and merged recursively in parallel, producing the fully ordered suffix array alongside boundary-resolved prefix lengths.

Rigorous mathematical analysis of caps-sa confirms robust asymptotic efficiency across typical operating environments, demonstrating an overall computational work bound of order n log n plus the sum of output prefix lengths with high probability. By applying Chernoff probability bounds to the oversampling pivot selection mechanism, the authors proved that choosing a sampling factor of thirty-two times the natural logarithm of sequence length guarantees that each resulting partition remains within a constant factor of the ideal subproblem size with high probability. Parallel computational depth is theoretically bounded by order n divided by p multiplied by log n with high probability across p target partitions, which provides sufficient thread concurrency to saturate modern multi-threaded work-stealing schedulers such as ParlayLib. While adversarial synthetic datasets exhibiting extreme prefix repetition can force worst-case quadratic running times due to output-sensitive prefix summations, natural biological sequences rarely exhibit such pathological structures during typical experimental runs.

To validate empirical efficiency and scaling responsiveness across realistic genomic workflows, the investigators evaluated caps-sa against state-of-the-art implementations of parallel-divsufsort, parallel-dc3, and the classic sequential divsufsort baseline across diverse biological reference sets. Benchmarking was performed on an enterprise computing server configured with four Intel Xeon Platinum 8160 processors providing a combined total of one hundred and ninety-two physical cores and one point five terabytes of DDR4 memory running Ubuntu Linux. Tested genomic datasets encompassed the standard human reference build GRCh38 patch thirteen, the telomere-to-telomere CHM13 assembly containing challenging repetitive heterochromatic sequences, compacted de Bruijn graph unitigs generated from human short-read sets by Cuttlefish 2, and large vertebrate reference genomes including the great white shark and the axolotl. A pathological stress dataset consisting of one thousand randomly sampled Salmonella enterica bacterial genomes was also incorporated to probe algorithmic limitations under severe sequence redundancy.

Experimental measurements collected via standardized operating system timing utilities demonstrated that caps-sa delivered superior execution speed compared to alternative parallel tools across all tested genomic references except the pathological bacterial collection. Although sequential single-threaded evaluations indicated that caps-sa executes greater total raw computational work than parallel-divsufsort or parallel-dc3 due to output-dependent prefix calculations, its superior cache performance allowed it to achieve faster absolute runtimes as thread allocation expanded from four to one hundred and twenty-eight cores. Hardware performance counter profiling using the Linux perf utility revealed that caps-sa achieved substantially lower processor cache-miss percentages across single-thread, thirty-two-thread, and sixty-four-thread configurations on both GRCh38 and CHM13 human genome assemblies. This empirical validation confirmed that superior cache locality and predictable memory access patterns significantly outweigh theoretical differences in asymptotic operation counts on modern multi-socket server hardware.

Addressing practical bioinformatics constraints where query sequences have predefined length restrictions, the authors introduced the formal concept of a bounded-context suffix array and demonstrated its natural implementation within caps-sa. In standard high-throughput sequencing alignment tools such as STAR, read mapping algorithms rely on short seed matches typically ranging between fifteen and thirty-one nucleotides, rarely exceeding maximum error-free read segments of approximately one hundred bases. Under a bounded-context formulation of order k, suffixes that share identical prefixes extending to or beyond k characters are treated as equivalent without resolving their deeper relative order, reducing theoretical comparison complexity to at most order n log n plus n times k in the worst case. Benchmarking on the highly repetitive one-thousand bacterial genome dataset demonstrated that constructing bounded-context arrays across power-of-two context lengths from sixty-four to sixty-five thousand five hundred and thirty-six dramatically diminished processing times compared to full-context construction.

Despite its notable runtime acceleration and cache efficiency, caps-sa exhibits distinct engineering trade-offs regarding memory footprint and algorithmic behavior on adversarial repetitive inputs that define its practical operational limits. While parallel-divsufsort achieved the lowest overall peak RAM utilization across several test cases, caps-sa requires four times the word size times sequence length in bytes of active working memory, though it concurrently outputs both the suffix array and the complete prefix array without auxiliary post-processing passes. The authors emphasized that the fine-grained, independent partition architecture of caps-sa makes it uniquely suited for future external-memory implementations, where individual subproblems and sampled pivot blocks can be paged dynamically between physical RAM and high-speed disk storage to satisfy strict hardware constraints. Implemented in modern C++17 and distributed under an open-source license, caps-sa provides high-performance parallel string indexing capable of scaling alongside ongoing expansions in genomic sequencing data.

Subject of Research: Parallel suffix array and longest common prefix array construction in computational genomics

Article Title: Fast, parallel, and cache-friendly suffix array construction

Article References: Khan, J., Rubel, T., Molloy, E., Dhulipala, L., & Patro, R. (2024). Fast, parallel, and cache-friendly suffix array construction. Algorithms for Molecular Biology, 19(1), Article 16. https://doi.org/10.1186/s13015-024-00263-5

Image Credits: AI Generated

DOI: 10.1186/s13015-024-00263-5

Keywords: suffix array, longest common prefix, parallel algorithms, cache locality, samplesort, computational genomics, bioinformatics, read alignment, genome indexing, multicore processing, merge sort, CHM13 assembly, GRCh38 reference, bounded-context suffix array, ParlayLib, string sorting, de Bruijn graph, memory hierarchy