Skip Navigation

Nucleic Acids Research 2005 33(Web Server Issue):W544-W547; doi:10.1093/nar/gki377
This Article
Right arrow Abstract Freely available
Right arrow Print PDF (435K) Freely available
Right arrow Screen PDF (138K) Freely available
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Commercial Re-use Guidelines
for Open Access NAR Content
Google Scholar
Right arrow Articles by Rachlin, J.
Right arrow Articles by Kasif, S.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Rachlin, J.
Right arrow Articles by Kasif, S.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2005. Published by Oxford University Press. All rights reserved
The online version of this article has been published under an open access model. Users are entitled to use, reproduce, disseminate, or display the open access version of this article for non-commercial purposes provided that: the original authorship is properly and fully attributed; the Journal and Oxford University Press are attributed as the original place of publication with the correct citation details given; if an article is subsequently reproduced or disseminated not in its entirety but only in part or as a derivative work this must be clearly indicated. For commercial re-use, please contact journals.permissions{at}oupjournals.org

Article

MuPlex: multi-objective multiplex PCR assay design

John Rachlin1,*, Chunming Ding2, Charles Cantor1,3,4,6 and Simon Kasif1,3,5

1Bioinformatics Program, Boston University Boston, MA 02215, USA 2Centre for Emerging Infectious Diseases, The Chinese University of Hong Kong, Prince of Wales Hospital Shatin, New Territories, Hong Kong Special Administrative Region, China 3Department of Biomedical Engineering, Boston University Boston, MA 02215, USA 4Center for Advanced Biotechnology, Boston University Boston, MA 02215, USA 5Center for Advanced Genomic Technologies, Boston University Boston, MA 02215, USA 6SEQUENOM, Inc. San Diego, CA 92121-1331, USA

*To whom correspondence should be addressed. Tel: +1 617 921 9669; Fax: +1 617 353 4814; Email: rachlin{at}bu.edu

Received February 14, 2005. Revised March 8, 2005. Accepted March 8, 2005.


   ABSTRACT
TOP
 ABSTRACT
INTRODUCTION
 ARCHITECTURE
 CONCLUSIONS AND FUTURE WORK
 REFERENCES
 
We have developed a web-enabled system called MuPlex that aids researchers in the design of multiplex PCR assays. Multiplex PCR is a key technology for an endless list of applications, including detecting infectious microorganisms, whole-genome sequencing and closure, forensic analysis and for enabling flexible yet low-cost genotyping. However, the design of a multiplex PCR assays is computationally challenging because it involves tradeoffs among competing objectives, and extensive computational analysis is required in order to screen out primer-pair cross interactions. With MuPlex, users specify a set of DNA sequences along with primer selection criteria, interaction parameters and the target multiplexing level. MuPlex designs a set of multiplex PCR assays designed to cover as many of the input sequences as possible. MuPlex provides multiple solution alternatives that reveal tradeoffs among competing objectives. MuPlex is uniquely designed for large-scale multiplex PCR assay design in an automated high-throughput environment, where high coverage of potentially thousands of single nucleotide polymorphisms is required. The server is available at http://genomics14.bu.edu:8080/MuPlex/MuPlex.html.


   INTRODUCTION
TOP
 ABSTRACT
 INTRODUCTION
ARCHITECTURE
 CONCLUSIONS AND FUTURE WORK
 REFERENCES
 
