Estimation of Distribution Algorithm for Protein Structure Prediction

Proteins are essential for maintaining life. For example, knowing the structure of a protein, cell regulatory mechanisms of organisms can be modeled, supporting the development of disease treatments or the understanding of relationships between protein structures and food attributes. However, discovering the structure of a protein can be a difficult and expensive task, since it is hard to explore the large search to predict even a small protein. Template-based methods (coarse-grained, homology, threading etc) depend on Prior Knowledge (PK) of proteins determined using other methods as X-Ray Crystallography or Nuclear Magnetic Resonance. On the other hand, template-free methods (full-atom and ab initio) rely on atoms physical-chemical properties to predict protein structures. In comparison with other approaches, the Estimation of Distribution Algorithms (EDAs) can require significant less PK, suggesting that it could be adequate for proteins of low-level of PK. Finding an EDA able to handle both prediction quality and computational time is a difficult task, since they are strong inversely correlated. We developed an EDA specific for the ab initio Protein Structure Prediction (PSP) problem using full-atom representation. We developed one univariate and two bivariate probabilistic models in order to design a proper EDA for PSP. The bivariate models make relationships between dihedral angles $ϕ$ and $ψ$ within an amino acid. Furthermore, we compared the proposed EDA with other approaches from the literature. We noticed that even a relatively simple algorithm such as Random Walk can find the correct solution, but it would require a large amount of prior knowledge (biased prediction). On the other hand, our EDA was able to correctly predict with no prior knowledge at all, characterizing such a prediction as pure ab initio.