Emergent protein folding modeled with evolved neural cellular automata using the 3D HP model

Computational Modeling of Proteins based on Cellular Automata: A Method of HP Folding Approximation

The design of a protein folding approximation algorithm is not straightforward even when a simplified model is used. The folding problem is a combinatorial problem, where approximation and heuristic algorithms are usually used to find near optimal folds of proteins primary structures. Approximation algorithms provide guarantees on the distance to the optimal solution. The folding approximation approach proposed here depends on two-dimensional cellular automata to fold proteins presented in a well-studied simplified model called the hydrophobic-hydrophilic model. Cellular automata are discrete computational models that rely on local rules to produce some overall global behavior. One-third and one-fourth approximation algorithms choose a subset of the hydrophobic amino acids to form H-H contacts. Those algorithms start with finding a point to fold the protein sequence into two sides where one side ignores H's at even positions and the other side ignores H's at odd positions. In addition, blocks or groups of amino acids fold the same way according to a predefined normal form. We intend to improve approximation algorithms by considering all hydrophobic amino acids and folding based on the local neighborhood instead of using normal forms. The CA does not assume a fixed folding point. The proposed approach guarantees one half approximation minus the H-H endpoints. This lower bound guaranteed applies to short sequences only. This is proved as the core and the folds of the protein will have two identical sides for all short sequences.

On Stable States in a Topologically Driven Protein Folding Model

Theoretical models of protein folding often make simplifying assumptions that allow analysis, yielding interesting theoretical results. In this article, we study models where folding dynamics is primarily driven by local topological features in an iterative manner. We illustrate the merit of the proposed approach through its ability to simulate realistic protein folding processes even when the sequence content information is reduced to just hydrophobic and polar. We then analyze our models and show that under our simple assumptions, certain structures are inherently unstable, and that determining whether structures can be stable is an [Formula: see text]-hard problem. Interestingly, we find that when our model has only two amino acids, the problem becomes solvable in polynomial time.