Primer Selection Algorithms for Cost-Effective DNA Amplification by Multiplex PCR
Funding agency: University of Connecticut Research Foundation
Amount: $18,000
PI: Ion I. Mandoiu
Period: 06/2004 – 05/2005
The main research results obtained with support from this grant include the following:
-
We have introduced a new string-pair covering formulation for the multiplex PCR primer set selection problem with amplification length constraints, and developed a greedy “potential-function” algorithm with an approximation factor of 1+ln(Delta), where Delta is the maximum coverage gain of a primer. Comprehensive experiments on both synthetic and genomic database test cases show that our greedy algorithm obtains significant reductions in the number of primers compared with previous methods.
-
We have designed an approximation algorithm for the minimum PCR primer set selection problem with both amplification length and amplification uniqueness constraints. Our algorithm, which is based on LP-rounding, has an approximation factor of O(L log n), which asymptotically improves over the previously best approximation factor of min{sqrt(n),L2}.
-
We have developed highly scalable distinguisher selection algorithms for a recently introduced genomic-based identification technique called string barcoding. Our algorithms are the first to enable distinguisher selection based on whole genomic sequences of hundreds of microorganisms of up to bacterial size.
-
We have proposed new exact and approximation algorithms for designing tag sets for use in universal DNA arrays. Our algorithms yield an increase of over 40% in the number of tags compared to previous methods.
-
We have proposed methods for improving the multiplexing rate in large-scale genomic assays by combining primer selection with tag assignment. Experimental results on simulated data show that this integrated optimization leads to reductions of up to 50% in the number of required arrays.
Software Packages