Multiplex polymerase chain reaction (PCR) is an extension of the standard PCR protocol
in which primers for multiple DNA loci are pooled together within a single reaction tube,
enabling simultaneous sequence amplification, thus reducing costs and saving time. Potential
cost saving and throughput improvements directly depend on the level of multiplexing
achieved. Designing reliable and highly multiplexed assays is challenging because primers
that are pooled together in a single reaction tube may cross-hybridize, though this can be
addressed either by modifying the choice of primers for one or more amplicons, or by altering
the way in which DNA loci are partitioned into separate reaction tubes. In this paper, we
introduce a new graph formalism called a multi-node graph, and describe its application to
the analysis of multiplex PCR scalability. We show, using random multi-node graphs that the
scalability of multiplex PCR is constrained by a phase transition, suggesting fundamental
limits on efforts to improve the cost-effectiveness and throughput of standard multiplex PCR
assays. In particular, we show that when the multiplexing level of the reaction tubes is roughly
Θ(log (sn)) (where s is the number of primer pair candidates per locus and n is the number
of loci to be amplified), then with very high probability we can ‘cover’ all loci with a valid
assignment to one of the tubes in the assay. However, when the multiplexing level of the tube
exceeds these bounds, there is no possible cover and moreover the size of the cover drops
dramatically. Simulations using a simple greedy algorithm on real DNA data also confirm the
presence of this phase transition. Our theoretical results suggest, however, that the resulting
phase transition is a fundamental characteristic of the problem, implying intrinsic limits on
the development of future assay design algorithms.
