@InProceedings{Bac:Wil:GCB98,
  author =       "Rolf Backofen and Sebastian Will",
  title =        "Structure Prediction in an {HP}-type Lattice with an Extended
                  Alphabet",
  booktitle =    "Proc of German Conference on Bioinformatics (GCB'98)",
  year =         1998,
  abstract = {
The protein structure prediction problem is one of the most important
problems in computational biology. This problem consists of finding
the conformation of a protein (given by a sequence of amino-acids)
with minimal energy. Because of the complexity of this problem,
simplified models like Dill's HP-lattice model
have become a major tool for investigating general properties of
protein folding. Even for this simplified model, the structure
prediction problem has been proven to be NP-complete.

A disadvantage of the HP-problem is its high degeneracy. I.e., for
every sequence there are a lot of conformations having the minimal
energy. For this reason, extended alphabets have been used in the
literature. One of these alphabets is the HPNX-alphabet, which
considers hydrophobic amino acids as well as positive and negative
charged ones.

In this paper, we describe an exact algorithm for solving the
structure prediction problem for the HPNX-alphabet.  To our knowledge,
our algorithm is the first exact one for finding the minimal
conformation of an lattice protein in a lattice model with an alphabet
more complex than HP.  We also compare our results with results as
given for the HP-model.
},
  user =	 {will}
}