Protein Structute Prediction is NP-Complete 

Unger and Moult showed that a lattice model of protein structure prediction is an NP-complete problem.  They mapped a known NP-complete problem, in polynomial time, to the protein structure prediction.  According to Mehul Khimasia, the author of the article on protein prediction, "a real protein has many more degrees of freedom than a simple lattice model, so it is justified to conclude that a 'real protein' structure prediction is also NP-complete."  This is the basis for the genetic algorithm approach to protein structure prediction.

The Lattice Model

In the lattice model of a protein, the positions of the monomer units are restricted to positions on a lattice.  These are often arranged in square or cubic patterns.  Since the computational power is limited, this simplification makes this model easier to use.  Although the model is less realistic, many features of the real protein system are mainained.  Most importantly this includes the interactions of the monomer units.  The lattice models have been used to study the folding process as well as simplified structure prediction.

Protein Structure prediction

Protein folding can best be understood by clicking to this site  which contains a clear diagram of the process.  The primary structure contains a simple one-dimensional string of amino acids.  The secondary structure is an alpha helix and /or a beta pleated sheet of amino acids.  The tertiary structure describes the overall appearance of the protein.  The folding in this structure is due to sulfhydril and hydrogen bonds and parts of the protein which are hydrophobic or hydrophillic.  The quaternary structure is how a specific protein fits into a protein complex.  The first problem in understanding protein folding is understanding the process itself.  The second is predicting the three-dimensional structure from the one-dimensional sequence of amino acids.  Since these problems are NP-complete, the DNA computer will be used to investigate and predict these structures.
 

Diseases Caused By Protein Pathology

I. Ciliac Disease

 This disease involves a malfunction in the production of the protein filament cilia which line the small intestine.  The structure of the protein is somehow compromised(to how it is currently unknown)  to where it no longer functions to push food along the small intestine.  Whether the malfunction occurs in the primary, secondary, tertiary, or quaternary structure is unknown.

II Tay-Sachs Disease

  In this disease the enzyme lipase is dysfunctional and fails to digest the fatty acids which in turn pass the blood-brain barrier (through which nothing is supposed to pass) and cause retardation in the brain.  The reason for the defect in lipase is a problem in the construction of the protein structure either in the primary, secondary, tertiary, quaternary or all four areas of the folding process.

III. Cancer

 Certain types of cancer are caused by mutated or deregulated expression of proteins. These proteins can only bend to their cognate DNA enhancer sites following homodimerization or heterodimerization with another family member.  Dimerization is the result of two proteins folded on to each other so that one blocks the proper folding of the other.  According to Dr. Glenn King, a professor at the University of Sydney, an anti-cancer strategy would be to inhibit dimerization of these proteins which would block the DNA binding.
 
Summary

 Understanding the structures of proteins,  the components of the relevant proteins, and deciphering which part of the protein (primary, secondary, tertiary, or quaternary) is compromised when a disease exists would allow for the development of a cure by ameliorating the dysfunctional structure of the protein.  Ciliac disease, Tay Sachs disease and cancers caused by dimerization of proteins could be treated once the protein folding process has been clearly defined.