Supervised learning to tune simulated annealing for in silico protein structure prediction

in Verleysen, Michel (Ed.) ESANN 2012 proceedings, 20th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (2012, April 25)

Simulated annealing is a widely used stochastic optimization algorithm whose efficiency essentially depends on the proposal distribu- tion used to generate the next search state at each step. We propose ... [more ▼]

Simulated annealing is a widely used stochastic optimization algorithm whose efficiency essentially depends on the proposal distribu- tion used to generate the next search state at each step. We propose to adapt this distribution to a family of parametric optimization problems by using supervised machine learning on a sample of search states derived from a set of typical runs of the algorithm over this family. We apply this idea in the context of in silico protein structure prediction. [less ▲]

Prédiction de structures de macromolécules par apprentissage automatique

Master's dissertation (2011)

Proteins are an essential constituent of cellular life whose biggest part of their function is determined by their tridimensional shape. Nowadays, however, no method is able to predict efficiently ... [more ▼]

Proteins are an essential constituent of cellular life whose biggest part of their function is determined by their tridimensional shape. Nowadays, however, no method is able to predict efficiently tridimensional protein structures based only on their amino acids sequence. We propose here an "ab initio" approach based on the concept of learning for search. Protein structure prediction is modeled in the form of an optimization problem solved by an optimization algorithm that follows an iterative framework in which a structure modification operator is selected and then applied to the current structure. The quality of the new structure is then assessed by an oracle that will determine whether or not the structure is accepted. The repetition of this framework will eventually lead to the sought structure. The critical point of this rationale lies in the choice of the modification operator, which has to be done very accurately in order to avoid the classical pitfalls of optimization problems. The operator selection step will then be subjected to machine learning thus legitimizing the term "learning for search" of the proposed method. The goal of this thesis is to show that machine learning can improve the results obtained via a simple optimization procedure. Our experiments show that this goal is fulfilled. We however know that many choices that we did should be questioned regarding both the optimization and the machine learning procedures. Finally, we can notice that the application domain of this work extends beyond the protein structure prediction problem. There exist indeed many optimization problems in the scientific literature for which no exact neither approximation algorithm exists and that are thus still very badly solved. Such problems could greatly benefit from a "learning for search" approach such as the one described in this work. [less ▲]