OPTIMIZATION TECHNIQUES FOR THE PROTEIN STRUCTURE PREDICTION PROBLEM
Dr Rolf Backofen, Institut für Informatik, Ludwig-Maximilians-Universität München, Germany

Abstract: The structure prediction problem is one of the most important unsolved problems in bioinformatics. To attack the problem, simplified models have been introduced to investigate general principles of protein folding. An important class of simplified models are lattice models, where the positions of the amino-acids are restricted to a regular lattice. Even for the simplified models, the structure prediction problem is NP-complete.

In this talk, I will define lattice models of proteins. Then I will present a constraint-based approach for the prediction of the native structure. One problem that arises is that the problem contains a lot of symmetries. For this reason, I will present a general method for excluding symmetries in constraint-based search. The method is not restricted to geometric symmetries (i.e., it can be used for arbitrary symmetries).

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 24 June 1999.

back