Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints

Details Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints

2004-06-28

arxiv.org/abs/cs/0406053v2

Computer Science

Data Structures and Algorithms

Scientific paper

A critical problem in the emerging high-throughput genotyping protocols is to minimize the number of polymerase chain reaction (PCR) primers required to amplify the single nucleotide polymorphism loci of interest. In this paper we study PCR primer set selection with amplification length and uniqueness constraints from both theoretical and practical perspectives. We give a greedy algorithm that achieves a logarithmic approximation factor for the problem of minimizing the number of primers subject to a given upperbound on the length of PCR amplification products. We also give, using randomized rounding, the first non-trivial approximation algorithm for a version of the problem that requires unique amplification of each amplification target. Empirical results on randomly generated testcases as well as testcases extracted from the from the National Center for Biotechnology Information's genomic databases show that our algorithms are highly scalable and produce better results compared to previous heuristics.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-385512