Automated Design of Oligopools and Rapid Analysis of Massively Parallel Barcoded Measurements Authors: Ayaan Hossain, Daniel P Cetnar, Travis L LaFleur, James R McLellan, Howard M Salis Published: 2024 ABSTRACT AbstractOligopool synthesis and next-generation sequencing enable the construction and characterization of large libraries of designed genetic parts and systems. As library sizes grow, it becomes computationally challenging to optimally design large numbers of primer binding sites, barcode sequences, and overlap regions to obtain efficient assemblies and precise measurements. We present the Oligopool Calculator, an end-to-end suite of algorithms and data structures that rapidly designs many thousands of oligonucleotides within an oligopool and rapidly analyzes many billions of barcoded sequencing reads. We introduce several novel concepts that greatly increase the design and analysis throughput, including orthogonally symmetric barcode design, adaptive decision trees for primer design, a Scry barcode classifier, and efficient read packing. We demonstrate the Oligopool Calculator’s capabilities across computational benchmarks and real-data projects, including the design of over four million highly unique and compact barcodes in 1.2 h, the design of universal primer binding sites for one million 200-mer oligos in 15 min, and the analysis of about 500 million deep sequencing reads per hour, all on an 8-core desktop computer. Overall, the Oligopool Calculator accelerates the creative use of massively parallel experiments by eliminating the computational complexity of their design and analysis.Keywords: automated design, massively parallel reporter assay, oligopools, barcodes, deep sequencing, genetic parts Introduction Massively parallel DNA oligonucleotide synthesis has transformed synthetic biology and gifted it with economies of scale.1−2 Several commercially available services provide the custom synthesis of thousands of DNA oligonucleotides with researcher-defined sequences, mixed together in pools that are commonly known as oligopools. Oligopools are becoming more widely used as the starting DNA material to construct large libraries of genetic systems, while also facilitating the tracking and quantification of each genetic system’s function through DNA barcoding. These technologies have already dramatically increased the scale, breadth, and precision of quantitative measurements, which have been leveraged across several applications to greatly push forward the state-of-the-art in Synthetic Biology.3 For example, synthetic biologists have leveraged oligopools to design and build large libraries of promoters,4−6 hammerhead ribozymes,7 biosensors,8 genetic circuits,9 protein scaffolds,10 therapeutic molecules,11 and RNA-based devices,12 followed by characterizing their functions using massively parallel reporter assays (MPRAs). MPRAs combine sequence-encoded readouts with next-generation sequencing (NGS) to quantify cell library compositions and measure mRNA and protein levels.13−16 By enabling the construction and characterization of large numbers of genetic systems, the resulting data sets have been applied to determine the sequence determinants of several biological processes, including transcription initiation,6,17,18 mRNA decay,19 eukaryotic translation initiation,20 and alternative transcript polyadenylation.21 Large-scale CRISPR libraries have also been constructed using oligopool synthesis and screened using MPRAs,22−24 while oligopool synthesis has been harnessed for storing information in DNA-based files.25 As oligopool technology development has accelerated, the number and maximum length of oligonucleotides in an oligopool continue to increase, while the material costs of manufacturing oligopools have greatly decreased, mirroring the supraexponential improvements in NGS technology. Thus, we expect that oligopools will continue to be leveraged to build large genetic system libraries coupled to MPRAs for quantitative characterization. However, the design of oligopool sequences and their analysis after MPRA characterization remain highly challenging and often bespoke efforts across individual projects, motivating the development of a software pipeline that is specially designed to accelerate these efforts. While there are several algorithms for designing related parts and tasks, they were often developed with prior applications in mind and do not take into account the massive increase in throughput and sequence complexity needed to design an oligopool and analyze its MPRA data. For example, IDT SciTools,26 Primer3,27 and PrimerMapper28 are well-developed software packages for designing pairs of PCR primers to amplify existing DNA templates. Primerize29,30 can split a single long construct into shorter oligo fragments. FreeBarcodes,31 DNABarcodes,32 and BARCOSEL33 provide DNA barcode libraries and barcode sequence design algorithms.34 SiteOut35 designs spacer sequences without forbidden motifs. Kallisto,36 HISAT2,37 and salmon38 accurately map and count transcriptomic reads for studying differential gene expression. However, to date, there are no algorithms that can rapidly design ultraspecific PCR primer binding sites and primers across megabases of custom sequence, while incorporating sequence, structural, and model-based constraints needed for efficient PCR amplification, DNA assembly, and MPRA characterization. Existing barcode libraries and design algorithms are decoupled from the overall oligopool design and analysis, though there are several workflow-wide constraints that must be satisfied, including ensuring minimum distinguishability criteria and the prevention of edge effects. Finally, the quantitative analysis of deep amplicon NGS libraries becomes computationally rate-limiting when files contain billions of reads across many thousands of barcoded variants. New algorithms are needed to rapidly design the many thousands of oligonucleotide sequences within an oligopool while coupling both design and analysis tasks so that the resulting NGS data may be rapidly analyzed with high quantitative precision. We introduce the Oligopool Calculator as a suite of design and analysis algorithms that enable the design of oligopool sequences (Design Mode) and the analysis of next-generation sequencing data from massively parallel reporter assays (Analysis Mode). In Design Mode, the algorithm designs barcodes, primer binding sites, primers, padding, spacers, and splits to facilitate the massively parallel PCR, DNA assembly, and cloning workflows used to build many thousands of genetic systems from a single oligopool (Figure 1A). Several workflow-wide criteria are mutually satisfied throughout the design of individual parts and the collective system. Barcode sequences are designed to be maximally distinguishable with a user-defined minimum pairwise Hamming distance so that NGS base calling error does not lower the precision of the MPRA measurements. Primer binding sites and primers are designed for maximum specificity and efficiency during PCR, which includes precise matching of primer melting temperatures, eliminating all off-target binding, eliminating inhibitory DNA structures, and greatly reducing primer dimer formation. Padding sequences are designed to ensure uniform oligopool synthesis, PCR amplification, and DNA assembly. In multifragment mode, long DNA assemblies are automatically split into multiple oligonucleotide fragments with optimally selected overlap regions for in vivo homology-directed, Golden Gate, PCR, or Gibson assembly.39−42 Design and analysis of oligopool variants using the Oligopool Calculator. (a) In Design Mode, oligonucleotide sequences are designed with optimized barcodes, primer binding sites, padding, and spacers. Longer constructs may also be split into shorter oligos for multifragment assembly. (b) In Analysis Mode, barcode indexing, mapping, and counting are carried out on billions of reads to quantify variant frequencies, which are used to measure cell library composition and genetic system activities. In Analysis Mode, the Oligopool Calculator rapidly and efficiently carries out the analysis of deep amplicon sequencing libraries from MPRAs to quantitatively measure the frequency of each genetic system variant within the pooled library (Figure 1B). Analysis Mode is used to (i) index genetic system variants and their associated barcodes, (ii) filter, merge, and compress NGS reads into smaller read packs, and (iii) accurately map barcodes and count their occurrences from the packed read files. Both association and combinatorial counting are supported, enabling each genetic system variant to be associated with a single designed barcode sequence or a combination of multiple designed barcode sequences. Sequence matching is performed to quantify any deviation from expected sequences with reporting of mismatch distributions. The resulting count matrices are analyzed to measure genetic system activity across conditions of interest and can be combined with biophysics and/or machine learning to develop predictive sequence-to-function models. Altogether, in the following results, we demonstrate how the Oligopool Calculator was used across several recent MPRA projects, carry out computational run-time and memory benchmarks to show-case its extremely fast design and analysis throughput, and formally explain how the algorithms are able to deliver unprecedented speed and accuracy. The Oligopool Calculator is available at https://github.com/hsalis/SalisLabCode and https://github.com/ayaanhossain/oligopool under a GPLv3 open-source license. Results and Discussion Design of Oligopools to Build Genetic Part Libraries We begin with three concrete examples of how the Oligopool Calculator was used to design high-complexity oligopools containing several thousand oligonucleotides (Figure 2). In the first example, we designed and constructed 93,180 promoters with systematically varied sequence motifs, which was used to develop predictive models of transcription initiation rate, called the Promoter Calculator6 and the Multi-Sigma Promoter Calculator (Figure 2A). The promoter variants are surrounded by several genetic parts that facilitate PCR, cloning, and characterization. The outer flanking regions contain an ultraspecific universal primer binding site, followed by flanking BamHI and HindIII restriction sites for digestion and ligation into a compatible vector. Next, the promoter variant is physically coupled to a unique barcode sequence. Barcode sequences were designed so that they could be uniquely distinguished even if they contained up to 6 mismatches or base calling errors. Finally, a pair of EcoRI and SpeI restriction sites facilitates a 2-step cloning procedure that enables the insertion of a long constant region in between the promoter variant and its corresponding barcode. In the final constructed systems, each designed promoter controls the transcription rate of a mRFP1 coding sequence with a designed ribosome binding site sequence that has a translation initiation rate of about 5,000 au on the RBS Calculator v2.1 scale43−46 (Figure 2B). Notably, the 2-step cloning procedure shifts the barcode position into the 3′ untranslated region so that it cannot affect the transcription initiation rate. Demonstrative examples of oligopool design to build genetic part libraries. (a) An oligopool architecture with 93,180 designed promoter variants and the (b) genetic system where promoters are inserted to measure their bacterial transcription initiation rates. (c) An oligopool architecture with 62,120 mRNA stability elements and the (d) genetic system where sequences are inserted to measure their mRNA decay rate in bacteria. (e) An oligopool architecture with 6,232 designed ribozymes, double barcodes, and triple primer binding sites and the (f) genetic system where ribozymes are inserted to measure their self-cleavage rate. In the second example, we designed and constructed 62,120 5′ untranslated regions to systematically determine the interactions that control bacterial mRNA decay rates (Figure 2C). We used a similar oligopool architecture as in the first example, although the optimal PCR primer binding sites were longer, while the barcode sequences were shorter, all while satisfying optimal design criteria. The restriction sites and enzymes used for the 2-step cloning procedure were different, though the Oligopool Calculator was able to rapidly design the needed primer binding sites, barcodes, and spacers, taking into account these changes. In the final constructed systems, the mRNA stability elements were introduced downstream of a constant promoter and followed by a sfGFP coding sequence (Figure 2D). In the third example, we designed and constructed 6,232 highly nonrepetitive hammerhead ribozymes, which increase mRNA stabilities and act as insulators within engineered genetic systems with many genetic parts (Figure 2E). The ribozymes were designed using Non-Repetitive Parts Calculator4 to have a maximum shared repeat length of only 16 nucleotides, which enables them to be all be used simultaneously without inadvertently triggering homologous recombination. We used a 2-barcode strategy to measure the ribozymes’ self-cleavage efficiencies, preparing two different barcoded amplicon libraries to quantify the amounts of cleaved versus full-length mRNAs. Here, the BC2 barcode counts are proportional to the total number of transcribed mRNAs, whereas the BC1 barcode counts are proportional to the number of full-length (uncleaved) mRNA. By incorporating internal controls into the part library, these barcode counts can be normalized and compared, yielding the ribozymes’ self-cleavage efficiencies. This application illustrates how multiple barcode sequences can be incorporated into an oligopool to quantify genetic part activities. Importantly, the Oligopool Calculator’s analysis mode can track and remove artifacts that occur when longer amplicons are sequenced, using its multibarcode combinatorial mapping. For example, when sequencing long amplicons, a small percentage of reads will contain mispaired barcodes (called “index hopping”), which are identified during mapping and removed during counting. More generally, the Oligopool Calculator is highly versatile and can be applied to design oligopools and analyze deep sequencing reads with diverse architectures. For example, combinatorial genetics en mass (CombiGEM) uses combinatorial DNA assembly to construct large toolboxes of genetic designs or screens, utilizing tandem arrays of DNA barcodes to uniquely identify each design.47−49 The Oligopool Calculator can design tandem barcode arrays and analyze multibarcode reads, enabling tracking and quantification of genetic designs for studying gene regulation, biosensor development, or metabolic pathway engineering.50−52 Optimal Design of Barcodes, Primer Binding Sites, Spacers, and Overlaps The Oligopool Calculator’s design mode carries out custom sequence design of barcodes, primer binding sites, primers, spacers, and overlap regions using newly developed algorithms that generate solutions that satisfy all workflow-wide constraints while being extremely fast and memory-efficient. For example, designing an oligopool with one million sequence variants takes about 35 min on a typical desktop computer, depending on the oligopool architecture (Figure 3). Below, we describe each design algorithm and measure their effectiveness via several benchmarking tasks. Oligopool cCalculator dDesign mMode bBenchmarks. (a) The computational runtime of designing an oligopool containing two primer binding sites, one barcode, and one spacer, using a single 3.5 GHz Intel processor on a desktop computer with 64 GB RAM, showing that runtime scales quadratically. (b) The computational memory (RAM) needed to design an oligopool scales linearly with the oligopool size. Dots and bars are the mean and standard deviation of 10 independent runs. Barcodes Barcodes in an oligopool are used to uniquely identify each variant and quantify each variants’ frequency in a sample. Barcodes are critical for properly tracking variants, especially when the variants have similar sequences. There are four key criteria for designing barcodes. First, there must be at least one barcode per variant, which dictates the number of barcodes that must be designed for the oligopool. Second, barcode sequences must be uniquely mappable with a tunable level of distinguishability, as determined by the expected base calling error during next-generation sequencing. Distinguishability is quantified globally by the minimum pairwise Hamming distance across all barcode sequences. Hamming distance is the number of mismatched nucleotides between two pairs of same-length barcodes. Third, the barcode length must be long enough to satisfy the first two design criteria, but not any longer, as oligonucleotide lengths are currently limited by synthesis processivity and space on the oligonucleotide remains scarce. Finally, all barcode sequences must not contain homopolymer tracts that are challenging to sequence while also excluding a set of researcher-defined sequences, such as restriction sites, that are necessary to facilitate cloning. The barcode design algorithm generates an optimal set of barcode sequences that satisfy all four design criteria, custom tailored to the oligopool library and a researcher-defined level of minimum distinguishability (Methods section, Figure 4A). For example, when sequencing an oligopool with 10-nt barcode sequences using Illumina NovaSeq, we expect a base calling error of 0.1%, yielding 0.991% of barcodes with a 1-nt mutation and 0.004% of barcodes with a 2-nt mutation.53 A minimum pairwise Hamming distance (Hmin) of 2 would uniquely distinguish 99.996% barcode reads. However, when sequencing the same oligopool using Oxford nanopore sequencing, we expect a base calling error of 0.5%, yielding 4.8% of barcodes with a 1-nt mutation, 0.1% of barcodes with a 2-nt mutation, and 0.001% of barcodes with a 3-nt mutation.54 Here, a Hmin of 2 would uniquely distinguish 99.9% of barcode reads, while a Hmin of 3 would improve the distinguishability to 99.999%. Designing a larger number of barcodes with higher minimum pairwise Hamming distances is a challenging computational task, especially when constrained to shorter barcode sequences. Barcode and primer design algorithms. (a) Barcode design algorithm schematic showing the selection of initial candidate set of four linked barcodes, and filtering them based on Hamming distance, excluded motifs, contextual nonrepetitiveness, and edge effects. All pair barcode Hamming distance distribution for (b) promoter oligopool, (c) mRNA stability element oligopool, and (d) nonrepetitive ribozyme oligopool barcode sets. (e) Primer design algorithm schematic showing the use of Non-Repetitive Parts Calculator to design primers based on a desired sequence constraint that is free of excluded motifs and edge effects when assigned to any context, and possess a desired level of nonrepetitiveness between the primer, the oligopool and background sequences. Designed primers also do not form stable hairpins or strong duplexes between paired primers and have a desired melting temperature. Examples of weak (f) homodimer formation between two copies of the first forward primer, and (g) a comparison between on-target primer binding and the distribution of off-target primer binding for the nonrepetitive ribozyme oligopool architecture. Barcode design takes place in a transformed integer space where each barcode sequence of length L is represented by an integer . In a loop, we generate M barcode sequence candidates by splitting the integer space into M partitions, randomly selecting an integer from the first partition and leveraging the M-way symmetry of the design space to select M–1 additional DNA barcodes that are highly distinguishable. We then decode the integers as base-4 numbers and convert them back to DNA sequences. For example, if L = 5 and M = 4, the integer space spans 0 to 1,023 and the partitions are 256 integers each. The initial random selection is x1 = 198, which controls the selection of integers in the remaining 4 partitions, according to x2 = 4L – 1 – x1 = 825, x3 = 4L/2 + x1 = 710, and x4 = 4L/2 – 1–x1 = 313. These integers when converted to DNA sequences are ATACG, TATGC, GTACG, and CATGC, showing the symmetry of dispersed selection in reverse compliment space. This approach enables very rapid generation of candidate barcode sequences even when L and M are large. In the next few steps, barcode candidates are removed if they do not satisfy all of the design criteria. The first filter is to remove any barcode candidate that contains excluded sequences, such as restriction cut sites or polymeric runs. The second filter is to efficiently calculate the pairwise Hamming distances across all barcode candidates, using multithreaded array broadcasting techniques,55 and then remove any barcode candidate that does not meet the Hmin threshold. Finally, we consider the potential edge effects of placing a candidate barcode adjacent to an upstream or downstream sequence within its designated position within an oligonucleotide (SupplementaryFigure 1). We loop through each oligonucleotide in the oligopool and assign a barcode sequence to each position only if the edge effects do not invalidate the design criteria. Barcode generation continues until all oligonucleotides have an assigned barcode sequence that meets the four design criteria. Altogether, this barcode design algorithm saturates the k-mer spectrum and ensures that the terminal ends of each barcode have maximally dissimilar sequence. Importantly, the algorithm is especially efficient at reducing the computational run time for the most intensive task of the design process, which is ensuring a minimum pairwise Hamming distance across all barcode sequences. First, the symmetry of the candidate barcode selection algorithm ensures that every initially generated barcode sequence is about (L – M) Hamming distance apart. Second, it is straightforward to track the previously generated candidate barcodes and ensure the selection of new candidate barcodes to preclude double-work. Third, the pairwise Hamming distances only need to be calculated for the newly generated candidate barcodes. In practice, the algorithm completes very quickly, taking less than 10 min for each of the three oligopool examples (Figure 2, Supplementary Table 1). The distributions of the pairwise Hamming distances (Figure 4B,C,D) as well as the distributions of the pairwise edit distances (SupplementaryFigures 2, 3, 4) for these designed barcodes met and greatly exceeded the design criteria. The 20-bp barcodes had about 15 mismatches on average; the 15-bp barcodes had about 11 mismatches on average; and the 11-bp barcodes had about 8 mismatches on average. Importantly, the lowest value of the pairwise Hamming distance in the distribution always exceeded or met the researcher-defined minimum value (1 to 3, depending on the oligopool design). At the extremes, the algorithm only needed 72 min to design 4,194,304 14-nt barcode sequences with a Hmin of 2; when increasing the Hmin to 3, the same barcode design procedure required 523 min (Supplementary Table 1). Primer Binding Sites PCR is routinely used to selectively amplify oligopools, converting the mixture of single-stranded DNA oligonucleotides into double-stranded DNA fragments. However, PCRs on oligopool templates are more challenging and require more careful design of the primers and primer binding sites to avoid mis-priming, low PCR efficiency, and primer dimer formation. The Oligopool Calculator generates pairs of primers and primer binding sites with target length (14 > L > 23) that satisfy 7 important design criteria. Designed sequences must not contain any researcher-defined excluded sequences, such as restriction sites and homopolymeric tracts, including edge effects (rule #1). Pairs of primers must have matching DNA melting temperatures (e.g., with a difference smaller than 0.3 °C) within a research-defined range (rule #2). Primers must not strongly bind to any undesired sites on the DNA template, which is achievable by ensuring that all primer sequences have more than (L–10) mismatches to any potential binding site (rule #3). Single-stranded primers must not fold into any stable secondary structure (ΔGfold ≥ 0 kcal/mol) that would inhibit template binding and PCR (rule #4). The 3′ ends of both primer sequences must be either an A or a T to weaken primer dimer structures that could result in strand extension and PCR amplification (rule #5). Finally, the two primers must not bind to each other and form competitively stable structures (ΔGdimer ≥ −7 kcal/mol), including homodimer and heterodimer structures (SupplementaryFigures 5, 6, 7), that would again inhibit template binding and PCR (rules #6 and #7). While some of these design criteria are well-known to the field, the Oligopool Calculator combines model-based path generation and k-mer hash tables to very rapidly generate primer solutions even when oligopools are complex. Pairs of universal primers were designed for each of our real-world oligopool examples (Figure 1) in fewer than 30 s (Supplementary Table 1), satisfying all design rules. At the extreme, the Oligopool Calculator only required 816 s to design a pair of universal primers for a million 200-mer oligonucleotides (equivalent to 200 Mbp of template DNA) (Supplementary Table 1). To do this, we leverage our previously developed Non-Repetitive Parts Calculator algorithm,4 which designs large toolboxes of genetic parts that do not contain any k-mers that match to either another genetic part in the toolbox or to an inputted “background” sequence. Here, the background sequence is the list of oligonucleotides in the oligopool DNA template (before the primer binding sites are added) as well as any other input template DNA sequence that must be avoided (e.g., the genome sequence of E. coli, which can appear as contaminant DNA in many laboratories). The Non-Repetitive Parts Calculator accepts sequence, structure, and function constraints, which are applied during path generation to avoid excess loss-of-work. We then use the Non-Repetitive Parts Calculator to generate a large number of candidate primer sequences with a maximum repeat length of 10 nucleotides, while applying sequence constraints to ensure rule #5, single-stranded DNA structure constraints to satisfy rule #4, and a string-matching function to ensure rule #1. The resulting toolbox of candidate primers satisfy rule #3 by construction. We then calculate the DNA melting temperatures of each candidate primer and pair primers together when they satisfy rule #2. For every candidate pair of primers, we use ViennaRNA56 to calculate their homodimer and heterodimer minimum-free-energy structures, discarding any primer pairs that break rules #6 and #7. This procedure continues until at least one pair of primers has been generated or until a counter has been exceeded. These calculations are carefully ordered so that less expensive operations (e.g., k-mer collisions) take place before more expensive operations (e.g., calculating DNA structures) during path generation and tracebacks (Methods section, Figure 4E). The sequences and orientations of the designed primers are then used to determine their corresponding primer binding sites within the oligopool. This design procedure results in highly specific primers with extremely low off-target binding to the oligopool template (Figure 4G, Supplementary Figure 8). Restriction Sites, Motifs, and Spacers The Oligopool Calculator’s design mode can introduce restriction sites, researcher-defined sequence motifs, and spacer regions into the oligopool design, while ensuring that they maximally satisfy the workflow-wide design rules. These sequences are defined using the IUPAC degenerate nucleotide code with an option to set the length of a spacer region to an oligonucleotide-specific value, making them useful as padding elements or anchor sequences used to define barcode positions. During sequence design, the Oligopool Calculator’s pathfinding algorithm evaluates the input specifications and identifies an oligonucleotide-specific sequence solution that satisfies design rule #1, preventing the appearance of researcher-defined excluded motifs and homopolymer tracts (including edge effects from oligonucleotide-specific flanking sequences). The design process is very fast; for example, designing the spacer regions for 93,180 oligonucleotides required only 6.8 s (Table S1). Splits and Overlap Regions While maximum oligonucleotide synthesis lengths continue to improve, there will always be genetic designs that are too long to fit within one oligonucleotide. One solution is to split the genetic design into multiple overlapping oligonucleotides and apply either in vitro enzyme assembly or in vivo recombination to build the full genetic system. The Oligopool Calculator facilitates this process by selecting the optimal split points and overlap regions within a long genetic system design with the overall goals of maximizing the sequence-specificity of the overlap regions, while ensuring that the overlap regions have a DNA melting temperature above a minimum set point. Both the DNA melting temperature and sequence specificity of the overlap region are important when using any DNA assembly technique that uses many Watson–Crick base pairings to determine the assembly order and ligation fidelity, which includes in vitro PCR assembly, in vitro Gibson assembly, and in vivo homologous recombination. For example, we previously applied the Oligopool Calculator to build 1,722 yeast promoters with a 325-bp variable region by splitting each design into a pair of designed 200-nt oligonucleotides with a 20-nt overlap region, yielding an oligopool of over 3,444 oligonucleotides.4 The overlap regions all had DNA melting temperatures above 50 °C. In this example, DNA assembly was carried out via in vitro one-pot PCR assembly, followed by genome integration via multifragment in vivo recombination inside yeast cells with both positive and negative selection. To do this, the Oligopool Calculator first carries out a left-alignment of all the genetic designs, adding padding sequence to the 3′ terminal ends where necessary to achieve uniformity, followed by calculating the number of oligonucleotides needed to build them, according to researcher-defined oligo specifications (Methods section, Figure 5A). The algorithm then calculates the Shannon entropy for each aligned position along the genetic design axis to identify the sequence regions that have the highest variability. The algorithm then selects a set of optimal sequence regions that have maximal lengths (limited by the maximum oligonucleotide length) with overlap sequences that have maximal entropy. Once the optimal set of splits is defined, the overlap region length is optimized. The overlap region length is varied uniformly for all assemblies to ensure that the overlap regions’ DNA melting temperatures are above a researcher-defined set point as well as to ensure that all pairs of overlap regions have Hamming distances above a minimum threshold. If the overlap region length exceeds a threshold (defined by the maximum oligonucleotide length), then the next most optimal set of splits is selected. Once this procedure is finished, the oligonucleotides are designed. If any terminal padding sequences were added during the alignment of the genetic system designs, then they are removed. Flanking restriction sites, motifs, and PCR primer binding sites are then added as described previously to facilitate PCR amplification and remove the PCR primer binding sites from the amplified DNA fragments. As another demonstration, we reran the Oligopool Calculator on the 1,722 yeast promoter regions and performed a four-way splitting of the genetic system designs into an oligopool with a maximum region length of 134 bp and using a minimum DNA melting temperature of 50 °C for the three overlap regions. The resulting split sets and overlap regions were found to have high DNA melting temperatures (Figure 5B) and with high pairwise Hamming distances (Figure 5C), satisfying the design rules for sequence-specific assembly. However, in order for this oligo splitting strategy to be successful, the genetic designs must have sufficiently long sequence regions with high sequence diversity, for example, by introducing nonrepetitive genetic parts or barcode sequences into the designs. Oligopool splitting and padding. (a) The Oligopool Calculator identifies optimal split sets and overlap regions for multifragment homology-based assembly. Overlap regions must have a minimum melting temperature and minimum pairwise Hamming distances. PCR primer binding sites, cut motifs, and spacers are then added to split regions to create oligonucleotides and oligopools. (b) The distributions of DNA melting temperatures are shown for three sets of designed overlap regions, satisfying a minimum DNA melting temperature of 50 °C. (c) The pairwise Hamming distance distributions are shown for three sets of designed overlap regions, showing high sequence variability between designed overlap regions. Rapid Analysis of Massively Parallel Measurements on Barcoded Genetic Systems While the Oligopool Calculator’s Design Mode carries out the automated design of oligopools to facilitate the construction of barcoded genetic systems, its Analysis Mode is responsible for rapidly analyzing next-generation sequencing data that measures the functions of those barcoded genetic systems. For example, an oligopool is designed, synthesized, and utilized to build a large library of plasmids that uses different regulatory or coding genetic parts to alter cell function (Figure 2). Barcodes are strategically positioned to provide a quantitative proxy measurement, which can include library composition, mRNA levels, or another coupled cell function (e.g., using a cell sensor, cell sorting, or growth-coupled enrichment). Cells are transformed with the plasmid library, grown in desired environmental conditions, and sampled across kinetic time points or during steady state. The DNA and mRNA from those cell samples are then processed and sequenced, using short-read sequencing or long-read sequencing, and yielding millions to billions of barcode-containing reads. The Oligopool Calculator analyzes these read files and very rapidly determines the barcode counts for each genetic system variant in the library, while reducing the effects of confounding factors that could alter barcode counts (e.g., assembly mutations or base-calling errors). To do this, the Oligopool Calculator carries out an automated procedure that includes: (i) automated training of an extremely robust barcode classifier, using a Scry machine learning model to quickly and accurately identify barcodes even if the sequence contains several mutations or base-calling errors; (ii) automated filtering, merging, and packing of reads, which greatly reduces storage sizes; and (iii) rapid counting of barcodes (in association or combinatorial modes) with the option of running barcode-dependent call-back functions on the genetic system’s sequence. Overall, Analysis Mode is extremely fast with throughputs of 180 to 720 million reads per hour on a typical 8-core desktop computer, depending on the sequencing format and number of barcodes (Tables S3, S4). Barcode Mapping To begin, the researcher inputs a list of expected (reference) barcode sequences for each barcode position in the genetic system library, as well as an anchor sequence that defines the locations of the barcoded positions. The anchor sequence is any constant sequence that has a constant distance from the barcode sequence, enabling rapid barcode mapping and counting. The anchor sequence does not need to be adjacent to the barcode but must be located within the same read during next-generation sequencing. The Oligopool Calculator then analyzes the reference barcodes and automatically generates a list of all uniquely identifiable barcode sequences including mismatches. These sequences are then stored in an efficient look-up table (Methods section, Figure 6A). The maximum pairwise Hamming distance across the reference barcodes is then calculated and used as the default tolerance for mismatches. Any nonunique reference barcodes are reported to the researcher. Indexing, packing, and counting of sequenced reads from oligopool characterization experiments. (a) Algorithm schematic for computing efficient indexes of barcodes, and associated variants, and training an accurate barcode classifier model. (b) Scry barcode classifier test results (blue lines) for the σ70 bacterial promoter oligopool barcodes show a mean of 99% area under the ROC curve score, compared to a baseline mean score of 91% (red lines). A total of 100 test cycles were conducted, with 10,000 barcodes tested in each iteration. (c) Schematic showing multicore packing of sequenced reads after filtering reads based on quality scores and read length and any optional merging or concatenation of paired reads. Each read pack then contains processed reads along with frequency counts of their occurrence within a batch. (d) Bar chart showing total number of amplicons samples sequenced at various time points (red bars) to characterize the mRNA stability element oligopool and the total number of unique reads after packing them efficiently (blue bars). (e) Algorithm schematic showing association and combinatorial counting of barcoded reads to produce count matrices. In association counting, the sequenced barcode is identified, and its association with the designed variant is verified. In combinatorial counting, multiple isolated barcodes, or various subbarcode combinations in the reads, are mapped and counted. (f) Bar chart showing the cleavage efficiency distribution of the nonrepetitive ribozyme library from sequencing characterization experiment. As a key innovation, we greatly accelerate barcode mapping by developing a novel classifier (called Scry) to rapidly and accurately predict the barcode label from an imperfect read sequence, including read sequences that contain several mismatches or indel mutations. Scry is a k-nearest neighbor classifier that uses the position-ordered k-mer motifs within an extracted barcode sequence to quickly identify its reference barcode sequence while being robust to multiple mismatches or indel mutations. For example, with k = 5, there are 16 ordered 5-mers in a 20-nt barcode sequence. If any two nucleotides in the read sequence are mutated or deleted, then anywhere from 6 to 10 of the 5-mers will be mutated, leaving 6 to 10 unaffected 5-mers as identifiers. The Scry classifier uses a rapid matching process to identify such unaffected k-mers and then utilizes them to uniquely identify the reference barcode or reject the sequence as nonidentifiable (Methods section). In greater detail, the Scry classifier first checks whether the barcode sequence extracted from a read is an exact match to the reference barcode sequence. If there is no exact match, the classifier decomposes the extracted barcode sequence into positioned k-mers, followed by carrying out a scored matching process that compares the positioned k-mers of the extracted barcode sequence to the positioned k-mers of all the reference barcode sequences. A match is favorably scored whenever matching k-mers have the same order of appearance, but not if matching k-mers appear out-of-order. The extracted barcode sequence is labeled as potentially arising from a reference barcode if it has the highest scoring match. This matching process is much faster than traditional gapped sequence alignment algorithms, particularly when (in our case) there are tens of thousands of reference sequences mapped across billions of reads while also being memory efficient. From the scored match process, the Scry classifier identifies a small set of reference barcode sequences that potentially match the extracted barcode sequence, greatly simplifying the identifiability challenge. The Scry classifier then identifies the highest matching reference barcode by carrying out a small number of pairwise alignments and calculating their edit distances, which is the total number of mismatches or indel mutations needed to convert one sequence to the other. The Scry classifier then uses the reference barcode sequence with the smallest edit distance to label the extracted barcode sequence. Importantly, the Scry classifier is robust to the presence of multiple mismatches or indel mutations without losing identifiability; however, if there are excess mutations, multiple reference barcodes will all have the same edit distance, enabling the Scry classifier to label the extracted barcode sequence as nonunique. We assessed the performance of the Scry classifier by performing barcode mapping on randomly mutated barcode sequences to determine how well they could be correctly labeled. We introduced between 2 and 6 random mutations (substitutions, insertions, or deletions) at random positions across 10,000 different reference barcode sequences and then applied Scry to predict the original reference barcode. We then repeated this test 100 times to determine the true and false positive rates. Overall, the average area under the receiver operating characteristic curve (AUROC) score for Scry barcode classification was over 99%, compared to an AUROC of 91% for a baseline classifier that only uses unordered k-mers (Figure 6B). Similarly, in our real-world examples, the Scry model had AUROC scores of 98% to 99% when carrying out barcode mapping on our example applications, as compared to 92% to 93% when using the baseline classifier (Supplementary Figure 9). The Scry classifier is computationally very fast. Index initialization only required about 0.2 s for 6,232 reference barcodes and about 2 s for 62,120 reference barcodes (Table S2). Barcode mapping with Scry has an exceptionally high throughput of over 1 billion reads per hour (Table S4) even when there are many thousands of reference barcodes. Read Merging, Filtering, and Packing The next key step is the processing of the next-generation sequencing reads, including read merging, filtering, and packing (Figure 6C). While read merging and filtering are commonly carried out,57−61 read packing is a simple, but novel, technique that greatly reduces computational storage requirements and accelerates the barcode mapping and counting process. First, the Oligopool Calculator assesses the reads in FastQ format for base calling accuracy (Q-score) and discards any reads with Q-scores less than a researcher-defined threshold. Reads that are substantially shorter than an expected researcher-defined length are also discarded. Next, the Oligopool Calculator automatically determines the best read merging parameters for paired-end reads, which may be overridden by researcher-defined options. The read merging parameters include the merge orientation, minimum overlap length, and maximum number of mismatches expected in the overlap region. For example, when reads have a strand orientation, paired-end reads can be merged in either the innie orientation (the overlap region is located on the 3′ ends of the reads) or the outie orientation (the overlap region is located on the 5′ ends of the reads). The overlap region’s length depends on the amplicon architecture. If no overlap exists, then the paired-end reads may be concatenated. The automated procedure samples 50,000 reads from the data set and determines the best merge parameters by counting successes across varied parameters and using their ranking for prioritization. The ranked list of parameters are then used to carry out read merging for the entire data set. For example, the Oligopool Calculator begins by using the highest ranked parameters to carry out read merging, but if unsuccessful, it then repeats the process using the next highest ranked parameters until success is achieved. This prioritized approach greatly reduces the computational cost of the read merging. However, if the provided FastQ file already contains filtered and merged reads, then the Oligopool Calculator provides an option to skip these steps. Finally, the Oligopool Calculator performs read packing to greatly accelerate the barcode mapping and counting process. When carrying out massively parallel experiments, we often collect next-generation sequencing results with very high read depths in order to obtain precise measurements. For example, one sequence variant might be read over 100,000 times, whereas another sequence variant might only be read 100 times. Overall, there will be many more reads than sequence variants even when considering that the number of unique variants will be much larger when including mutations or base calling errors commonly found in read sequences. Thus, by combining all of the same-sequence reads together into a single read pack, which contains within it the read sequence and the read count, we can greatly reduce the amount of work needed to extract barcode sequences and label barcode identifiers. For example, 438 million reads from the mRNA stability element library could be compressed into 101 million packs (a 4.3-fold reduction) (Figure 6D) while 81 million reads from the ribozyme library could be compressed into 11 million packs (a 7.4-fold reduction) (Supplementary Figure 10). Overall, the Oligopool Calculator carries out read filtering, merging, and packing with very high computational throughputs (181–270 million reads per hour with merging, 760 to 775 million reads per hour without merging) (Table S3). Several techniques are used to ensure that read processing is limited only by I/O throughput, even when using a typical multicore desktop computer (Methods section). Rapid Counting of Packed Reads The final step of the Oligopool Calculator’s analysis mode is to apply the Scry classifier on each barcode sequence within each read pack and compile a barcode count matrix that lists the number of times each reference barcode was found (Figure 6E). Two counting modes are available. When association counting is used, each reference barcode sequence is uniquely associated with a sequence variant. The generated output lists the number of times each reference barcode sequence was observed (counts), including the barcode’s unique identifier and the edit distance to the actual barcode sequence in the read. For example, the output will show the barcode counts for all perfectly matched barcode sequences (edit distances of 0), as well as the barcode counts of the imperfectly matched, but still uniquely identifiable barcode sequences (positive edit distances). The barcode mapping process checks for the correctness of the anchor sequences and the overall amplicon architecture; if there are too many mismatches (above a researcher-defined threshold), then the read pack is discarded and not counted. When combinatorial counting is used, the Scry classifier is applied to uniquely label each barcode sequence in the read pack and count the number of times each combination of reference barcodes are observed. Multiple barcodes can appear anywhere inside the read sequence, in either adjacent or distance locations, as defined by the researcher during the indexing step. The generated output lists the number of times each combination of reference barcode sequences was observed (counts). Missing barcodes are labeled as null values and treated as potential combinations, enabling their quantification for quality control. In both counting modes, barcode sequences are extracted from reads by using the inputted anchor sequences and anchor-barcode distances to carry out a minimal, rapid alignment, followed by Scry classification and counting. At this step, the Oligopool Calculator can call a researcher-defined custom callback function, using the identified reference barcodes and read sequence as inputs, and tally the function’s results in dictionary format. This optional callback function can be used to calculate another property of the genetic system variant that is found within the read pack, for example, identifying transcription start sites, RNA cleavage locations, or mutated amino acids. The callback function may also be used to apply additional quality control filters, such as discarding concatemer reads. If the Scry classifier fails to find any expected barcode sequence, then the Oligopool Calculator will automatically analyze the read sequence and determine if it contains PhiX genomic DNA or a low-complexity sequence. PhiX DNA is often added to deep amplicon libraries before sequencing, while low-complexity sequences are often generated if overclustering or color saturation takes place during sequencing. The amounts of PhiX genomic DNA and low-complexity DNA are reported after the analysis is completed. Overall, barcode mapping and counting are extremely fast after the read packs are generated. The Oligopool Calculator had a computational throughput of 1.15 to 1.2 billion reads per hour when analyzing the 590 million reads collected to characterize the promoter library (association counting) whereas its throughput was 1.2 to 3.6 billion reads per hour when analyzing the 2 billion reads collected to characterize the mRNA stability elements and the 300 million reads collected to characterize the nonrepetitive ribozymes (both using combinatorial counting) (Table S4). The count measurements are then used to quantify the activities of the genetic system variants; as an example, we measured the self-cleavage efficiencies of 6,232 designed, nonrepetitive ribozymes and identified over 300 with high self-cleavage efficiencies (Figure 6F). The presented Oligopool Calculator is a suite of automated workflows that enables the rapid design of oligopools to carry out massively parallel construction of many genetic system variants as well as the rapid analysis of deep sequencing results to characterize the genetic system variants’ activities. As illuminating examples, we show how the Oligopool Calculator was used to build and characterize thousands of promoters, mRNA stability, and ribozyme variants. Overall, the Oligopool Calculator now makes it much simpler to design complex oligopools with multiple well-designed barcodes while eliminating common failure modes. After the experiments are finished and deep sequencing is carried out, the Oligopool Calculator converts what was an error-prone multistep process into an hours-long automated procedure that generates precise measurements with transparent reporting. As oligopools are increasingly used to build and test thousands of genetic system variants, it will become ever more important to apply automated design and analysis workflows to extract reusable knowledge from thousands of defined experiments. Methods Edge Effect Minimization Given a nonempty set of n left/prefix context sequences X, and a nonempty set of n right/suffix context sequences Z, in the DNA alphabet set {}, we first extract all suffixes of all possible lengths from elements of X, and all prefixes of all possible lengths from elements of Z. Given a nonempty set of excluded DNA motif sequences E, we partition every element ej in the set into all possible prefixes and suffixes of all possible lengths, where . A set of inserts Y = {y1,y2,...,yn} are then designed to be free from left edge effects with respect to E, by ensuring that every prefix yi[0.q) is not a suffix of some excluded motif ej, where , if placed next to xi such that xi[p.|xi|) is a prefix of ej, where , for all . Similarly, the inset yi is optimized to be free from right edge effect with respect to an excluded motif sequence ek, by ensuring that yi[u.|yi|) is not a prefix of ek, where , when placed before context sequence zi such that zi[0.ν) is a suffix of ek, where , for all . If the insets are designed using Non-Repetitive Parts (NRP) Calculator in Maker Mode, these objectives are fulfilled using its traceback mechanism; otherwise, the insets are evaluated from a set of randomly generated sequence candidates until one meeting these criteria are found. Barcode Design The barcode design algorithm requires as input barcode length integer b, oligo limit length integer o, minimum Hamming distance integer h, maximum shared repeat length integer k, the prefix context string set X, suffix context string set Z, and a set of excluded motifs E, and outputs barcode set C. All inputs are validated for data type and value range correctness. First, we verify (i) , where n is the total number of variants in the oligopool, (ii) a barcode set can be built without any of the excluded motif sequence, i.e., there does not exist all possible 4m strings of length m inside E, , and (iii) adding a barcode of length b to the context X and Z does not exceed oligo limit o, i.e., , where xlongest and zlongest are the longest sequences in X and Z. This is followed by construction of hash tables to store all information necessary to eliminate edge effects as well as building a k-mer dictionary from X and Z for eliminating repeats. We then initialize a random number generator to iteratively stream all numbers between 0 and 4b–1–1, and use it produce a set of random numbers p = {p1, p2, p3, p4}, where p1 is the number produced by the generator, , , and . Each of these numbers are then decoded as a base-4 integer and converted into a string in the DNA alphabet based on the mapping: 0 → A, 1 → C, 2 →g and 3 → τ. All elements in p are then evaluated for the following objectives. Objective 1: HammingDistance(pi, c) ≥ h, where c ∈ C and HammingDistance(g, h) = |{j: gj ≠ hj, j = 0, ..., min(|g|, |h|) – 1}|. Objective 2: no edge effect occurs when pi is accepted as cj, where j = |C|, with respect to X and Z. Objective 3: no k-mer in pi is duplicated in context set X or Y upon acceptance as cj. Objective 4: no excluded motif e ∈ E exists in pi. Objective 5: no substring of length q is shared between pi and strings in C, where . All barcode candidates that fulfill these objectives are sequentially added to C. To speed up objective 1, we use strategies described later for the Scry classifier to reduce the number of previously designed barcodes against which a current barcode is evaluated for Hamming distance conflicts. This process is repeated until |C| = n, or until we fail to produce a barcode in t successive attempts, where t is the number of trials in which a barcode is expected to be designed successfully. This parameter is initially set to 1,000, but iteratively adjusted based on the failure count between successive barcode generation, by modeling the barcode design process as a Bernoulli trial. Primer Design Primer design relies on the NRP Calculator as an underlying component for sequence optimization. Input to the algorithm includes degenerate sequence constraint s in alphabet IUPAC where each element in IUPAC maps uniquely to P(DNA), oligo limit length integer o, primer type integer r, minimum and maximum melting temperatures tmin and tmax, maximum shared repeat length k, paired primer sequence sp in DNA alphabet, a set of substrings from background DNA sequences B, prefix context string set X, suffix context string set Z, and a set of excluded motifs E. The primer sequence constraint s is verified to have degenerate IUPAC characters, no palindrome substrings and no internal inverted repeats following canonical Watson–Crick base pairing, embedded within s. Oligo limit length and the excluded motif set are validated like those in barcode design algorithm. We then determine if a primer sequence can be designed within tmin and tmax bounds using Monte Carlo simulation of candidate primer sequences with predominantly weak or strong bases, i.e., and , where sweak and sstrong are candidate DNA strings preferentially composed using {} and {} respectively, and Tm(DNA+) returns the melting temperature of a DNA string based on parameters from SantaLucia 1998.62 This is followed by construction of hash tables to store all information necessary to eliminate edge effects, as well as building a k-mer dictionary from X and Z for eliminating repeats. The primer sequence constraint s and the paired primer sequence sp are then reverse complemented as necessary to correct orientation based on primer type parameter r. An instance of NRP Calculator is then used to design the primer sequence s’, based on the following objectives with a jump count of 1,000 and failure count of 100,000. Objective 1: no substrings are shared between s’ and B. Objective 2: no k-mer in s’ is shared with context set X or Y. Objective 3: no repeats longer than 6 characters in length are shared between s’ and sp. Objective 4: no excluded motif e ∈ E emerges in s’ during sequence construction unless due to s. Objective 5: no edge effect occurs at the terminal ends of s’. Objective 6: post construction . Objective 7: no stable secondary structures forms between single stranded copies of s’, i.e., , where predicts the minimum free energy associated with the most favorable secondary structure for a given DNA string using Matthews 2004 parameters.63 Objective 8: no stable dimer forms between single stranded copies of s’ and sp, i.e., and also based on Mathews 2004 parameters. All these objectives are fulfilled on a per nucleotide basis using a combination of local and global model functions input to the NRP Calculator that is used to guide the primer sequence space exploration. Spacer and Motif Design Motifs are based on an IUPAC sequence constraint s such as a primer. Additional inputs include oligo limit length integer o, prefix and suffix context DNA string sets X and Z, and the excluded motif DNA string set E. If s has no degenerate characters, then it is simply inserted as a constant between X and Z, and no optimization is done. Otherwise, NRP Calculator is used to design the motifs with respect to edge effect and excluded motif objectives like those specified for primer sequences. To speed up computation, once a candidate motif string is designed for context i it is validated against and assigned to as many remaining contexts as possible, such that and n = |X| = |Z|. This process continues until every context has a designed motif. Spacers are a weaker form of motif, in which we derive a maximally degenerate IUPAC sequence constraint s based either on a fixed or contextually defined spacer length integer l for every xi ∈ X and zi ∈ Z such that |xi| + |zi| + l = o. The objectives considered are the same as motifs, but a spacer designed for context i is only evaluated for reassignment against context sequences xj and zj such that |xi| + zi| = |xj| + |zj|. Oligo Splitting The splitting algorithm takes as input a set of DNA strings Y = {y1,y2,...,yn} where n = |Y|, split limit integer l, minimum melting temperature t, minimum Hamming distance integer h, and minimum and maximum overlap span length integers smin and smax. All inputs are validated for value range and correctness, and all y ∈ Y are padded with random strings to ensure |yi| = |yj|, for all and . However, no splitting is done if the difference in the . We first analyze Y to extract a set of tuples such that for all , where , , and p(x) is the probability of x in y. The strings in Y may then only be split in intervals from C. Based on l and C, we then choose a breakpoint w inside an interval tuple c ∈ C such that , where u is set initially to 0. We then choose another breakpoint v also inside c, where ν < w, such that all satisfy the following objectives. Objective 1: . Objective 2: for all pairs of elements , , where function is same as the one evaluated for barcode design, and . Objective 3: . We initially set and then continue decreasing it by 1 until either all the objectives are met, or ν reaches the starting coordinate in c. If no such breakpoint ν is found, then the algorithm terminates. Otherwise, the split fragment for all y is stored as y[u.w), u is updated to ν, and the remaining sections of the strings in Y are processed. The algorithm continues until the value of w is the ending coordinate of the last interval in C. The final set of split fragments is then y[ν.|y|). Once every string in Y was split, the randomly added pads are stripped out from the final fragment set. Padding of Split Sequences A single set of split fragments Y are then padded with DNA strings until the length of each fragment reaches an oligo limit length integer o, with internal 3′ flanking primers containing a TypeIIS restriction site of choice. The forward pad sequence constraint is maximally degenerate, and the full pad is based on the fragment length differences , a TypeIIS restriction site t, and the melting temperature range for the core primer which is kept approximately 20 bases long. Design of forward pad p is based on and . Initially the algorithm specifies p = t. If , then clearly no forward pad sequence can be designed to contain the cut site completely, and the algorithm terminates. Otherwise, p is prepended by dlongest −|t| fully degenerate IUPAC bases upstream such that |p| = dlongest, of which is the primer region. The full pad sequence is then designed using NRP Calculator with previously defined primer objectives for the core primer region, and the only excluded motif set is {t} A total of 34 restriction sites are available for use including AcuI, AlwI, BbsI, BccI, BceAI, BciVI, BcoDI, BmrI, BpuEI, BsaI, BseRI, BsmAI, BsmBI, BsmFI, BsmI, BspCNI, BspQI, BsrDI, BsrI, BtgZI, BtsCI, BtsI, BtsIMutI, EarI, EciI, Esp3I, FauI, HgaI, HphI, HpyAV, MlyI, MnlI, SapI, and SfaNI. These restriction enzymes are selected due to their short recognition sequence, and because they uniquely cut close to the 3′ end of the recognition site. The reverse pad q is designed in the same way but within bases, but in the reverse complement orientation. Once both pads are designed, the algorithm trims the 5′ ends of p and q and appends them to y ∈ Y in the correct orientation such that |y| = o. Scry Classifier The Scry classifier essentially behaves like a 1-nearest neighbor model, since we are interested in locating the best reference barcode match given a sequenced barcode string. For training the model we instantiate a Scry object which takes as input a set of DNA barcode strings X, a barcode label vector such that |y| = n, barcode length integer b, and an expected sequencing error count integer t. We then store all inputs as object attributes and build the following data structures. Contigs: an associative array where each key uContig is a substring of length l, where , from some , and the value associated with uContig is the set of all yi ∈ Y such that uContig is a substring in . Spectrum: an associative array where each key uSpectrum is a k-mer from X, and the associated value is a tuple of ⟨Iv, Ig⟩, where k = [b/2]. Iv is the sorted set of all indexes i such that xi ∈ X contains as a -mer inside it. Ig is an array of length of m = b – k + 1 where the gth element of Ig is a tuple ⟨p,q⟩ such that every Iv[p.q) and . For prediction tasks, the algorithm takes as input a sequenced barcode DNA string x’ such that , otherwise it returns a tuple ⟨Ø,0⟩, where Ø denotes an unmatched label. If we find an x′ = xi ∈ X, we simply return the tuple ⟨yi,1⟩ as the corresponding result since it is a perfect match. Otherwise, we extract all substrings xl of length l in decreasing order and check if xl ∈ Contigs, where . As soon as we find an xl mapping uniquely to some yi ∈ Y, we return the tuple ⟨yi,l/b⟩ since it is a strong partial match. These steps are part of the fast prediction mode. Otherwise, we initialize an array of zeroes Score of length n. Next, for each k-mer uSequence from x’ starting at location c, where , we use Spectrum to determine the set of indexes Ic such that for some and for all h ∈ Ic, and increase the count at those indexes in Score by k for each k-mer hit. Once all k-mers from x’ have been processed, we determine all indexes Imax in Score containing the maximum value. For each such index m ∈ Imax, we then compute the , and accept ym as the label for x’ if , where EditDistance(DNA+,DNA+) returns the canonical Levenshtein distance64 between two strings. If none of the indexes in Imax are accepted or more than one index is accepted, then the algorithm returns ⟨Ø,0⟩. Otherwise, it returns an unambiguous matching result ⟨⟩. These steps constitute a sensitive prediction mode. The algorithm runs fast prediction before executing the sensitive matching steps. Index Construction To build indexed objects of barcodes and associated variants, the algorithm requires a set of n tuples B = {⟨y1,b1⟩,...} where yi is the identity label for DNA barcode string bi and , barcode prefix and suffix constant strings abarcode and cbarcode, barcode prefix and suffix gap integers gbarcode and hbarcode, and optionally a set of n tuples V = {⟨y1,ν1⟩,...} where yi is the identity label for DNA variant νi, variant prefix and suffix constants avariant and cvariant, and variant prefix and suffix gap integers gvariant and hvariant. Crucially, we interpret a barcode with label y to be linked with the variant which also has y as its label. All barcodes are required to be unique and of fixed length, but the associated variants may have variable lengths or duplicates. If no associated variant information is provided, then the indexed objects can only be used for combinatorial counting and not association counting. Once all inputs are validated, we built the following objects. MetaMap: an associative array storing all meta data information such as variant count, barcode length, prefix and suffix constants, gap lengths, constant trimming policy, and association information. IdentityMap: an ordered array of labels, i.e., IdentityMap. BarcodeModel: a Scry classifier trained on the barcode data and related information. The default error tolerance parameter tdefault is automatically inferred from barcode length and is set to ⌊⌋. AssociateMap: an ordered array of variant sequences, i.e., AssociateMap[i.i + 1) contains a variant with label yi. All objects are compressed and stored in a single “.oligopool.index” file for later use. Collectively, an index serves as a single unit of information that needs to be mapped and counted in sequenced reads. Read Packing The packing algorithm requires an R1 FastQ file r1, R1 content type integer c1, R1 Phred quality score threshold integer q1, and R1 minimum read length integer l1. If paired-end reads are available, additional inputs include the R2 FastQ file r2, R2 content type integer c2, R2 quality threshold integer q2, and R2 minimum read length integer l2. Finally, the packing operation identifier integer p, batch size integer s, total number of CPU cores u to be used, and memory limit m to be allocated to each core may be specified. All inputs are checked for correctness, and default values are used for optional inputs that are absent. Depending on p, if the paired-end reads are to be assembled, we process a sample of 50,000 reads in r1 and r2 to determine the optimal assembly parameters. Briefly, we reverse complement both r1 and r2 as necessary based on c1 and c2, and align the 3′ end of r1 to 5′ end of r2 (innie alignment), as well as the 5′ end of r1 to the 3′ end of r2 (outie alignment) to rank the alignment scheme e with higher overlap length. The alignment overlap lengths are then stored in a vector O. We then define the read operation policy as the tuple g = ⟨a,o⟩ where a is a tuple ⟨emax,emin⟩ ranking both alignment schemes based on their frequency in the sampled reads, and o=max(min(0),10). If p indicates concatenation or if only r1 is specified, then where ⊕ indicates the string concatenation operation and ° indicates the delimiter. Each of the u cores then process th portion of r1 and r2 in parallel and stores the reads inside two process-specific associative arrays PackHeader and PackLocal. Paired reads shorter than l1 and l2, or having quality scores less than q1 and q2 are filtered out and the read operation based on g is applied to produce a single read ri for all . If merging is involved, we first apply scheme emax, and then apply emin if emax produces an overlap of length oi < o. Once the reads are aligned . If g0=⊕ then . Next, we checked whether ri exists as a key in PackHeader, which is initially empty. If ri is a key in PackHeader, we simply increase its count value by 1, otherwise we store and update the count of ri in PackLocal until the cardinality of PackLocal exceeds pack size s. Once the size of PackLocal is greater than s and if PackHeader is empty, we move the contents of PackLocal to PackHeader, otherwise we first serialize PackLocal to disk and then clear its contents. Once all cores have finished processing r1 and r2, we move each read r from the jth PackHeader to the zeroth PackHeader if r is a key inside the latter, and update their counts, where . Each updated PackHeader is then serialized to a disk. Finally, all serialized content is compressed and archived in a single “.oligopool.pack” file. Each pack file is then a single experiment against which an index is to be mapped and counted. At any point during packing, if the memory occupied by the jth process exceeds m after processing the ith read, then the process is respawned where packing resumes at read number i + u. A process may also be restarted if the available free memory falls below 2 gigabytes. These policies allow packing to be executed in fixed memory and dynamically adjust the memory profile of each process. Read Counting The combinatorial counting algorithm requires a single index file IndexFile, pack file PackFile, mapping type integer p, barcode error count integer tbarcode, associate error count integer tassociate, an optional callback function F, total number of CPU cores u to be used, and the memory cap per core m. In contrast, the association counting algorithm does not require associate error count as an input, but more than one index file ⟨IndexFile1, IndexFile2, .⟩ may be specified. Once all inputs are validated, read packs from PackFile are distributed uniformly to each of the u cores for parallel mapping and counting. For association counting, each process loads all indexed objects from the input IndexFile and builds a set P containing 30-mers from the ΦX174 genome. We then process each Pack ∈ PackFile as an ordered array of tuples ⟨r,c⟩ where r is a DNA read string and c is the count of r in Pack. For each ri, we first correct its orientation based on the barcode prefix and suffix constants abarcode and cbarcode. If neither constants are matched in ri, we check (1) if where , and (2) if where returns the sum of counts of each alphabet of ∑ in a DNA string, , and . If the first condition is met, then we record ri as a PhiX read. If the second condition is met, then we consider ri to be a low complexity read. If neither of the conditions is met, we simply record ri as a “failed read”. Once the read has been corrected for orientation, we extract the region of ri between the constants as barcode candidate string , which is classified using the BarcodeModel stored in IndexFile based on p and tbarcode. If the barcode is not mapped, then we discard ri as a “failed read”. Otherwise, we extract the region of ri between the prefix and suffix constants avariant and cvariant as the variant candidate string , and check if , where νi is the variant associated with predicted barcode label yi. If shows higher edit distance, ri is again considered as a “failed read”. Next, if a callback function F is specified, ri is discarded if F(ri) returns False (a “false read”), otherwise ri is accepted. A central associative array Count, which is accessible from all processes is then used to update the count of yi by c. Once all packs are processed, the entries in Count are written out to a “.oligoopool.acount” file. Combinatorial counting follows the same steps as association counting, except that associated variants cannot be mapped, but multiple barcodes may be mapped instead based on IndexFile1, IndexFile2, and so on. Each entry in the central Count is then a tuple ⟨y1,y2,...⟩ where yq is the barcode label predicted based on the qth IndexFile. Counting processes are restarted in the same manner as that done during read packing. Acknowledgments We’d like to thank Alexander Reis and David Kuo for their feedback. This project was supported by funds from the National Science Foundation (MCB-2131923), the Defense Advanced Research Projects Agency (FA8750-17-C-0254), and the Department of Energy (DE-SC0019090). Data Availability Statement A Python implementation of Oligopool Calculator can be found at (1) github.com/hsalis/SalisLabCode, (2) github.com/ayaanhossain/oligopool, and (3) pypi.org/project/oligopool. Supporting Information Available The Supporting Information is available free of charge at https://pubs.acs.org/doi/10.1021/acssynbio.4c00661. Additional schematics, calculations, and computational benchmarks as shown in Supplementary Figures 1 to 10 and Supplementary Tables 1 to 4 (PDF) Additional schematics, calculations, and computational benchmarks as shown in Supplementary Figures 1 to 10 and Supplementary Tables 1 to 4 (PDF) Author Contributions A.H. and H.M.S. conceived the project, developed the algorithms, and wrote the manuscript. A.H., T.L.L., D.P.C., J.M., and H.M.S. applied the algorithms and analyzed data. J.M. wrote documentation. All authors read and approved the final manuscript. The authors declare the following competing financial interest(s): HMS is the founder of De Novo DNA. Supplementary Material sb4c00661_si_001.pdf References Associated Data Supplementary Materials sb4c00661_si_001.pdf Data Availability Statement A Python implementation of Oligopool Calculator can be found at (1) github.com/hsalis/SalisLabCode, (2) github.com/ayaanhossain/oligopool, and (3) pypi.org/project/oligopool.