タンパク質設計
ILPソルバーは、シンプレックス法やバリアベース法などの線形計画法(LP)アルゴリズムに依存して、各分岐でLP緩和を実行する。これらのLPアルゴリズムは、汎用の最適化手法として開発されたものであり、タンパク質設計問題(式(1))に最適化されたものではない。そのため、問題のサイズが大きくなると、LP緩和がILPソルバーのボトルネックになる。最近では、タンパク質設計問題のLP緩和の最適化のために、メッセージ伝搬アルゴリズム(message-passing)に基づくいくつかの代替案が設計された。これらのアルゴリズムは、整数計画の双対問題または主問題の両方を近似することができるが、最適性の保証を維持するためには、タンパク質設計問題の双対を近似するために使用するのが最も有効である。なぜなら、双対を近似することで、解を見逃さないことを保証するからである。メッセージ伝搬法に基づく近似法には、ツリー再重み付け最大積メッセージ伝搬アルゴリズム(tree reweighted max-product message passing)や、メッセージ伝搬線形計画アルゴリズム(message passing linear programming)などがある。
h は、まだ割り当てられていない回転異性体のエネルギーの下限値である。それぞれは、以下のように設計されている。ここで、d は部分立体配座の最後に割り当てられた残基のインデックスである。
g = ∑ i = 1 d ( E ( r i ) + ∑ j = i + 1 d E ( r i , r j ) ) {\displaystyle g=\sum _{i=1}^{d}(E(r_{i})+\sum _{j=i+1}^{d}E(r_{i},r_{j}))}
h = ∑ j = d + 1 n [ min r j ( E ( r j ) + ∑ i = 1 d E ( r i , r j ) + ∑ k = j + 1 n min r k E ( r j , r k ) ) ] {\displaystyle 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}))]}
Donald, Bruce R. (2011). Algorithms in Structural Molecular Biology. Cambridge, MA: MIT Press
Sander, Chris; Vriend, Gerrit; Bazan, Fernando; Horovitz, Amnon; Nakamura, Haruki; Ribas, Luis; Finkelstein, Alexei V.; Lockhart, Andrew et al. (1992). “Protein Design on computers. Five new proteins: Shpilka, Grendel, Fingerclasp, Leather and Aida”. Proteins: Structure, Function, and Bioinformatics 12 (2): 105–110. doi:10.1002/prot.340120203. PMID 1603799.
Jin, Wenzhen; Kambara, Ohki; Sasakawa, Hiroaki; Tamura, Atsuo & Takada, Shoji (2003).