Summary
Single-nucleotide polymorphism (SNP) genotyping is an important molecular genetics process, which can produce results that will be useful in the medical field. Because of inherent complexities in DNA manipulation and analysis, many different methods have been proposed for a standard assay. One of the proposed techniques for performing SNP genotyping requires amplifying regions of DNA surrounding a large number of SNP loci. To automate a portion of this particular method, it is necessary to select a set of primers for the experiment. Selecting these primers can be formulated as the Multiple Degenerate Primer Design (MDPD) problem. The Multiple, Iterative Primer Selector (MIPS) is an iterative beam-search algorithm for MDPD. Theoretical and experimental analyses show that this algorithm performs well compared with the limits of degenerate primer design. Furthermore, MIPS outperforms an existing algorithm that was designed for a related degenerate primer selection problem.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
G. Marth, R. Yeh, M. Minton, R. Donaldson, Q. Li, S. Duan, R. Davenport, R. Miller, and P. Kwok. Single-nucleotide polymorphisms in the public domain: how useful are they? Nature Genetics, 27: 371–372, 2001.
F. S. Collins and V. A. McKusick. Implications of the human genome project for medical science. JAMA, 285:2447–2448, 2001.
P. Kwok. Methods for genotyping single nucleotide polymorphisms. Annual Review of Genomics and Human Genetics, 2:235–258, 2001.
W.R. Pearson, G. Robins, D.E. Wrege, and T. Zhang. On the primer selection problem in polymerase chain reaction experiments. Discrete and Applied Mathematics, 71:231–246, 1996.
M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, NY, 1979.
K. Doi and H. Imai. A greedy algorithm for minimizing the number of primers in multiple PCR experiments. Genome Informatics, 10:73–82, 1999.
W. R. Pearson, G. Robins, D. E. Wrege, and T. Zhang. A new approach to primer selection problem in polymerase chain reaction experiments. In Third International Conference on Intelligent Systems for Molecular Biology, pp. 285–291. AAAI Press, Cambridge, United Kingdom, 1995.
P. Nicodeme and J. Steyaert. Selecting optimal oligonucleotide primers for multiplex PCR. In Proceedings of Fifth Conference on Intelligent Systems for Molecular Biology ISMB97, HAAI Press, Halkidiki, Greece pp. 210–213, 1997.
K. Doi and H. Imai. Complexity properties of the primer selection problem for PCR experiments. In Proceedings of the 5th Japan-Korea Joint Workshop on Algorithms and Computation, The University of Tokyo, Tokyo, Japan pp. 152–159, 2000.
S. Kwok, S.Y. Chang, J.J. Sninsky, and A. Wang. A guide to the design and use of mismatched and degenerate primers. PCR Methods and Applications, 3:S39–S47, 1994.
Cornish-Bowden. IUPAC-IUB symbols for nucleotide nomenclature. Nucleic Acids Research, 13:3021–3030, 1985.
C. Linhart and R. Shamir. The degenerate primer design problem. Bioinformatics, 18 (Suppl. 1):S172–S180, 2002.
R. Souvenir. An iterative beam search algorithm for degenerate primer selection. Master’s thesis, Washington University, Saint Louis, MO, December 2003.
R. Bisiani. Search, beam. In S.C. Shapiro, editor, Encyclopedia of Artificial Intelligence, pp. 1467–1468. Wiley-Interscience, New York, NY, 2nd edition, 1992.
G.Z. Hertz and G.D. Stormo. Identifying DNA and protein patterns with statistically significant alignments of multiple sequences. Bioinformatics, 15:563–577, 1999.
M.S. Waterman. Introduction to Computational Biology. Chapman & Hall, London, UK 1995.
The Genome Sequencing Consortium. Initial sequencing and analysis of the human genome. Nature, 409:860–921, 2001.
UCSC genome browser. Web site http://genome.ucse.edu.
A.F.A Smit. Origin of interspersed repeats in the human genome. Current Opinion in Genetics and Development, 6(6):743–749, 1996.
A.F.A Smit. Structure and Evolution of Mammalian Interspersed Repeats. PhD thesis, USC, 1996.
A.F.A. Smit and P. Green. RepeatMasker. Available at http://ftp.genome.washington.edu/RM/RepeatMasker.html .
G.D. Forney, Jr. The Viterbi algortihm. In Proceedings of IEEE, volume 61, pp. 268–278, 1973.
W.R. Pearson and D.J. Lipman. Improved tools for biological sequence analysis. In PNAS, volume 85, pages 2444–2448, 1988.
D. Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, chapter 15, p. 377. Press Syndicate of the University of Cambridge, 1997.
R. Souvenir, J. Buhler, G. Stormo, and W. Zhang. Selecting degenerate multiplex PCR primers. In Proceedings of Workshop on Algorithms in Bioinformatics (WABI-03), 2003.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Humana Press
About this protocol
Cite this protocol
Souvenir, R., Buhler, J., Stormo, G., Zhang, W. (2007). An Iterative Method for Selecting Degenerate Multiplex PCR Primers. In: Yuryev, A. (eds) PCR Primer Design. Methods in Molecular Biology™, vol 402. Humana Press. https://doi.org/10.1007/978-1-59745-528-2_12
Download citation
DOI: https://doi.org/10.1007/978-1-59745-528-2_12
Publisher Name: Humana Press
Print ISBN: 978-1-58829-725-9
Online ISBN: 978-1-59745-528-2
eBook Packages: Springer Protocols