MOTIVATION: Multiplex PCR-based enrichment is widely used in viral genome sequencing and pathogen surveillance. However, designing large sets of primers that maximize genome coverage while minimizing primer-primer interactions remains a major computational challenge. Existing methods such as SADDLE and Olivar use heuristics to optimize a Badness score for primer dimers but lack theoretical guarantees on solution quality. RESULTS: We introduce PRISM, a new framework that formulates multiplex primer design as a constrained submodular maximization problem. Our method defines an objective that balances genome coverage and dimer risk, and applies a local search algorithm with a constant-factor approximation guarantee. Evaluations on viral genome datasets demonstrate that PRISM consistently achieves lower Badness scores compared to PrimalScheme, Olivar, and primerJinn. These results highlight the scalability and theoretical rigor of submodular optimization in primer design. AVAILABILITY: PRISM is open-source and available at https://github.com/yhhan19/PRISM-new. The experimental data, scripts, and results used in this paper are archived on Figshare at https://doi.org/10.6084/m9.figshare.32806499.

The FM-index is one of the main success stories of the field of compact data structures and is a key part of many important tools in bioinformatics. Its primary weakness is a lack of access locality, with each step in a backward search typically causing several cache misses. If the indexed text is more than about lg σ times the size of cache, where σ is the size of the alphabet, then the bitvector at each level of the wavelet tree over the Burrows-Wheeler Transform (BWT) of the text may by itself be larger than cache — causing a cache miss as we descend from each level of the wavelet tree to the next. The resulting slowdown can be enough to cause practitioners to switch from FM-indexes to compressed suffix arrays, which have somewhat better locality.

In this paper, we present an algorithm for constructing the Lempel-Ziv 77 (LZ77) factorization using prefix-free parsing, an algorithm that was first developed as preprocessing algorithm for constructing the Burrows-Wheeler transform and the suffix array for input text. It was then demonstrated that the output of prefix-free parsing can be an effective data structure that emulates a compressed suffix tree (CST). PFP-LZ77 marries this data structure with the algorithm proposed by Karkkäinen et al. [CPM 2013]. In particular, we implemented a modification of the primitives used to support CST operations to enable previous smaller value and next smaller value queries on the suffix array of the text. This allow PFP-LZ77 to exploit the repetitiveness of the text, while building the LZ77 parse. We show that PFP-LZ77, SE-KKP, and ReLZ were the only methods capable of scaling to large datasets (e.g., 1024 copies of chromosome 19). And although SE-KKP and ReLZ performed well, SE-KKP was between 2.5 and 5 times slower, and used between 3 and 11 times more memory than PFP-LZ77 for reasonably large datasets (i.e., more than 16 copies of chromosome 19), and ReLZ only generates an LZ77 approximation. Our implementation is available at https://github.com/AaronHong1024/PFP_LZ77.

FM-indexes are a crucial data structure in DNA alignment, for example, but searching with them usually takes at least one random access per character in the query pattern. Ferragina and Fischer [5] observed in 2007 that word-based indexes often use fewer random accesses than character-based indexes, and thus support faster searches. Since DNA lacks natural word-boundaries, however, it is necessary to parse it somehow before applying word-based FM-indexing. Last year, Deng et al. [3] proposed parsing genomic data by induced suffix sorting, and showed the resulting word-based FM-indexes support faster counting queries than standard FM-indexes when patterns are a few thousand characters or longer. In this paper we show that using prefix-free parsing-which takes parameters that let us tune the average length of the phrases-instead of induced suffix sorting, gives a significant speedup for patterns of only a few hundred characters. We implement our method and demonstrate it is between 3 and 18 times faster than competing methods on queries to GRCh38. And was consistently faster on queries made to 25,000, 50,000 and 100,000 SARS-CoV-2 genomes. Hence, it is very clear that our method accelerates the performance of count over all state-of-the-art methods with a minor increase in the memory. The source code for PFP-FM is available at https://github.com/marco-oliva/afm.