A Greedy Algorithm for Minimizing the Number of Primers in Multiple PCR Experiments

The selection of a suitable set of primers is very important for polymerase chain reaction (PCR) experiments. Most existing algorithms for primer selection are concerned with producing a primer pair for each DNA sequence. However, when all the DNA sequences of the target objects are already known, like the approximately 6,000 yeast ORFs, we may want to design a small set of primers to PCR amplify all the targets, which can then be resolved electrophoretically in a series of experiments. This would be quite useful, because decreasing the number of primers greatly reduces the cost of an experiment. This paper extends the problem of primer selection for a single experiment presented in Doi and Imai (Genome Informatics, 8:43-52, 1997) to primer selection for multiple PCR experiments, and proposes algorithms for the extended problem. The algorithms design primer sets one at a time. We extend the greedy algorithm for one PCR experiment in (Genome Informatics, 8:43-52, 1997) by handling amplified segments in DNA sequences that have been identified by primer pairs already selected and by changing the priorities in the greedy algorithm. This algorithm is applied to real yeast data. The number of primers equaled 85% of the number of identified DNA sequences, which represented more than 90% of all the target DNA sequences. This is 42% the number of primers needed for multiplex PCR. Furthermore, the length of each primer is less than half the length of multiplex PCR primers so the cost of producing the primers is reduced to 20% of the cost in the multiplex PCR case.