RPE: Nathan Clement, GDC 3.816

Contact Name: 
Lydia Griffith
May 14, 2014 2:00pm - 4:00pm

RPE: Nathan Clement

Title: Improvements in the protein side-chain packing problem
Date: May 14, 2014
Time: 2pm
Location: GDC 3.816
Committee Members: Chandrajit Bajaj, Peter Stone, Greg Plaxton

Protein structure design, the task of creating a 3-dimensional model of a protein from its given sequence (chain) of amino acids (residues), is a very difficult problem. One of the sub-problems of protein design is side-chain packing. Each residue in a protein chain consists of backbone and side-chain atoms.  Once the backbone atoms have been placed (by another sub-problem in the design pipeline), a specific placement of side-chain atoms in 3-dimensional space can be chosen. Since a given residue can contain up to 20 different side-chain atoms, the assignment of a given side-chain atom may effect neighboring atoms on the protein backbone. The optimal side-chain packing algorithm would choose an assignment that minimizes atomic clashes and the global energy. In continuous space, this problem quickly become intractable, but if the side chains are discretized into rotamers based on preferential conformations of each amino acid, the problem become somewhat simpler. However, even after discretizing into rotamers, the hardness is still O(Nk^N), where N is the number of residues and k is the average number of rotamers for a given amino acid.

In this presentation I will report on an algorithm that uses a graph coarsening technique to reduce the theoretical running time to O(Nk^{N^{2/3}\log N}). I will show that, even after this coarsening technique is used, the problem is still provably NP-Hard, but the actual running times are reasonable--especially for large molecules. I will also briefly outline a 1-\epsilon polynomial time approximation scheme that can be applied to larger problem sets.