Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 6 / Issue 6

available in:   PDF (400 kB) PS (250 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-006-06-0560


Invariant Patterns in Crystal Lattices: Implications for Protein Folding Algorithms

William E. Hart (Sandia National Laboratories, USA)

Sorin Istrail (Celera Genomics, USA)

Abstract: Crystal lattices are infinite periodic graphs that occur naturally in a variety of geometries and which are of fundamental importance in polymer science. Discrete models of protein folding use crystal lattices to define the space of protein conformations. Because various crystal lattices provide discretizations of the same physical phenomenon, it is reasonable to expect that there will exist "invariants" across lattices related to fundamental properties of the protein folding process. This paper considers whether performance-guaranteed approximability is such an invariant for HP lattice models. We define a master approximation algorithm that has provable performance guarantees provided that a specific sublattice exists within a given lattice. We describe a broad class of crystal lattices that are approximable, which further suggests that approximability is a general property of HP lattice models.

1 C.S.Calude and G.Stefanescu (eds.). Automata, Logic, and Computability. Special issue dedicated to Professor Sergiu Rudeanu Festschrift.

Keywords: HP model, Protein folding, approximation algorithm, lattice models

Categories: F.2, J.3