Name
Title | ||
|---|---|---|
Lattice and off-lattice side chain models of protein folding (extended abstract): linear time structure prediction better than 86% of optimal |
Abstract | ||
|---|---|---|
This paper considers the protein structure prediction problem for lattice and off-lattice protein folding models that explicitly represent side chains. Lattice models of pro- teins have proven extremely useful tools for reasoning about protein folding in unrestricted continuous space through anal- ogy. This paper provides the first i1ustration of how rigorous algorithmic analyses of lattice models can lead to rigorous algorithmic analyses of off-lattice models. We consider two side chain models: a lattice model that generalizes the HP model (Dill 85) to explicitly represent side chains on the cubic lattice, and a new off-lattice model, the HP Tangent Spheres Side Chain model (HP-TSSC), that generalizes this model further by representing the backbone and side chains of proteins with tangent spheres. We describe algorithms with mathematically guaranteed error bounds for both of these models. In particular, we describe a linear time per- formance guaranteed approximation algorithm for the HP side chain model that constructs conformations whose en- ergy is better than 86% of optimal in a face centered cubic lattice, and we demonstrate how this provides a 70% per- formance guarantee for the HP-TSSC model. This is the first algorithm in the literature for off-lattice protein struc- ture prediction that has a rigorous performance guarantee. Our analysis of the HP-TSSC model builds off of the work of Dancik and Hannenhalli who have developed an approx- imation algorithm for the HP model on the hexagonal close packed lattice. Further, our analysis provides a mathemat- ical methodology for transferring performance guarantees on lattices to off-lattice models. These results partially an- swer the open question of Karplus et al. (1994) concerning i,he complexity of protein folding models that include side |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1145/267521.267540 | Journal of Computational Biology |
Keywords | Field | DocType |
protein folding,off-lattice side chain model,linear time structure prediction,computational biology,branch and cut | Statistical physics,Discrete mathematics,Protein folding,Lattice (order),Branch and cut,Genetics,Time complexity,Mathematics,Side chain | Conference |
Volume | Issue | ISBN |
4 | 3 | 0-89791-882-7 |
Citations | PageRank | References |
32 | 4.54 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| William E. Hart | 1 | 1028 | 141.71 |
| Sorin Istrail | 2 | 1415 | 170.40 |