ICS Theory Group

ICS 269, Winter 2000: Theory Seminar

10 March 2000:
A polynomial time algorithm for counting protein aggregation packings
Mac Casale, ICS, UC Irvine

We present an algorithm for the enumeration of packings of peptide chains. This algorithm is one part of the larger problem of simulating protein aggregation such as occurs in Alzheimer's, Huntington's and other neurodegenerative diseases. We briefly present the problem context, including the medical need and an overview of the protein folding and aggregation problems, and then concentrate on the enumeration algorithm. This algorithm is shown to be O(|L|^4 |a||b|^2), where L is the dimension of the lattice, |a| is the length of the peptide that is held fixed during the enumeration and |b| is the length of the peptide whose position and orientation are varied. After presenting the basic algorithm, we give several improvements suggested by the author for reducing time and/or space, making use of, among other things, multi-dimensional hash tables. The talk concludes with speculation on further improvements of the enumeration algorithm as integrated into the protein aggregation problem.

(Based on S. Istrail, R. Schwartz, and J. King, "Lattice simulations of aggregation funnels for protein folding", J. Comp. Bio. 6(2):143-162, 1999.)