The Density Constraint

Abstract

The paper expands on the growing body of literature which makes use of constraint programming techniques to solve bioinformatics problems, es- pecially in the context of discrete models. The focus is on the use of constraint programming methodologies to solve the problem of prediction of real-size pro- tein structures. In particular, the paper builds on the good results obtained using simplified energy models (e.g., HP [1]) and bioinformatics-specific global con- straints [3]. The paper shows how information obtained through electron cryomi- croscopy can help this research. The density maps obtained from cryomicroscopy are formalized as global constraints and used to further prune the space of pos- sible configurations of amino acids in the 3D space. The paper investigates the complexity of these new global constraints, and presents a preliminary imple- mentation of the associated propagation procedures.