Item Details

On the Primer Selection Problem in Polymerase Chain Reaction Experiments

Robins, Gabriel; Wrege, Dallas; Zhang, Tongtong; Pearson, William
Robins, Gabriel
Wrege, Dallas
Zhang, Tongtong
Pearson, William
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
University of Virginia, Department of Computer Science, 1993
Published Date
Libra Open Repository
Logo for In CopyrightIn Copyright


Access Online