Selecting a good collection of primers is very important for
polymerase chain reaction (PCR) experiments.
Most existing algorithms for primer selection
are concerned with computing a primer pair
for each DNA sequence. 
We consider  selecting a  small set of primers which amplify 
all DNA sequences by allowing each primer matches  several places.
This is quite useful because deceasing the number of primers greatly
reduces the cost of biological experiments.

First, we formulate the primer selection problem
and analyze the complexity of these  problems. 
A simple formulation to cover all sequences can be reduced to a set cover problem.  
 By using the greedy algorithm, we obtain a nice collection of primers 
in this case.
Due to the necessity of resolving amplified parts by electrophoresis, the 
length of each amplified part by PCR should be different. 
With this length constraint, the problem is shown to be much harder to solve from 
the complexity and approximability viewpoints. 
Our results  demonstrate 
that a clear complexity gap exists between cases with and without 
the length constraint.


Next, we implement the greedy algorithm for the simple formulation 
and apply it to real yeast data.  It is observed that solutions by this greedy algorithm do 
not satisfy biological constraints, such as minimum length constraint 
and distinct length constraint for amplified segments. 
We extend the greedy algorithm by  introducing prohibitive conditions to satisfy 
the biological constraints, by which a good solution is obtained. 

Finally, we construct algorithms which 
design the sets of primers  
for multiple experiments by extending these greedy algorithms.
We obtain primer sets which distinguish half of all yeast DNA sequences.