title: A new approach to primer selection in polymerase chain reaction experiments.
abstract: 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 NP-complete, and show that even approximating solutions to this problem to within a constant factor times optimal is intractable. On the practical side, we give a simple branch-and-bound algorithm that solves the primers minimization problem within reasonable time for typical instances. We present an efficient approximation scheme for this problem, and prove that our heuristic always produces solutions no worse than a logarithmic factor times the optimal, this being the best approximation possible within polynomial time. 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 presenting the empirical performance of our methods on biological data.
authors.affiliation: Department of Computer Science, University of Virginia, Charlottesville 22903-2442, USA.
authors.forename: W R
authors.initials: WR
authors.lastname: Pearson
authors.forename: G
authors.initials: G
authors.lastname: Robins
authors.forename: D E
authors.initials: DE
authors.lastname: Wrege
authors.forename: T
authors.initials: T
authors.lastname: Zhang
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D004247:DNA / Q000737:chemistry* / Q000378:metabolism*; D017931:DNA Primers; D008962:Models, Theoretical; D016133:Polymerase Chain Reaction; D012984:Software
chemical_list: D017931:DNA Primers; D004247:DNA