Editing Protein design (section)

====Branch and bound====
{{main|Branch and bound}}

The protein design conformational space can be represented as a [[Tree (data structure)|tree]], where the protein residues are ordered in an arbitrary way, and the tree branches at each of the rotamers in a residue. [[Branch and bound]] algorithms use this representation to efficiently explore the conformation tree: At each ''branching'', branch and bound algorithms ''bound'' the conformation space and explore only the promising branches.<ref name="donald10" /><ref name="gordon99">{{cite journal|last=Gordon|first=DB|author2=Mayo, SL |title=Branch-and-terminate: a combinatorial optimization algorithm for protein design.|journal=Structure|date=September 15, 1999|volume=7|issue=9|pages=1089–98|pmid=10508778|doi=10.1016/s0969-2126(99)80176-2|doi-access=free}}</ref><ref name="leach98" >{{cite journal|last=Leach|first=AR|author2=Lemon, AP |title=Exploring the conformational space of protein side chains using dead-end elimination and the A* algorithm.|journal=Proteins|date=November 1, 1998|volume=33|issue=2|pages=227–39|pmid=9779790|doi=10.1002/(sici)1097-0134(19981101)33:2<227::aid-prot7>3.0.co;2-f|citeseerx=10.1.1.133.7986|s2cid=12872539 }}</ref>

A popular search algorithm for protein design is the [[A* search algorithm]].<ref name="donald10" /><ref name="leach98" /> A* computes a lower-bound score on each partial tree path that lower bounds (with guarantees) the energy of each of the expanded rotamers. Each partial conformation is added to a priority queue and at each iteration the partial path with the lowest lower bound is popped from the queue and expanded. The algorithm stops once a full conformation has been enumerated and guarantees that the conformation is the optimal.

The A* score <var>f</var> in protein design consists of two parts, <var>f=g+h</var>. <var>g</var> is the exact energy of the rotamers that have already been assigned in the partial conformation. <var>h</var> is a lower bound on the energy of the rotamers that have not yet been assigned. Each is designed as follows, where <var>d</var> is the index of the last assigned residue in the partial conformation.

: <math>g=\sum_{i=1}^d (E(r_i ) + \sum_{j=i+1}^d E(r_i,r_j) )</math>

: <math>h = \sum_{j=d+1}^n [\min_{r_j}(E(r_j) + \sum_{i=1}^d E(r_i,r_j) + \sum_{k=j+1}^n \min_{r_k} E(r_j,r_k))]</math>