Greedy Heuristics for Degenerate Primer Selection ⋆

Abstract. Amplification of multiple DNA sequences in a single Polymerase Chain Reaction (PCR) experiment, called Multiplex PCR (MP-PCR), is a widely known laboratory technique that requires efficient selection of a set of synthetic strings called Degenerate Primers to result in successful PCR products. The Multiple Degenerate Primer Selection Problem (MDPSP) is a fundamental problem in molecular biology and has received attention from numerous researchers in the recent past. Several variants of MDPSP have been proved to be NP-Complete. Many heuristic algorithms exist in the literature for MDPSP that have been shown to perform well in practice on real biological data. In this paper, we present two new greedy heuristics for the problem, analyze their time and space complexities and compare the performance of one of the proposed algorithms on random and real biological data with that of two previously reported algorithms. Our results show that the proposed algorithm performs almost equally in terms of quality, i.e., the number of degenerate primers, and executes in time much less than the two algorithms, also eliminating the dependency on an empirical input parameter that the previous algorithms exhibit in their performance both in terms of quality and time of execution. Keywords: Degenerate Primers, Primers for MP-PCR, Multiplex Primers