## 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.)