PSICO
PSICO stands for Processing Structural Information with Constraint programming and Optimisation. The relevant publications on this work are:
Krippahl, L., Barahona, P., PSICO: Solving Protein Structures with Constraint Programming and Optimisation, Constraints 2002, 7, 317-331. Download .pdf
Krippahl, L, Barahona P, Propagating N-ary Rigid-Body Constraints, (2003). Principles and Practice of Constraint Programming, CP'2003 (Procs.), Francesca Rossi (Ed.), Lecture Notes in Computer Science, vol. 2833, Springer, pp. 452-465, October, 2003. Download .pdf
Constraint Propagation
Each atom is represented by one cuboid delimiting the volume where the atom can be placed and a set of zero or more additional cuboids indicating regions within the first volume from which the atom must be excluded. Distance constraints are propagated by intersecting or adding cuboid regions until arc-consistency (AC-3).
Enumeration
After enforcing arc-consistency, one domain is split in two and one half discarded, setting off a new propagation cycle. Failures, indicated by empty domains, result in backtracking to redo the split selecting the part that was previously discarded.
Local search
After all domains have a longest dimension of 2 Angstrom, or after a preset number of backtracking steps, the domains are used to fit a torsion angle model of the protein, which in turn serves as a starting point for a local search minimisation of all constraint violations.