FPGA Computing in Modern Bioinformatics - Parallel Computing for Bioinformatics and Computational Biology - page 722

from scratch without a probable starting structure. Protein structure prediction that
does not use protein domains are called “ab initio” protein structure prediction.
Within the following sections a possible solution of an “ab initio” protein structure
prediction approachwill be described and discussed. Then the possibilities of a parallel
execution of the task is shown. Finally, the implementation aspects are discussed and
the layout of a parallel architecture is presented.

28.5.1 “Ab Initio” Protein Structure Prediction

In general “ab initio” protein structure prediction is a problem which is still unsolved
today [21] although interesting progress in this field has been reported [22-24]. The
“ab initio” structure prediction problemcan be formulated as an optimization problem,
because it leads to the task of finding the free enthalpyminimum in the conformational
space of the protein.
Thus protein structure prediction can be divided into two subproblems:

1. Search method / structure generator for different structures.
2. Evaluation of the protein structure energy.

The protein structures are generated in the first step by the structure generator
using different strategies. The first step models the protein and describes it as the
combination of the amino acid atoms. Each atom is defined by its three-dimensional
coordinates and an atom type number. This representation must be recomputed every
time a modification in the protein structure is performed.
Once a protein structure is generated or modified it must be evaluated within the
second step. Important for this evaluation of the protein is its free enthalpy. Because
the free enthalpy is related to the energy, this energy value is computed using the
atom type classifications and van der Waals radii as devised by Nussinov et al. [25].
The computed energy is returned back to the first step and compared to the already
evaluated protein structures.
This two-stepworkflow is computedwithin a loop to check all the generated protein
structures and to find the protein structure with the lowest energy. The number of
possible protein structure conformations is enormous and no efficient algorithm is
known which can guarantee to find the global optimum of this energy landscape. This
is the reasonwhy it is necessary to compute a vast number of protein structures in order
to find the global energy minimum of a protein. Hence, the faster the computation
of protein energies can be performed the bigger the size of proteins which can be
computed in a feasible time. This is especially the case for the energy calculation,
because this step requires more than 90% of the complete execution time.
The focus of the subsequent section is on the efficient and powerful implemen-
tation of this energy calculation as it is computed by a FPGA processor. First, the
requirements for the energy computation are presented and the used calculation mod-
els are discussed. Second, a possible execution architecture for this energy calculation
is shown and finally the parallel architecture will be described and outlined in detail
before the results of the implementation are presented.