Primer Selection Algorithms for CostEffective 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 stringpair covering formulation for the multiplex PCR primer set selection problem with amplification length constraints, and developed a greedy “potentialfunction” 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 LProunding, has an approximation factor of O(L log n), which asymptotically improves over the previously best approximation factor of min{sqrt(n),L^{2}}.

We have developed highly scalable distinguisher selection algorithms for a recently introduced genomicbased 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 largescale 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