Algorithms & experiments for the protein chain lattice fitting problem

Simple item page
dc.contributor.authorThomas, Dallas
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorGuar, Daya
dc.date.accessioned2007-11-29T16:31:32Z
dc.date.available2007-11-29T16:31:32Z
dc.date.issued2006
dc.degree.levelMasters
dc.descriptionix, 47 leaves ; 29 cm.en
dc.description.abstractThis 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.identifier.urihttps://hdl.handle.net/10133/535
dc.language.isoen_USen
dc.publisherLethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2006en
dc.publisher.departmentDepartment of Computer Scienceen
dc.publisher.facultyFaculty of Arts and Scienceen
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en
dc.subjectDissertations, Academicen
dc.subjectComputer algorithmsen
dc.subjectLattice pathsen
dc.subjectProtein folding -- Computer programsen
dc.subjectProteins -- Computer programsen
dc.titleAlgorithms & experiments for the protein chain lattice fitting problemen
dc.typeThesisen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
THOMAS_DALLAS_MSC_2006.pdf
Size:
4.69 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.88 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses