タンパク質設計
最も一般的なエネルギー関数は、回転異性体とアミノ酸タイプの間のペアワイズ項に分解できるため、問題を組み合わせ問題として計算し、強力な最適化アルゴリズムを用いて解決することができる。このような場合、各配列に属する各立体配座の総エネルギーは、残基位置間の個別項とペアワイズ項の和として定式化できる。設計者が最良の配列のみに関心がある場合、タンパク質設計アルゴリズムは、最低エネルギー配列の最低エネルギー配座のみを必要とする。このような場合には、各回転異性体のアミノ酸の同一性を無視し、異なるアミノ酸に属するすべての回転異性体を同じように扱うことができる。タンパク質鎖の残基位置 i にある回転異性体を ri とし、回転異性体の内部原子間の位置エネルギーを E(ri) とする。E(ri, rj) を、残基位置 j における ri と回転異性体 rj の間の位置エネルギーとする。そして、最適化問題を最小エネルギー (ET) の立体配座を見つけることの1つと定義する。
ET を最小化する問題は、NP困難な問題である。問題のクラスがNP困難であるにもかかわらず、実際には、タンパク質設計の多くの事例は、ヒューリスティックな方法によって正確に解決したり、十分に最適化することができる。
∑ r j q i j ( r i , r j ) = q i ( r i ) , ∀ i , r i , j {\displaystyle \sum _{r_{j}}q_{ij}(r_{i},r_{j})=q_{i}(r_{i}),\forall i,r_{i},j}
q i , q i j ∈ { 0 , 1 } {\displaystyle q_{i},q_{ij}\in \{0,1\}}
CPLEX(英語版)に代表されるILPソルバーは、タンパク質設計問題の大規模な事例に対して、正確な最適解を計算することができる。これらのソルバーは、問題の線形計画緩和(英語版)(linear programming relaxation)を使用し、qi と qij が連続した値をとることができ、ブランチ・アンド・カット(英語版)アルゴリズム(branch and cut)を組み合わせて、最適な解を求めて立体配座空間のごく一部を探索するものである。ILPソルバーは、側鎖配置問題の多くの事例を解決することが示されている。