Natural language research announcements

["Margaret M. Fleck" <mfleck AT cs.uiuc.edu>]

COMPUTER SCIENCE COLLOQUIUM


  Protein Folding and Parsing


    Julia Hockenmaier
    Institute for Research in Cognitive Science
    University of Pennsylvania

    April 12 (Thursday), 2007 at 10:00 a.m.
    2405 Siebel Center for Computer Science
        
                        
We know that adult speakers of a language have no problem understanding 
newspapers in that language, and that proteins fold spontaneously into 
specific three-dimensional structures. However, a sentence in the Wall 
Street Journal may have millions of possible grammatical analyses, and a

protein may have millions of possible structures. As computer scientists

who want to design systems that can either parse natural language or 
predict the folded structure of proteins, we are faced with two very 
similar search problems: In both cases, we want to find the optimal 
structure of an input sequence among an exponential number of possible 
alternatives.

The first part of my talk will be a brief introduction to statistical 
parsing of natural language. I will use my own work on wide-coverage 
parsing with a linguistically expressive grammar to illustrate the 
questions that arise in this field.

In the second, longer, part of my talk, I will demonstrate how CKY, a 
standard dynamic programming algorithm that is normally used in natural 
language parsing, can be adapted to give us novel insights into the 
protein folding problem. If we assume that folding is a greedy, 
hierarchical search for lowest-energy structures, CKY provides an 
efficient way to find all direct folding routes. I will also show that 
we can extend CKY to construct a Markov chain model of the entire 
folding process, and that this Markov chain may explain an apparent 
contradiction between what experimentalists observe in a test tube and 
what many theorists predict.


Bio:
Julia Hockenmaier is a postdoc with Aravind Joshi at the University of 
Pennsylvania, and also a frequent visitor to Ken Dill's lab at the 
University of California at San Francisco.  Her research areas are 
natural language processing (computational linguistics) and 
computational biology, specifically natural language parsing and protein

folding.

She received her PhD in 2003 from the University of Edinburgh, where she

was working with Mark Steedman on the creation of the first 
wide-coverage statistical Combinatory Categorial Grammar parser. 
Julia's dissertation was one of the five runners-up for the British 
Computer Society's Distinguished Dissertation Award 2004 (an award for 
the best Computer Science dissertation in the UK).


If you would like to subscribe to announcement:
http://mail.cs.uiuc.edu/mailman/listinfo/announce