Approximation Algorithms for the Primer Selection, Planted Motif Search, and Related Problems

In this chapter, we consider two problems from computational biology, namely, primer selection and planted motif search (PMS). The closest string and the closest substring problems are closely related to the PMS problem. All of these problems have been proven to be NP-hard. We survey some representative approximation algorithms that have been proposed for these problems.