Protein Folding: Computational Challenges

We review several results related to the protein folding problem. We start by analyzing the nature of the interactions among protein atoms and their influence on folding. We then examine several approaches to solve the folding problem, or restricted versions thereof. We conclude with a survey of results related to the computational complexity of the protein folding problem and analyze their implications on finding efficient solutions to the problem. 1 Introduction Proteins represent an important component of living organisms. They act as enzymes for different chemical reactions within our bodies, DNA being unable to function in their absence. They are also important parts of the immune system and are often the key element in many diseases. Therefore their study has a huge importance in understanding the functionality of the human body and in combating many deadly diseases. Due to the large complexity of proteins (an average protein has several thousands of atoms), computers are needed..