Title: Efficient Algorithms to Sample Closed Clash-Free Conformations of Protein Loops

Abstract: Several applications in biology--e.g., incorporation of protein fexibility in ligand docking algorithms, interpretation of fuzzy X-ray crystallographic data, and homology modeling--require computing the internal parameters of protein fragments--often loops in order to connect their termini to the rest of the protein without causing any steric clash inside the fragment and with the rest of the protein. In most applications, one must sample many such conformations, for instance to optimize an objective function or to get an adequate representation of the conformational range of the studied fragment. While sampling must be fast, it is made difficult by the fact that two often conflicting constraints--kinematic closure and clash avoidance--must be satisfied concurrently. This talk describes two efficient and complementary algorithms to sample the set of closed clash-free conformations of a given loop. The "seed sampling" algorithm samples broadly distributed conformations from this set. The "deformation sampling" algorithm uses these conformations as starting points to explore more finely selected regions of the set. The algorithms are implemented in a software toolkit, LoopTK, available at http://ai.stanford.edu/looptk.