Technical Report Number
Single Nucleotide Polymorphism (SNP) Genotyping is an important molecular genetics process in the early stages of producing results that will be useful in the medical ﬁeld. Due to inherent complexities in DNA manipulation and analysis, many diﬀerent 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. In order 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. In this thesis, we describe an iterative beam-search algorithm, Multiple, It-erative Primer Selector (MIPS), for MDPD. Theoretical and experimental analyses show that this algorithm performs well compared to the limits of degenerate primer design. Furthermore, MIPS outperforms an existing algorithm which was designed for a related degenerate primer selection problem. Further analysis shows that, due to the composition of the human genome, the results from MIPS may not be realized in practice. Consequently, we address the challenges involved in selecting a suitable set of degenerate primers and possible future improvements to the algorithm.
Souvenir, Richard, "An Iterative Beam Search Algorithm for Degenerate Primer Selection" Report Number: WUCSE-2003-76 (2003). All Computer Science and Engineering Research.