6

問題:球のリストが与えられたとき、球で完全に囲まれているすべての空きスペースを見つけます。

詳細:これは私が取り組んでいる問題で、タンパク質にある空洞を特定しようとしています。タンパク質を構成する原子のリスト ((x,y,z) 座標と半径) が与えられます。次に、アルゴリズムを実行して、他の球体と衝突することなく (指定された半径の) プローブを配置できるかどうかを確認することで、タンパク質の境界内にあるすべての空のスペースを見つけます。空きスペースには、ボイド スペースとキャビティの 2 種類があります。空隙は、タンパク質につながるか、またはタンパク質の外側にある空間です。空洞は、タンパク質原子によって完全に囲まれた空の空間です。これは、私たちが扱っているサンプル「タンパク質」の画像です。

タンパク質

こちらで立体的に見ることができます。

タンパク質の中心近くに空洞があります。タンパク質を通過するトンネルは、原子によって完全に囲まれていないため、ボイド スペースと見なされます。

例: 26 個のアトムのリストが与えられた場合、これらのアトムは 3 次元グリッドで (0,0,0) から (1,1,1) まで等間隔に配置されます。各原子の半径は 0.25 で、任意の軸の 0、0.5、または 1 に配置されます。ポイント (0.5, 0.5, 0.5) にはアトムはありません。これらの原子を 3D で描くと、中心が欠けた立方体のような形になります。キャビティは、半径 0.25 の (0.5,0.5,0.5) に指定されます。この空洞は四方をタンパク質に囲まれていると考えられます。

画像例:画像

上記は立方体とタンパク質の 2D 表現に過ぎないことに注意してください。それは実際には3Dです。

はるかに大きくて不規則な形状の原子グループの空隙と空洞をどのように決定するのでしょうか?

すべての方向をチェックしてグラフの最大境界と最小境界に到達できるかどうかを確認する再帰アルゴリズムを実装することを考えていましたが、これが正しい方法であるかどうかはわかりません。

おまけ：タンパク質の外側に到達するための非常に小さな「経路」があるため、例の空洞が実際には空隙であると言う別のアルゴリズムはありますか? 空洞が存在するには、原子によって完全に囲まれている必要があります。タンパク質の外側へのパス (任意の方向、必ずしも直線ではない) を持つ空隙は、空洞とは見なされません。

4

1 に答える 1

4

クールな質問。トリックを行うアルゴリズムは次のとおりです。

表記：

  • 可動球を としましょうS。
  • diam(X)球の直径を書くX
  • からまでdist(X,Y)の距離を書きます。これは、 の中心から の中心までの距離から半径の合計を引いたものと同じです。XYXY

アルゴリズム:

  1. 任意の 2 つの動かない球体Aおよびについて、 がとの中心間を直接通過できるBかどうか(すなわち、 は?) をチェックします。SABdiam(S) <= dist(A,B)
  2. もしそうなら、他の各球体について、他の球体が存在しない場合、3つの球体すべてに同時に触れることができるCかどうかを確認してください。3 つすべてに同時に触れることができる場合は、 、、およびの中心の間に三角形を描きます。 SABCSABC
    • これはいくつかの方法で確認できます。かなり簡単な方法の 1 つ: の中心の可能な位置を、S両方に触れて円Aを形成します。Bこの円上にdiam(S) + diam(C)の中心から離れた点があるかどうかを知りたいとしCます。これは簡単な幾何学です。
  3. 問題は次の質問に帰着します: 三角形は中心の初期位置をS無限大から分離しますか? 一度に 1 つの連結要素に答えることができます。実際、一度に 1 つの「エッジ接続」コンポーネントに回答することもできます。ここで、頂点を通過しないパスによって頂点以外の 2 つのポイントをリンクできる場合、コンポーネントはエッジ接続されます。これらのコンポーネントは、簡単なグラフ検索で計算できます。
  4. 特定のエッジ接続コンポーネントについて、コンポーネントが中心をS無限から分離するかどうかを決定する必要があります。これを行うにはいくつかの方法があります。
    • コンポーネントの 2-ホモロジーを計算し、有効な生成元を選択し、それぞれについて、点と無限大がサイクルの同じ側にあるかどうかを尋ねます。これは方向クラスを使用して確認できます。
    • または、コンポーネントのペイントを開始します。
      • から到達できる三角形から始めて、Sそこから到達できるすべての面をペイントします。これは少し微妙ですが、アルゴリズムは「どこからでも開始し、エッジをキューに入れ、各エッジを面上で交差させてそのエッジと最小の角度を形成し、エッジが残っていないときに停止する」だけです。同じ三角形の反対側が、最小の角度を形成する面である可能性があることに注意してください。
      • 無限から同じことをしてください。ペイントされた三角形を横切りましたか? はいの場合、あなたの球は逃げることができます。いいえ、できません。

機能する理由

ステップ 3 は真です。なぜなら、とCの間のエッジを「回転」しているときに球体に当たらなければ、そのエッジのどの側にも到達できるからです。別の言い方をすれば、無限に行くのを止める位置には、少なくとも 3 つの球に触れる必要があります。ABS

Sが一度に 4 つの球体に触れた場合など、「例外的な」状況から発生する微妙な点がいくつかあることに注意してください。手順 3 と 4 を実行する前に形状を再三角形化することで、これらの微妙な点を回避できます。

于 2012-05-01T03:55:50.503 に答える