Protein folding and chart parsing

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 293–300, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Protein folding and chart parsing Julia Hockenmaier Aravind K. Joshi Institute for Research in Cognitive Science University of Pennsylvania Philadelphia, PA 19104, USA ��������  �� ��  �  �!!"# %$%� Ken A. Dill Dept. of Pharmaceutical Chemistry University of California, San Francisco San Francisco, CA 94143, USA $�� ���&'�() � �*+& ,-�%  �- �./0 $%� Abstract How can proteins fold so quickly into their unique native structures? We show here that there is a natural analogy between parsing and the protein folding problem, and demonstrate that CKY can find the na- tive structures of a simplified lattice model of proteins with high accuracy. 1 Introduction In statistical parsing, the task is to find the most likely syntactic structure for an input string of words, given a grammar and a probability model over the analyses defined by that grammar. Pro- teins are sequences of amino acids (polypeptide chains) that form unique, sequence-specific three- dimensional structures. The structure into which a particular protein folds has a lower energy than all other possible structures. In protein structure pre- diction, the task is thus to find the lowest-energy physical structure for an input sequence of amino acids, given a representation of possible structures and a function that assigns an energy score to these structures. There is therefore a natural analogy between these two seemingly unrelated computa- tional problems. Based on this analogy, we pro- pose an adaptation of the CKY chart parsing algo- rithm to protein structure prediction, using a well- known simplified model of proteins as proof of concept. Models of protein folding additionally aim to explain the process by which this structure for- mation takes place, and their validity depends not only on the accuracy of the predicted structures, but also on their physical plausibility. One com- mon proposal in the biophysical literature is that the folding process is hierarchical, and that folding routes are tree-shaped. CKY provides an explicit computational recipe to efficiently search (and re- turn) all possible folding routes. This sets it apart from existing folding algorithms, which are typi- cally based on Monte Carlo simulations, and can only sample one possible trajectory. Since we believe that there is much scope for future work in applying statistical parsing tech- niques to more detailed models of proteins, a sec- ondary aim of this paper is to provide an introduc- tion to the research questions that arise in protein folding to the NLP community. Proteins are essential components of the cells of any living organism, and their biological function (eg. as enzymes that catalyze certain reactions) de- pends on their three-dimensional structure. How- ever, genes only specify the linear, sequence of the amino acids, and the ribosome (the cell’s “pro- tein factory”) uses this information to assemble the polypeptide chain. Under “natural” condi- tions, these polypeptide chains then fold rapidly and spontaneously into their …

Content truncated to 500 words