Multi-node graphs: A framework for multiplexed biological assays

Noga Alon, Vera Asodi, Charles Cantor, Simon Kasif, John Rachlin

Research output: Contribution to journalReview articlepeer-review

4 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1659-1672
Number of pages14
JournalJournal of Computational Biology
Issue number10
StatePublished - Dec 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Genetics
  • Molecular Biology
  • Computational Theory and Mathematics
  • Modeling and Simulation


  • Algorithms
  • Combinatorics
  • Computational molecular biology


Dive into the research topics of 'Multi-node graphs: A framework for multiplexed biological assays'. Together they form a unique fingerprint.

Cite this