Title: Optimal Robust Non-Unique Probe Selection Using Integer Linear  Programming
Speaker: Gunnar Klau, University of Vienna
Date: Thursday, Feb 12, 12-13, room 3501





Abstract
--------
Abstract:
---------

The talk covers a mathematical problem that arises in the area of
computational biology: the optimal selection of probes for microarray
experiments. Besides their prevalent use for analyzing gene expression,
microarrays are an efficient tool for biological, medical, and industrial
applications due to their ability to assess the presence or absence of
biological agents, the targets, in a sample. Given a collection of genetic
sequences of targets one faces the challenge of finding short
oligonucleotides, the probes, which allow detection of targets in a
sample.

Each hybridization experiment between a target and a probe determines
whether the short oligonucleotide probe binds to its
corresponding sequence in the target.  Depending on the problem, the
experiments are conducted using either unique or
non-unique probes and usually under the assumption that only one
target is present in the sample.  Assuming the oligonucleotides are
given, the problem at hand is to compute a design, i.e., a
minimal set of probes that allows to infer the targets in the
sample from the result of the hybridization experiment. If we allow to
test for more than one target in the sample, the design of the probe set
becomes difficult in the case of non-unique probes.

The presentation describes the first exact approach to select a
(minimal) probe set for the case of non-unique probes and the presence
of (a small number of) multiple targets in the sample. The approach is
based on an ILP formulation that is the basis for a branch-and-cut
algorithm.  Our preliminary implementation already greatly reduces the
number of oligos needed while preserving the decoding capabilities.

joint work with: Sven Rahmann, Knut Reinert, Alexander Schliep, and Martin 
Vingron

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

Gunnar Klau studied computer science in W"urzburg, Padova
and Saarbr"ucken where he got his Diplom in 1997.
He started his PhD research in Saarbr"ucken under the supervision
of Petra Mutzel, who in 1999 became a professor at the
Vienna University of Technology.
In 2001, he got his PhD in Saarbr"ucken with a thesis on
"A Combinatorial Approach to Orthogonal Placement Problems". 
In 2002/2003, he spent a year at the Department of Discrete
Optimization (headed by Prof. Martin Gr"otschel)
at the Konrad-Zuse-Zentrum f"ur Informationstechnik Berlin (ZIB).
Currently, he is a research associate at the
Vienna University of Technology.
His homepage is http://www.ads.tuwien.ac.at/~guwek.

For both his Diplom thesis and PhD thesis his was awarded prizes.
In 1997, he won the German Student Research Prize
(Deutscher Studienpreis) by the K"orber Foundation.
In 2002, he won the Dissertation Prize of the German Operations
Research Society (GOR), sponsored by SAP AG.