MuPlex (http://genomics14.bu.edu:8080/MuPlex/MuPlex.html) is a web-enabled system for designing multiplex PCR assays. A multiplex PCR solution specifies a forward and reverse primer for each single nucleotide polymorphism (SNP) and assigns each primer pair to one of a finite set of tubes. In partitioning SNP primers into individual tubes, care must be taken to ensure that all primers within a tube are mutually compatible, i.e. that they do not form primer-dimers through cross-hybridization, which would otherwise reduce target product yield. The multiplex PCR problem is equivalent to partitioning a graph G(V, E) into a set of disjoint cliques, where nodes represent SNPs, edges connect two SNPs whose associated primers are tube-compatible and resulting cliques constitute valid multiplex PCR tubes. The problem of partitioning a graph into k ≤ K disjoint cliques is NP-complete (1). The MuPlex system is unique in that it provides multiple design alternatives that reveal inherent tradeoffs with respect to multiple competing objectives, such as average tube size, tube size uniformity and overall SNP coverage.

Multiplex PCR is a core enabling technology for high-throughput SNP genotyping, serving as a foundation for applications in forensic analysis, including human identification and paternity testing (2), the diagnosis of infectious diseases (3,4), whole-genome sequencing (5), and pharmacogenomic studies aimed at understanding the connection between individual genetic traits, drug response and disease susceptibility (6).

For example, in the hME assay (7), genomic sequences containing the SNPs of interest are first amplified by PCR. After shrimp alkaline phosphatase digestion of excess dNTPs, a primer extension reaction is carried out to interrogate the SNPs. The primer extension products (often oligonucleotides ~18 to 25 bases long) are then detected by matrix-assisted laser desorption ionization time-of-flight (MALDI-TOF) mass spectrometry. Given the large molecular weight window (4500–9000 Da) and the high resolution of the mass spectrometry, 20 or more SNPs can be easily and simultaneously genotyped. Thus, the throughput-limiting step is often the PCR plex level. In a 384-well format with 20-plex PCR, the per-SNP cost can be reduced to just a few cents while a single MALDI-TOF mass spectrometry can be used to genotype 76 800 SNPs by a single operator in 1 day.

MuPlex features
Given a set of DNA sequences and a SNP location at each, the system aims at designing (i) a set of pair forward and reverse primers for each sequence; (ii) a placement of these primers into maximal size tubes such that the coverage (number of sequences) included in the PCR assay is maximized. Figure 1 presents the MuPlex home page where specific problems may be submitted. (No user registration or fee is required.) The user provides a set of SNPs and associated flanking sequences in the standard FASTA format. These sequences may be entered manually or uploaded from a file. To improve primer specificity, users may instruct the MuPlex server to filter resulting primer candidates by aligning them against the human genome using BLAT (8). In addition to the SNP sequences, the user specifies primer selection criteria, including length, GC content, positional constraints, and melting temperature Tm constraints for individual primer oligos as well as interaction parameters (maximum local alignment score, 3' tail {Delta}G), and a maximum Tm range for all primer pairs within a single multiplex assay.



View larger version (38K):
[in this window]
[in a new window]
  		Figure 1 The MuPlex homepage. Users specify primer selection criteria and provide a collection of SNPs in the FASTA format. The system emails to the user one or more solution alternatives revealing key design tradeoffs.

 
MuPlex then solves the dual problem of selecting primer pairs for amplifying the flanking sequence of each SNP and partitions these primer pairs into multiplex compatible sets each corresponding to a single multiplex PCR tube reaction. As noted above, MuPlex generates multiple solutions alternative each corresponding to a set of multiplex PCR tubes.

Each solution is evaluated with respect to the following objectives:

  1. Total number of tubes required.
  2. Minimum, average and maximum tube size (multiplexing level).
  3. Number of unique tube sizes.
  4. Total SNP coverage measured both in terms of the percentage of SNPs (associated primer pairs) assigned to maximum-sized tubes, as well as the percentage of SNPs assigned to tubes of any size.

For example, some solutions may achieve higher overall multiplexing levels but at the expense of lower coverage, i.e. by excluding some SNPs from the solution. In addition, MuPlex tries to minimize the number of unique tube sizes in order to facilitate automation in a high-throughput genomics environment. Resulting solutions are emailed to the user. The email contains a solution summary allowing quick comparison of each alternative, and details for each solution including the selected primers, their individual properties and assigned tube.

MuPlex employs a number of heuristic algorithms and allows new algorithms to be added over time. Solution time depends on the number of solution alternatives requested, the number of SNPs and the target multiplexing level. For typical problems involving <100 SNPs, multiple solutions can often be generated in 5–10 min.


   ARCHITECTURE
TOP
 ABSTRACT
 INTRODUCTION
 ARCHITECTURE
CONCLUSIONS AND FUTURE WORK
 REFERENCES
 
MuPlex is written entirely in Java (j2sdk1.4.2_05) and employs the Apache Jakarta Tomcat server (http://jakarta.apache.org/tomcat) connected to a backend mySQL database (http://www.mysql.com). Individual solvers operate asynchronously on a network of workstations running a customized distribution of the Linux operating system based on Fedora Core 3 (http://fedora.redhat.com). These solvers monitor the MuPlex database for the arrival of new problems. New problems are assigned to the first available solver. As depicted in Figure 2, the solver maintains a population of candidate solutions. Each solution is evaluated with respect to a set of registered objectives. Agents encapsulating specific algorithms either create new solutions from scratch, improve or modify existing solutions, or remove unpromising solutions from further consideration. For example, one ‘creator’ algorithm is based on a best-fit methodology that iteratively assigns SNPs to the largest open compatible tube. When the tube size reaches the target multiplexing level specified by the user, it is closed, and no further additions or modifications to that tube are made. Each unassigned SNP is assigned a new primer pair candidate and the process repeats. One improver algorithm eliminates partial tubes in order to reduce the number of unique tube sizes but while incurring reduced coverage, while another attempts at reformulating partial tubes in an effort to identify additional full tubes. Efficiency is enhanced during the optimization process by periodically culling unpromising solutions from the population of candidates. The architecture is scaleable in the sense that new algorithms can be readily plugged-in over time, and it is robust in that it does not depend on a single algorithm to generate every viable alternative, and because system load is balanced across a distributed collection of solvers.



View larger version (18K):
[in this window]
[in a new window]
  		Figure 2 The MuPlex Optimizer. Once a problem is submitted and validated, it is assigned to one of the several solvers distributed across the network. Each solver instantiates one or more agents (algorithms) that either create new solutions from scratch, attempt to improve an existing solution candidate or eliminate unpromising solutions from further consideration. The collaboration of algorithms in this manner enables the system to produce multiple Multiplex PCR solutions that reveal intrinsic design tradeoffs.

 
Within a given solution, there is no guarantee that a SNP will be assigned, and the results depend on the random order in which SNPs and primers are processed. Resulting coverage critically depends on the number of SNPs and the target level of multiplexing desired (J. Rachlin, C. M. Ding, C. Cantor and S. Kasif, manuscript submitted).


   CONCLUSIONS AND FUTURE WORK
TOP
 ABSTRACT
 INTRODUCTION
 ARCHITECTURE
 CONCLUSIONS AND FUTURE WORK
REFERENCES
 
The MuPlex server allows scientists to design Multiplex PCR assays while explicitly considering intrinsic design tradeoffs. The consideration of competing alternatives has played a key role in the development of optimization and decision-support technologies in complex domains such as manufacturing and transportation logistics (9,10). Here, we have demonstrated the viability of such approaches to the optimization of multiplex PCR assays. Future efforts will focus on the development of new algorithms and on allowing users to impose dynamic feedback constraints in an effort to further guide the design optimization process towards solutions that more closely meet the scientist's particular design objectives. We also plan to develop a distributed version that will run on our 128-processor Linux cluster.


   ACKNOWLEDGEMENTS
 
The authors thank Noga Alon and Richard Beigel for many profound insights and suggestions. This work is supported in part by NSF grants DBI-0239435 and ITR-048715 and NHGRI grant #1R33HG002850-01A1. Funding to pay the Open Access publication charges for this article was provided by NHGRI.

Conflict of interest statement. None declared.


   REFERENCES
TOP
 ABSTRACT
 INTRODUCTION
 ARCHITECTURE
 CONCLUSIONS AND FUTURE WORK
 REFERENCES
 

  1. Garey, M.R. and Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness, (1979) San Francisco, CA W.H. Freeman .

  2. Inagaki, S., Yamamoto, Y., Doi, Y., Takata, T., Ishikawa, T., Imabayashi, K., Yoshitome, K., Miyaishi, S., Ishizu, H. (2004) A new 39-plex analysis method for SNPs including 15 blood group loci Forensic Sci. Int., 144, 45–57[Medline] .

  3. Elnifro, E., Ashshi, A., Cooper, R., Klapper, P. (2000) Multiplex PCR: optimization and application in diagnostic virology Clin. Microbiol. Rev., 13, 559–570[Abstract/Free Full Text] .

  4. Pinar, A., Bozdemir, N., Kocagoz, T., Alacam, R. (2004) Rapid detection of bacterial atypical pneumonia agents by multiplex PCR Cent. Eur. J. Public Health, 12, 3–5[Medline] .

  5. Tettelin, H., Radune, D., Kasif, S., Khouri, H., Salzberg, S. (1999) Optimized multiplex PCR: efficiently closing a whole-genome shotgun sequencing project Genomics, 62, 500–507[CrossRef][Web of Science][Medline] .

  6. Shi, M., Bleavins, M., de la Iglesia, F. (1999) Technologies for detecting genetic polymorphisms in pharmacogenomics Mol. Diagn., 4, 343–351[CrossRef][Web of Science][Medline] .

  7. Tang, K., Fu, D.J., Julien, D., Braun, A., Cantor, C.R., Koster, H. (1999) Chip-based genotyping by mass spectrometry Proc. Natl Acad. Sci. USA, 96, 10016–10020[Abstract/Free Full Text] .

  8. Kent, W.J. (2002) BLAT: the BLAST-like alignment tool Genome Res., 12, 656–664[Abstract/Free Full Text] .

  9. Constraints & Agents Murthy, S., Rachlin, J., Akkiraju, R., Wu, F. (1997) Agent-Based Cooperative Scheduling Technical Report WS 1997-97-05 .

  10. Rachlin, J., Goodwin, R., Murthy, S., Akkiraju, R., Wu, F., Kumaran, S., Das, R. (1999) A-Teams: An Agent Architecture for Optimization and Decision-Support. Lecture Notes in Artificial Intelligence 1555, .


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Nucleic Acids ResHome page
S. N. Gardner, A. L. Hiddessen, P. L. Williams, C. Hara, M. C. Wagner, and B. W. Colston Jr
Multiplex primer prediction software for divergent targets
Nucleic Acids Res., October 1, 2009; 37(19): 6291 - 6304.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
B. Contreras-Moreira, B. Sachman-Ruiz, I. Figueroa-Palacios, and P. Vinuesa
primers4clades: a web server that uses phylogenetic trees to design lineage-specific PCR primers for metagenomic and diversity studies
Nucleic Acids Res., July 1, 2009; 37(suppl_2): W95 - W100.
[Abstract] [Full Text] [PDF]

Home page
 J. Clin. Microbiol.Home page
B. T. Leader, J. G. Frye, J. Hu, P. J. Fedorka-Cray, and D. S. Boyle
High-Throughput Molecular Determination of Salmonella enterica Serovars by Use of Multiplex PCR and Capillary Electrophoresis Analysis
J. Clin. Microbiol., May 1, 2009; 47(5): 1290 - 1299.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
A. C. Ziesel, M. A. Chrenek, and P. W. Wong
MultiPriDe: automated batch development of quantitative real-time PCR primers
Nucleic Acids Res., May 1, 2008; 36(9): 3095 - 3100.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
O. J. Jabado, G. Palacios, V. Kapoor, J. Hui, N. Renwick, J. Zhai, T. Briese, and W. I. Lipkin
Greene SCPrimer: a rapid comprehensive tool for designing degenerate primers from multiple sequence alignments
Nucleic Acids Res., December 2, 2006; 34(22): 6605 - 6611.
[Abstract] [Full Text] [PDF]

This Article
Right arrow Abstract Freely available
Right arrow Print PDF (435K) Freely available
Right arrow Screen PDF (138K) Freely available
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Commercial Re-use Guidelines
for Open Access NAR Content
Google Scholar
Right arrow Articles by Rachlin, J.
Right arrow Articles by Kasif, S.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Rachlin, J.
Right arrow Articles by Kasif, S.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?