Back to search

Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2006

Algorithms & experiments for the protein chain lattice fitting problem

Abstract

dc:description.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).

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2006
Year dc:date.issued
2006

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Thomas, Dallas
  • University of Lethbridge. Faculty of Arts and Science
Advisor dc:contributor.supervisor
  • Guar, Daya

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/535

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Thomas, Dallas; University of Lethbridge. Faculty of Arts and Science. Algorithms & experiments for the protein chain lattice fitting problem. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2006, 2006. https://hdl.handle.net/10133/535