2004/06/28 by K. Konwar, Kishori M. Konwar, Ion Măndoiu +9
Biochemistry, Genetics and Molecular Biology · Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Biological sciences #FOS: Computer and information sciences #G.1.6 #Gene expression and cancer classification #Genomic variations and chromosomal abnormalities #Molecular Biology Techniques and Applications #Quantitative Methods (q-bio.QM) #cs.DM #cs.DS #q-bio.QM
paper · pdf · doi:10.48550/arxiv.cs/0406053
openalex publication_date 2004/06/28 · arxiv created 2004/07/27 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.