CS 789 THEORY SEMINAR [home]

Speaker:  Klara Kedem
Affiliation: Computer Science, Ben Gurion University and Cornell University
Date: Monday, September 16, 2002
Title: Shape Matching Algorithms for Proteins:
         Consensus Structures for Protein Families

Abstract:

We investigate methods to compare protein 3D structures. In particular, we consider the problem of identifying a consensus three-dimensional structure for a family of proteins. Just as the profile of a protein family summarizes the sequence data for a protein --- by providing a probability for each amino acid (or a gap) at each residue location --- the consensus structure summarizes the structural data for a protein family. The idea is to construct a representative "average" shape for a protein family, a shape that highlights similarities and dissimilarities among members of the family. As an important by-product, our work can be used to find the multiple structural alignment of the proteins in the family.

We define a unique $4$-dimensional consensus structure (where the fourth dimension represents a gap coordinate). We prove the properties of this structure and describe its interpretations and uses. We present an iterative algorithm to compute the consensus structure and argue that, in practice, this algorithm converges quickly to the optimal result. The algorithm has been used to compute consensus structures for several known protein families. 

The consensus structure appears to be a useful tool for exploring the relation between sequence and structure. For example, in ongoing research, we compare our multiple structural alignment with multiple sequence alignment for protein families.

Joint work with Paul Chew.