Speaker:Hans Mittelmann,
Department of Mathematics and Statistics

Title:A New Method for the Exact Solution of Protein Structure Alignment Problems

Abstract:

The main purpose of this talk is to highlight the importance of optimization in computational biology and bioinformatics. A very important and difficult problem is that of identifying proteins by comparing them to known samples. The 3-d structure makes this problem considerably more challenging than the sequence alignment problem. Still, many methods have been developed and several made available on web servers. Most methods are approximate and do not have high success rates.

One of the more powerful techniques proposed recently is based on maximizing the Contact Map Overlaps of the pair. The contact map does not require a precalculated equivalence of protein residues. This problem can be formulated as a linear 0-1 optimization problem and be solved with specialized branch&cut techniques. It can also be seen as equivalent to the Maximal Independent (Stable) Set (MIS), or equivalently, to the Maximum Clique problem on certain graphs.

As a new method we propose to use semidefinite (SDP) relaxations to solve the MIS problem, specifically, computing the Lovasz theta number of the graph and to apply branch&bound. The SDP bound is much sharper than the LP relaxation making this approach feasible. It is still to be expected that the computational effort is not small. Consequently, we propose to use parallel computation for its solution.