Prelegent: Marcin Wierzbiński

The modeling of protein folding, a biological issue, is particularly intriguing. The deterministic solution of the so-called hydrophobic-polar (HP) protein folding model is one such problem. It turns out that the Monte Carlo methods used in computer science and statistics are quite relevant to this model.

The A* search algorithm for the protein folding problem in the HP model is introduced in this talk. There are primarily two difficulties. The problem is first shown to be NP-hard. Second, without prior knowledge of the HP model, the solution cannot be easily found using a search method in the vast solution space.