In applications where a collection of similar sequences needs to be amplified through PCR, degenerate primers can be used to improve the efficiency and accuracy of amplification. Conceptually, a degenerate primer is a sequence in which some bases are ambiguous, in the sense that they can bind to more than one nucleotide. These ambiguous bases allow degenerate primers to bind to multiple target sequences. When designing degenerate primers, it is essential to find a good balance between high coverage (the number of amplified target sequences) and low degeneracy. In this paper, we propose a new heuristic, called RRD2P, for computing a pair of forward and reverse primers with near-optimal coverage, under the specified degeneracy threshold. The fundamental idea of our algorithm is to represent computing optimal primers as an integer linear program, solve its fractional relaxation, and then apply randomized rounding to compute an integral solution. We tested Algorithm RRD2P on three biological data sets, and our experiments confirmed that it produces primer pairs with good coverage, comparing favorably with a similar tool called HYDEN.
展开▼
