EXPLOITING SYMMETRY PROPERTIES OF THE DISCRETIZABLE MOLECULAR DISTANCE GEOMETRY PROBLEM

The Discretizable Molecular Distance Geometry Problem (DMDGP) involves a subset of instances of the distance geometry problem for which some assumptions allowing for discretization are satisfied. The search domain for the DMDGP is a binary tree that can be efficiently explored by employing a Branch & Prune (BP) algorithm. We showed in recent works that this binary tree may contain several symmetries, which are directly related to the total number of solutions of DMDGP instances. In this paper, we study the possibility of exploiting these symmetries for speeding up the solution of DMDGPs, and propose an extension of the BP algorithm that we named symmetry-driven BP (symBP). Computational experiments on artificial and protein instances are presented.

Polymer principles and protein folding

This paper surveys the emerging role of statistical mechanics and polymer theory in protein folding. In the polymer perspective, the folding code is more a solvation code than a code of local phipsi propensities. The polymer perspective resolves two classic puzzles: (1) the Blind Watchmaker's Paradox that biological proteins could not have originated from random sequences, and (2) Levinthal's Paradox that the folded state of a protein cannot be found by random search. Both paradoxes are traditionally framed in terms of random unguided searches through vast spaces, and vastness is equated with impossibility. But both processes are partly guided. The searches are more akin to balls rolling down funnels than balls rolling aimlessly on flat surfaces. In both cases, the vastness of the search is largely irrelevant to the search time and success. These ideas are captured by energy and fitness landscapes. Energy landscapes give a language for bridging between microscopics and macroscopics, for relating folding kinetics to equilibrium fluctuations, and for developing new and faster computational search strategies.