On the Primer Selection Problem in Polymerase Chain Reaction ExperimentsReport
In this paper we address the problem of primer selection in polymerase chain reaction (PCR) experiments. We prove that the problem of minimizing the number of primers required to amplify a set of DNA sequences is <i>NP</i> -complete. Moreover, we show that it is also intractable to approximate solutions to this problem to within a constant times optimal. On the practical side, we give a simple branch-and-bound algorithm that solves the primers minimization problem within reasonable time for typical instances. Moreover, we present an efficient approximation scheme for this problem, and prove that our heuristic always produces solutions with cost no worse than a logarithmic factor times optimal. Finally, we analyze a weighted variant, where both the number of primers as well as the sum of their "costs" is optimized simultaneously. We conclude by addressing the empirical performance of our methods on biological data.
Note: Abstract extracted from PDF file via OCR
All rights reserved (no additional license for public reuse)
Robins, Gabriel, Dallas Wrege, Tongtong Zhang, and William Pearson. "On the Primer Selection Problem in Polymerase Chain Reaction Experiments." University of Virginia Dept. of Computer Science Tech Report (1993).
University of Virginia, Department of Computer Science