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.