ON THE PRIMER SELECTION PROBLEM IN POLYMERASE CHAIN-REACTION EXPERIMENTS

In this paper we address the problem of primer selection in polymerase chain reaction experiments. We prove that the problem of minimizing t he number of primers required to amplify a set of DNA sequences is NP- complete. Moreover, we show that it is also intractable to approximate solutions to this problem to within a constant times optimal. We deve lop a branch-and-bound algorithm that solves the primers minimization problem within reasonable time for typical instances. Next, we present an efficient approximation scheme for this problem, and prove that ou r heuristic always produces solutions with cost no worse than a logari thmic factor times optimal. Finally, we analyze a weighted variant, wh ere both the number of primers as well as the sum of their costs are o ptimized simultaneously. We conclude by addressing the empirical perfo rmance of our methods on biological data.