Abstract: 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. When designing multiplex PCR assays, one has to avoid cross-hybridizations between primers of different loci in the same reaction tube. This can be addressed either by modifying the choice of primers for one or more loci, or by altering the way in which DNA loci are partitioned into separate reaction tubes. In this talk, 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 when the multiplexing level of the reaction tubes is roughly $\Theta(\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. We further
present an algorithm that finds such a cover for most of the graphs.

Joint work with Noga Alon, Charles Cantor, Simon Kasif and John Rachlin.