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). / ix, 47 leaves ; 29 cm.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:ALU.w.uleth.ca/dspace#10133/535 |
| Date | January 2006 |
| Creators | Thomas, Dallas, University of Lethbridge. Faculty of Arts and Science |
| Contributors | Guar, Daya |
| Publisher | Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2006, Faculty of Arts and Science, Department of Computer Science |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
| Relation | Thesis (University of Lethbridge. Faculty of Arts and Science) |
Page generated in 0.0019 seconds