Institutional Repository

Algorithms & experiments for the protein chain lattice fitting problem

DSpace/Manakin Repository

Show simple item record

dc.contributor.advisor Guar, Daya
dc.contributor.author Thomas, Dallas
dc.contributor.author University of Lethbridge. Faculty of Arts and Science
dc.date.accessioned 2007-11-29T16:31:32Z
dc.date.available 2007-11-29T16:31:32Z
dc.date.issued 2006
dc.identifier.uri http://hdl.handle.net/10133/535
dc.description ix, 47 leaves ; 29 cm. en
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). en
dc.language.iso en_US en
dc.publisher Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2006 en
dc.relation.ispartofseries Thesis (University of Lethbridge. Faculty of Arts and Science) en
dc.subject Dissertations, Academic en
dc.subject Computer algorithms en
dc.subject Lattice paths en
dc.subject Protein folding -- Computer programs en
dc.subject Proteins -- Computer programs en
dc.title Algorithms & experiments for the protein chain lattice fitting problem en
dc.type Thesis en
dc.publisher.faculty Faculty of Arts and Science en
dc.publisher.department Department of Computer Science en


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account

Statistics