An efficient algorithm for minimum degeneracy primer selection

Selecting degenerate primers for multiplex polymerase chain reaction (MP-PCR) experiments, called the degenerate primer design problem (DPDP), is an important problem in computational molecular biology and has drawn the attention of numerous researchers in the recent past. Several variants of DPDP were formulated by Linhart and Shamir and proven to be NP-complete. A number of algorithms have been proposed for one such variant, namely, the maximum coverage degenerate primer design problem (MC-DPDP). In this paper, we consider another important variant called the minimum degeneracy degenerate primer design with errors problem (MD-DPDEP), propose an algorithm to design a degenerate primer of minimum degeneracy for a given set of DNA sequences and show experimental results of its performance on random and real biological datasets. Our algorithm combines methodologies in motif discovery and an iterative technique to design the primer.