Editing Protein design (section)

===Optimization algorithms without guarantees===

====Monte Carlo and simulated annealing====

Monte Carlo is one of the most widely used algorithms for protein design. In its simplest form, a Monte Carlo algorithm selects a residue at random, and in that residue a randomly chosen rotamer (of any amino acid) is evaluated.<ref name="voigt00" /> The new energy of the protein, <var>E</var><sub>new</sub> is compared against the old energy <var>E</var><sub>old</sub> and the new rotamer is ''accepted'' with a probability of:

: <math> p=e^{-\beta(E_{\text{new}}-E_{\text{old}}))},</math>

where <var>&beta;</var> is the [[Boltzmann constant]] and the temperature <var>T</var> can be chosen such that in the initial rounds it is high and it is slowly [[simulated annealing|annealed]] to overcome local minima.<ref name="samish11">{{cite journal|last=Samish|first=I|author2=MacDermaid, CM |author3=Perez-Aguilar, JM |author4= Saven, JG |title=Theoretical and computational protein design.|journal=Annual Review of Physical Chemistry|year=2011|volume=62|pages=129–49|pmid=21128762|bibcode= 2011ARPC...62..129S |doi= 10.1146/annurev-physchem-032210-103509}}</ref>

====FASTER====

The FASTER algorithm uses a combination of deterministic and stochastic criteria to optimize amino acid sequences. FASTER first uses DEE to eliminate rotamers that are not part of the optimal solution. Then, a series of iterative steps optimize the rotamer assignment.<ref>{{cite journal|last=Allen|first=BD|author2=Mayo, SL |title=Dramatic performance enhancements for the FASTER optimization algorithm.|journal=Journal of Computational Chemistry|date=July 30, 2006|volume=27|issue=10|pages=1071–5|pmid=16685715|doi=10.1002/jcc.20420|citeseerx=10.1.1.425.5418|s2cid=769053}}</ref><ref>{{cite journal|last=Desmet|first=J|author2=Spriet, J |author3=Lasters, I |title=Fast and accurate side-chain topology and energy refinement (FASTER) as a new method for protein structure optimization.|journal=Proteins|date=July 1, 2002|volume=48|issue=1|pages=31–43|pmid=12012335|doi=10.1002/prot.10131|s2cid=21524437}}</ref>

====Belief propagation====

In [[belief propagation]] for protein design, the algorithm exchanges messages that describe the ''belief'' that each residue has about the probability of each rotamer in neighboring residues. The algorithm updates messages on every iteration and iterates until convergence or until a fixed number of iterations. Convergence is not guaranteed in protein design. The message <var>m</var><sub><var>i&rarr; j</var></sub><var>(r<sub>j</sub></var> that a residue <var>i</var> sends to every rotamer <var>(r<sub>j</sub></var> at neighboring residue <var>j</var> is defined as:

: <math>m_{i\to j}(r_j) = \max_{r_i} \Big(e^{\frac{-E_i(r_i)-E_{ij}(r_i,r_j)}{T}}\Big) \prod_{k \in N(i)\backslash j} m_{k\to i (r_i)}</math>

Both max-product and sum-product belief propagation have been used to optimize protein design.