Computer scientists Larissa L. M. Aguiar and Felipe A. Louza have designed a linear-time string processing algorithm that computes left-bounded shortest unique substrings twice as fast on average as existing methods while maintaining an identical peak memory footprint. The computational framework, detailed in Algorithms for Molecular Biology, operates in linear time relative to text length, consuming two memory words plus one byte per input character. Finding shortest unique substrings represents a fundamental problem in string processing and computational biology, where identifying unique text segments underpins sequence analysis pipelines. Across benchmarks evaluating biological genomes and repetitive artificial texts, the proposed implementation consistently outperformed leading published algorithms, demonstrating an average twofold speedup in practical execution time. By restructuring how intermediate arrays are processed and overwritten in working memory, the researchers achieved significant speed improvements without inflating storage requirements, resolving a persistent computational trade-off in modern genomic sequence analysis.
The computational task directly reflects the primer selection problem, an essential step in biological procedures such as the polymerase chain reaction used to amplify target DNA segments during genome sequencing. In molecular biology, a primer is a short strand of DNA or RNA, termed an oligonucleotide, that serves as a starting point for DNA synthesis. Within a given genomic text, the primer selection task requires identifying, for every character position, the shortest unique substring beginning at that index and occurring only once across the sequence. This formulation is equivalent to finding the left-bounded shortest unique substring, a variant introduced by Pei and colleagues. Beyond its direct utility in designing PCR primers, identifying left-bounded shortest unique substrings plays an integral role in other bioinformatics workflows, including alignment-free genome comparison and specialized data compression techniques tailored for massive DNA sequence repositories.
To formalize the problem mathematically, the researchers define an input string as a finite sequence of symbols drawn from an ordered alphabet of fixed size. A substring represents any contiguous segment within the primary text, designated as proper whenever it does not equal the entire original string. Prefixes denote substrings beginning at the first character, while suffixes denote substrings extending from an internal position through the final character. For analytical convenience and structural rigor, the input sequence is assumed to terminate with a unique sentinel character that appears nowhere else and precedes all other alphabet symbols in lexicographical ordering. A substring is formally classified as unique if it occurs exactly once within the text, excluding the terminal symbol so that suffixes do not trivially qualify as unique. A shortest unique substring is defined as a unique segment containing no proper substring that is also unique.
The specific focus of the study centers on left-bounded shortest unique substrings, where the search is anchored to a designated starting index. For any given position within an input text, the left-bounded shortest unique substring represents a contiguous segment starting at that index that occurs exactly once across the sequence, such that no shorter prefix beginning at that position is unique. Solving this task requires generating an integer array of equal length to the input, in which each entry records the exact length of the left-bounded shortest unique substring originating at that index, or records zero when no unique substring exists. Because any proper prefix of a left-bounded shortest unique substring must appear multiple times elsewhere, the length of the unique segment is inherently governed by the longest common prefix shared between the corresponding suffix and adjacent suffixes in the lexicographically ordered suffix array.
Prior algorithmic attempts to compute left-bounded shortest unique substrings have steadily reduced theoretical time complexity and practical space requirements over several decades. Pei and colleagues initially resolved the problem in quadratic time using suffix trees, an approach that became computationally prohibitive as biological dataset sizes expanded. Subsequently, Ileri and collaborators reduced execution time to linear complexity by utilizing two auxiliary integer arrays to store both the suffix array and the longest common prefix array, termed IKX-LSUS. However, IKX-LSUS required a substantial peak memory footprint of thirteen bytes per character under thirty-two-bit integer representation and twenty-five bytes per character under sixty-four-bit architectures. Hon and coauthors later developed an alternative linear-time approach, designated HTX-LSUS, that eliminated explicit precomputation of the longest common prefix array. By computing prefix lengths using Kasai’s algorithm and overwriting the inverted suffix array, HTX-LSUS reduced memory requirements to nine bytes per character.
Aguiar and Louza achieved their practical speedup by fundamentally re-engineering the permuted longest common prefix algorithm, known as the Phi-algorithm, to compute left-bounded shortest unique substrings directly. Rather than constructing the permuted longest common prefix array as an intermediate output, the authors established a mathematical formulation expressing left-bounded shortest unique substring values directly through relationships between the Phi-array and permuted longest common prefix values. In their theoretical framework, the required segment length at any suffix position is determined by taking the maximum common prefix shared with its immediate lexicographical predecessor and successor in the suffix array. Because the Phi-array maps each suffix to its predecessor, the researchers demonstrated that common prefix lengths can be computed in text order and immediately translated into candidate substring lengths, allowing intermediate values to be stored, updated, and overwritten without ever retaining the entire permuted longest common prefix structure in working memory.
The mechanics of the resulting procedure, designated Algorithm 1, operate using two auxiliary integer arrays across a sequence of carefully structured traversals. The first array initially stores the precomputed suffix array and is progressively overwritten to contain the final left-bounded shortest unique substring lengths, while the second array holds the Phi-array. The algorithm initializes all output positions to negative one, signifying that no comparisons have yet occurred, and sets an initial prefix comparison length tracker to zero. An outer loop then traverses the input text sequentially from the first character to the last. At each position, the algorithm retrieves the index of the preceding suffix from the Phi-array and determines the longest common prefix length between the current suffix and its predecessor. If the target positions are empty, this value is stored; otherwise, the algorithm calculates the candidate unique length by taking the maximum between the stored and newly computed values.
A crucial element guaranteeing theoretical linear time complexity and computational efficiency is the preservation of comparison skips adapted from the original Phi-algorithm. Because consecutive suffixes in text order share substantial character overlap with their respective predecessor suffixes, the length of the common prefix for any suffix is guaranteed to be at least one character less than the prefix length computed for the preceding position. By decrementing the comparison length counter and using it as a starting threshold rather than restarting character comparisons from scratch, the algorithm bounds total character comparisons to linear time, adding only constant-time operations per iteration. Special boundary cases are handled explicitly: when a suffix is the first lexicographical entry in the suffix array, its preceding pointer is zero and its left-bounded shortest unique substring length evaluates to zero; additionally, an appended terminal symbol ensures that the final suffix in the suffix array receives its completed calculation.
To evaluate practical performance, the authors conducted empirical testing on a dedicated workstation equipped with an AMD Ryzen 9 7900 central processing unit, 128 gigabytes of random-access memory, and four terabytes of solid-state NVMe storage running Fedora Linux. The ANSI C implementations of the proposed algorithm, HTX-LSUS, and IKX-LSUS were benchmarked under identical conditions, with running times tracked using the standard C clock function and peak memory measured through the malloc_count monitoring library. The evaluation utilized diverse datasets from the Pizza and Chili corpus, incorporating highly repetitive text collections such as einstein-de, kernel, fib41, and cere, alongside a one-gigabyte excerpt of standard English text. Furthermore, the experiments incorporated real biological datasets of significant scale: the complete telomere-to-telomere assembly of the human genome, designated HS-T2T, and a concatenated dataset of assembled SARS-CoV-2 viral sequences, all utilizing linear-time suffix array construction via SACA-K.
The empirical experimental results demonstrated that the proposed algorithm was the fastest alternative across almost all evaluated datasets, running on average 1.93 times faster than HTX-LSUS and 2.03 times faster than IKX-LSUS while maintaining an identical minimum peak memory consumption of nine bytes per input byte for thirty-two-bit integers and seventeen bytes for sixty-four-bit integers. Across the SARS-CoV-2 benchmark, IKX-LSUS failed to execute on sequences exceeding two to the thirty-second power bytes due to its heavy memory requirement of twenty-five bytes per character, whereas the proposed method processed the full dataset without failure. The only observed performance exception occurred on the pitches dataset, where execution speeds varied slightly. Concluding their study, Aguiar and Louza highlighted that their linear-time framework delivers substantial performance gains for large-scale bioinformatics applications and posed an open theoretical question asking whether left-bounded shortest unique substrings can ultimately be computed in linear time using only one memory word plus one byte per input character.
Subject of Research: Algorithmic string processing and linear-time left-bounded shortest unique substring computation
Article Title: Faster computation of left-bounded shortest unique substrings
Article References: Aguiar, L. L. M., & Louza, F. A. (2025). Faster computation of left-bounded shortest unique substrings. Algorithms for Molecular Biology, 20(1), Article 11. https://doi.org/10.1186/s13015-025-00287-5
Image Credits: AI Generated
DOI: 10.1186/s13015-025-00287-5
Keywords: string processing, bioinformatics, shortest unique substrings, PCR primer design, suffix array, linear time algorithms, computational biology, genomics, Faster, computation, left-bounded, shortest
News Source: Gregory Coleman. (November 9, 2026). New Linear-Time Algorithm Doubles Computation Speed for Left-Bounded Shortest Unique Substrings. Scienmag.
