

![0_image_0.png](0_image_0.png)

Still, the search tree reduction is not completely reflected in runtime **speedup,**
which illustrates the computational overhead of DDS in the current **prototypic**
implementation. Anyway, our data shows that DDS is well suited to improve solution counting even for dense graphs with P
e **about 40%. We expect even higher**
speedups and search-tree reductions if the solutions are counted completely, i.e. without the current upper bound of 1 million. Table 1 suggests that the speedup decreases with increasing number of nodes to color in the graph. With increasing number of nodes, the graph as well as the constraint graph **grow quadratically.**
The speedup is significantly lower than the reduction of the search tree. In part this can be ascribed to our implementation that rebuilds the constraint graph in each search step. A system that provides cheaper constraint graph access, e.g. by maintaining it incrementally, is expected to perform much better.

## 7.2 Optimal Protein Structure Prediction

The prediction of optimal (minimal energy) structures of simplified lattice proteins is a hard (NP-complete) problem in bioinformatics. Here we focus on the HP-model introduced by Lau and Dill [13]. In this model, a protein chain is reduced to a sequence of monomers of equal size, whereby the 20 **aminoacids** are grouped into hydrophobic (H) or polar (P). A structure is a self-avoiding walk of the underlying lattice (e.g. square or cubic). A contact energy function is used to determine the energy of a structure. The energy table and an example is given in Fig. 9. The problem is to predict minimal energy structures for a given HP-sequence.

The number and quality of optimal structures has applications in the **study**
of energy landscape properties, protein evolution and kinetics [9, 20, 25]. The constraint model**. In [2], the problem was successfully modeled as CSP**
and named Constraint-based Protein Structure Prediction (CPSP). Here, a variable is introduced for each sequence position and with lattice points as do-