Abstract.

We consider the problem of determining the three-dimensional folding of a protein given its one-dimensional amino acid sequence. We use the HP model for protein folding proposed by Dill (1985), which models protein as a chain of amino acid residues that are either hydrophobic or polar, and hydrophobic interactions are the dominant initial driving force for the protein folding. Hart and Istrail (1996) gave approximation algorithms for folding proteins on the cubic lattice under HP model. In this paper, we examine the choice of a lattice by considering its algorithmic and geometric implications and argue that triangular lattice is a more reasonable choice. We present a set of folding rules for a triangular lattice and analyze the approximation ratio which they achieve. In addition, we introduce a generalization of the HP model to account for residues having different levels of hydrophobicity. After describing the biological foundation for this generalization, we show that in the new model we are able to achieve similar constant factor approximation guarantees on the triangular lattice as were achieved in the standard HP model. While the structures derived from our folding rules are probably still far from biological reality, we hope that having a set of folding rules with different properties will yield more interesting folds when combined.

Note: Extended abstract (163K) appeared in the Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97), (1997):390-399.

Note: 2 page abstract (64K) appeared in the Proceedings of the First Annual International Conference on Computational Molecular Biology (RECOMB'97), (1997):1-2.

Bibtex entries:

@Article{ABDDFHMS97,
  author =       "R. Agarwala and S. Batzoglou and V. Dan{\v c}{\'\i}k and 
                  S. Decatur and S. Hannenhalli and M. Farach and 
                  S. Muthukrishnan and S. Skiena",
  title =        "Local Rules for Protein Folding on a Triangular Lattice 
                  and Generalized Hydrophobicity in {HP} Model",
  booktitle =    "Journal of Computational Biology",
  year =         "1997",
  volume =       "4",
  number =       "2",
  pages =        "275-296"
}


@InProceedings{ABDDFHS97,
  author =       "R. Agarwala and S. Batzoglou and V. Dan{\v c}{\'\i}k and 
                  S. Decatur and S. Hannenhalli and M. Farach and S. Skiena",
  title =        "Local Rules for Protein Folding on a Triangular Lattice 
                  and Generalized Hydrophobicity in {HP} Model",
  booktitle =    "8th Annual ACM-SIAM Symposium on Discrete Algorithms, 
                  Proceedings",
  year =         "1997",
  pages =        "390-399"
}


@InProceedings{ABDDFHMS97,
  author =       "R. Agarwala and S. Batzoglou and V. Dan{\v c}{\'\i}k and 
                  S. Decatur and S. Hannenhalli and M. Farach and 
                  S. Muthukrishnan and S. Skiena",
  title =        "Local Rules for Protein Folding on a Triangular Lattice 
                  and Generalized Hydrophobicity in {HP} Model",
  booktitle =    "Proceedings of the First Annual International Conference on
                  Computational Molecular Biology",
  year =         "1997",
  pages =        "1-2"
}

Return to Previous Level

USC Computational Biology Home Page