Natural language parsing and protein folding
Prof. Julia Hockenmaier
University of Illinois at Urbana-Champain
February 28, 2008
Bailey 201

We know that people have no problem understanding their native language. Otherwise, we wouldn't be able to communicate. We also know that proteins, the molecules which are involved in many chemical reactions in every cell of any living organism, fold spontaneously into specific three-dimensional structures. Otherwise, the organism would not live.

As computer scientists we may want to design systems that can either parse natural language or predict the folded structure of proteins. However, a sentence that appears in a newspaper may have millions of possible grammatical analyses, and a protein may have millions of possible structures. That is, in both cases we are faced with very hard search problems. I hope that I will be able to convince you that those two search problems are in fact very similar, and can therefore be addressed with very similar computational techniques.