Computational tradeoffs in multiplex PCR assay design for SNP genotyping

Abstract

Background: Multiplex PCR is a key technology for detecting infectious microorganisms, whole-genome sequencing, forensic analysis, and for enabling flexible yet low-cost genotyping. However, the design of a multiplex PCR assays requires the consideration of multiple competing objectives and physical constraints, and extensive computational analysis must be performed in order to identify the possible formation of primer-dimers that can negatively impact product yield.

Results: This paper examines the computational design limits of multiplex PCR in the context of SNP genotyping and examines tradeoffs associated with several key design factors including multiplexing level (the number of primer pairs per tube), coverage (the % of SNP whose associated primers are actually assigned to one of several available tube), and tube-size uniformity. We also examine how design performance depends on the total number of available SNPs from which to choose, and primer stringency criterial. We show that finding high-multiplexing/high-coverage designs is subject to a computational phase transition, becoming dramatically more difficult when the probability of primer pair interaction exceeds a critical threshold. The precise location of this critical transition point depends on the number of available SNPs and the level of multiplexing required. We also demonstrate how coverage performance is impacted by the number of available snps, primer selection criteria, and target multiplexing levels.

Conclusion: The presence of a phase transition suggests limits to scaling Multiplex PCR performance for high-throughput genomics applications. Achieving broad SNP coverage rapidly transitions from being very easy to very hard as the target multiplexing level (# of primer pairs per tube) increases. The onset of a phase transition can be "delayed" by having a larger pool of SNPs, or loosening primer selection constraints so as to increase the number of candidate primer pairs per SNP, though the latter may produce other adverse effects. The resulting design performance tradeoffs define a benchmark that can serve as the basis for comparing competing multiplex PCR design optimization algorithms and can also provide general rules-of-thumb to experimentalists seeking to understand the performance limits of standard multiplex PCR.

Figure 1

Phase transition in full-tube coverage as a function of SNP-SNP compatibility probability. These results are based on a simulations where the controlling parameter P denotes the probability that two SNPs are compatible. Two SNPs are compatible if their associated primers are all pair-wise compatible. This simulation is based on N = 1,200 SNPS and S = 500 primer pairs per SNP. In reality, this compatibility probability, P, depends on the stringency by which primer pairs are tested for cross-interactions. As we increase the target multiplexing level, higher compatibility, beyond what are normally obtained using standard primer selection criteria is required, suggesting fundamental barriers to increasing target multiplexing levels.

Figure 2

Coverage vs. target multiplex level using two different best-fit tube assignment strategies. These results were all based on N = 1,200 for varying target multiplexing level M. In each trial, the number of allowed tubes is limited to . Full-tube coverage, the percentage of SNPs assigned to full tubes, of close to 80% is achieved at a multiplexing level of 20, though it drops rapidly for higher multiplexing levels. The graph shows a significant improvement in one algorithm over the other, demonstrating that such tradeoffs can be used to effectively compare and contrast competing optimization strategies.

Figure 3

Multiplex PCR performance tradeoffs. A closer examination of the Fixed Assignment Best-Fit algorithm reveals tradeoffs between the available number of SNPs, N, the target multiplexing level, M, and full-tube coverage. The dip at N = 1000, M = 30 is an artifact of the algorithm which strictly limits the number of tubes to = 34 tubes. Since M does not divide N evenly, the algorithm ends up partially filling the excess tube rather than working harder to fill the remaining 33 tubes to full 30-plex capacity.

Figure 4

Multi-node graphs. A multi-node graph is a convenient way of formalizing the multiplex PCR problem. In multi-node graphs, individual nodes can take on one or more states. In this figure, an edge between two nodes, X and Y, is determined by the state of the two nodes, or more specifically, an edge matrix E_XY connecting nodes X and Y. There is no restriction on the number of states per node, and each node may contain a different number of states.

Figure 5

Primer-primer compatibility probability and primer selection stringency. This figure shows how a number of primer selection criteria impact the overall probability that two primers will be mutually compatible. If compatible primers are connected by edges in a graph, the resulting probability is equivalent to the graph density. This figure plots graph density as a function of 3' ΔG interaction. Each point represents a single trial where additional primer compatibility thresholds were randomly chosen within specified ranges. Considered were the 3' tail ΔG interaction, complementary sequence local alignment score, and melting temperature (Tm) difference. Points that are more red allow for high Tm differences while points that are more blue require smaller Tm differences. The impact of local alignment score thresholds, while not shown explicitly, is indirectly revealed by the multiple tiers (bands) across the graph, the lowest corresponding to score = +4 and the highest to score = +6 to +10.