[Colloquium] Reminder: Jinbo Xu Talk Today @ 3pm

[Katherine Cumming]

Jinbo Xu 
Massachusetts Institute of Technology
Fast and Accurate Protein Structure Prediction
April 4, 2005 3:00pm
Abstract:
If we know the primary sequence of a protein, can we predict its
three-dimensional structure by computational approaches? This is one of
the most important and difficult problems in computational molecular
biology and has tremendous implications for the field of proteomics.

In this talk, I will present two efficient algorithms to solve two key
problems of protein structure prediction: backbone prediction by protein
threading technique and side-chain prediction. Both problems are NP-hard
and hard to approximate.

First, I will present a linear integer programming approach to the
protein threading problem. With a theoretically-grounded formulation,
this approach will lead to an amazing result: almost all the relaxed
linear program instances will produce integral solutions directly,
without using branch-and-bound. This result indicates that the protein
threading problem is tractable empirically although it is hard
theoretically. Next, I will describe a novel approach to the protein
side-chain packing problem, based on the tree-decomposition of a protein
structure. This algorithm not only runs very efficiently in practice,
but also yields a polynomial-time approximation scheme for some types of
objective functions.<BR.
I have implemented the proposed algorithms combined with several other
components as two protein structure prediction programs RAPTOR (for
backbone prediction) and SCATD (for side-chain prediction). RAPTOR ranks
first among all the programs of its category in CASP5 and third in
CASP6, the most recognized competition in the area of protein structure
prediction. Without losing any prediction accuracy, SCATD achieves an
average speed five times faster than SCWRL 3.0, a widely-used side-chain
packing program, and runs up to 90 times faster on large proteins.


Jinbo Xu is a postdoctoral research fellow in the Mathematics Department
and Computer Science and AI lab, MIT. In the past four years he has
worked in several subfields of computational biology, including protein
structure prediction, protein structure alignment, and homology search.
He has developed several protein structure prediction tools, such as
RAPTOR, ACE, and SCATD. He received his PhD in 2003 from the University
of Waterloo, Canada, MSc in 1999 from the Chinese Academy of Sciences
and BSc in 1996 from the University of Science and Technology of China. 
If you have questions, or would like to meet the speaker, please contact
Katherine at 4-1994 or kcumming at tti-c.org. For information on future
TTI-C talks or events, please go to the TTI-C Events
<http://ttic.uchicago.edu/events/events_dyn.php>  page. 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20050404/2850da25/attachment.htm