Speaker: Jorge Duitama
Day:  Wednesday, 10/31/2007
Room: ITEB 336
Time: 2:00-3:00pm

Title: Multiplex PCR Primer Set Selection with Amplification Length
Constraints

Abstract:
 
Primers selection for multiplex PCR induces a NP-Hard minimization problem
on the number of primers needed to amplify all desired loci, subject to a
constraint on the product length. Approximation algorithms have been
developed to find nearly optimal solutions with a feasible runtime by
translating the original problem into a well known one like Set Cover or
ILP. In this talk there are going to be discussed two ILP approaches and
the original set cover problem greedy algorithm to go toward a generic
greedy algorithm based on a potential function that describes what is the
gain reached with each selected primer. A good approximation guarantee for
this algorithm is going to be proven.
 
Reference:
 
K. Konwar, I.I. Mandoiu, A. Russell, and A. Shvartsman. Exact and
approximation algorithms for multiplex PCR primer set selection with
amplification length constraints. In I.I. Mandoiu and A.Z. Zelikovsky
(Eds.), Bioinformatics Algorithms: Techniques and Applications. Wiley (to
appear).