ドッキングシミュレーション等で、二つの分子表面の相補性の良さを計算することがある。Katchalski-Katzir algorithm では、これを FFT を使って高速に行う。
三次元空間において、蛋白質Aの表面なら1,外部なら0という関数 を考える。同様に、蛋白質Bについて を考える。蛋白質Aを固定して蛋白質Bを 並行移動したときの相補性の良さを表すスコア S は、表面と表面が重なった時に得点すると考えると、 という演算で求められる。
これを全ての移動 について計算して最大化することでベストなドッキング位置を計算できるが、愚直に計算すると、空間を NxNxN 点のグリッドに離散化したとして、1つの積分に かかるので、全部で かかってしまう。
幸い、上記の積分は畳み込み積分である(よくある畳み込み積分は という形をしているが、 の正負の違いは関数 g の中に吸収できる)。したがって、畳み込み定理により、フーリエ変換後の逆空間における掛け算に変換可能であり、FFT を使うと で計算可能だ。
なお、回転については、回転角を適当に離散化して、1つ1つ計算するらしい。#これ、なんとかならないの?
なお実際には、蛋白質の食い込みを防ぐため、蛋白質Aの内部ではfを大きな負の値に、蛋白質Bの内部ではgを小さな正の値にしておく。すると、Aの内部がBの表面や内部に食い込んだときに巨大なペナルティを課すことができる。この場合、Bの内部がAの表面に軽く食い込んだ場合はペナルティが生じないが、結合時の induced fit があることを考えて正当化されるという。
参考文献: On proteins, grids, correlations, and docking C. R. Biologies 327 (2004) 409–420 by Eisenstein M, Katchalski-Katzir E.