Speaker: Ion Mandoiu

Day:  Wednesday, 09/7/2005
Room: ITE 336
Time: 3:30pm

Title: Exact and Approximation Algorithms for DNA Tag Set Design


----------------------------------------------------------------------------

Abstract:
High throughput genomic technologies have revolutionized biomedical
sciences, and progress in this area continues at an accelerated pace in
response to the increasingly varied needs of biomedical research. A
promising emerging technology is the use of universal DNA tag arrays,
which provide unprecedented assay customization flexibility while
maintaining a high degree of multiplexing and low unit cost.  In this talk
I will present some recent exact and approximation algorithms for an
interesting combinatorial optimization problem arising in this area: the
tag set design problem.  I will show that previous formalizations of the
problem can be solved to optimality for problem instances of moderate size
via integer programming, and describe more scalable algorithms based on an
approximation scheme for packing linear programs due to Garg and Konemann.
I will also discuss an interesting connection between tag design and the
problem of packing the maximum number of vertex-disjoint directed cycles
in a given graph, and show that combining a simple greedy cycle packing
algorithm yields an increase of over 40% in the number of tags compared to
previous methods.  This is joint work with Dragos Trinca.