A survey of recent work on evolutionary approaches to the protein folding problem

Abstract- A problem of immense importance in computational biology is the determination of the functional conformations of protein molecules. With the advent of faster computers, it is now possible to use rules to search conformation space for protein structures that have minimal free energy. This paper surveys work done in the last ve years using evolutionary search algorithms to nd low energy protein conformations. In particular, a detailed description is included of some work recently started at the National Cancer Institute, which uses evolution strategies. 1Introduction Biological organisms contain thousands of di erenttypes of proteins. Proteins are responsible for transporting small molecules (e.g., hemoglobin transports O2 in the bloodstream), catalyzing biological functions, providing structure to collagen and skin, regulating hormones, and many other functions. Each protein is a sequence of amino acids, bound into linear chains, that adopts a speci c folded three-dimensional shape. Each shape provides valuable clues to the protein's function. Indeed, this information is vital to the design of new drugs capable of combating disease. Regrettably, ascertaining the shape of a protein is a di cult, expensive task which explains why few proteins have been categorized in this regard. Virtual protein models, created on computers, may provide a cost effective solution to accurate prediction of protein shapes. Unfortunately, the protein folding problem|trying to predict the structure of a protein given only the protein's sequence of amino acids|is a combinatorial optimization problem, which so far has eluded solution because of the exponential number of potential solutions. The purpose of this paper is two-fold. Previous papers have surveyed the use of evolutionary algorithms (EAs) in protein folding problems, but they have been written primarily from the perspective of biophysicists