Algorithms & experiments for the protein chain lattice fitting problem
Date
2006
Authors
Thomas, Dallas
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2006
Abstract
This study seeks to design algorithms that may be used to determine if a given lattice is
a good approximation to a given rigid protein structure. Ideal lattice models discovered
using our techniques may then be used in algorithms for protein folding and inverse protein
folding.
In this study we develop methods based on dynamic programming and branch and bound
in an effort to identify “ideal” lattice models. To further our understanding of the concepts
behind the methods we have utilized a simple cubic lattice for our analysis. The algorithms
may be adapted to work on any lattice. We describe two algorithms. One for aligning the
protein backbone to the lattice as a walk. This algorithm runs in polynomial time. The second
algorithm for aligning a protein backbone as a path to the lattice. Both the algorithms
seek to minimize the CRMS deviation of the alignment. The second problem was recently
shown to be NP-Complete, hence it is highly unlikely that an efficient algorithm exists. The
first algorithm gives a lower bound on the optimal solution to the second problem, and can
be used in a branch and bound procedure. Further, we perform an empirical evaluation of
our algorithm on proteins from the Protein Data Bank (PDB).
Description
ix, 47 leaves ; 29 cm.
Keywords
Dissertations, Academic , Computer algorithms , Lattice paths , Protein folding -- Computer programs , Proteins -- Computer programs