@inproceedings{Bac:Wil:GCB98,
author = {Backofen, Rolf and Will, Sebastian},
title = {Structure Prediction in an {HP}-type Lattice with an Extended
         Alphabet},
booktitle = {Proc of German Conference on Bioinformatics (GCB'98)},
year = {1998},
doi = {https://dblp.org/db/conf/gcb/gcb1998.html},
user = {will},
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.}
}