2006年06月12日

Pythonでケムインフォ:Fingerprint

Fingerprintについてメモしたいと思います。化学構造のFingerprintでは、ビット列中の各ビットに部分構造(フラグメント)があてはめられています。例えば、1ビット目にあてはめられた部分構造が、化合物中に存在すれば"1"、存在しなければ"0"とセットします。Fingerprintの長さは、通常、数百〜数千ビット程度ではないでしょうか。

代表的なFingerprintの使い方は、類似性検索だと思います。分子Aと分子Bの類似性を評価する場合、Fingerprint A(分子Aより生成)とFingerprint B(分子Bより生成)間の距離を"類似性"の尺度とし評価します。この距離の計算には、Tanimoto係数、コサイン係数など多くの手法が提案されています。

もう1つのFingerprintの作り方として、ハッシングを用いる方法があります。上記方法では、ユーザが各ビットに特定の部分構造を設定しますが、ハッシングでは、与えられた部分構造からハッシュ値を計算し、その値で、何ビット目に1を立てるか決定します。利点としては、はじめに各ビットの部分構造を決定する必要がないこと。また、ハッシュ関数でハッシュ値の上限が設定できるため、ビット列長を自由に設定できることなどが挙げられます。逆に、欠点としては、ハッシュ値の衝突により、特定のビットに2つ以上の部分構造があてはめられることが挙げられます。したがって、類似性評価を行う場合、Fingerprint生成アルゴリズムはチェックすべき項目だと思います。

さて、部分構造検索は、グラフ理論でいうグラフの同形判定であり、この同形を判定する作業は、NP完全問題です。したがって、この部分における高速化は、かなりしんどいタスクとなります。そこで、同形判定をする前に、明らかに部分構造ではない化合物を取り除く工程でFingerprintが利用されています。ここでは、ハッシングによるFingerprintが活躍しています。

例えば、Fingerprint Aをクエリーとして、Fingerprint Bを標的とする場合、Fingerprint AがFingerprint Bの部分構造であるためには、Fingerprint Aの全ての1の立っているビットがBにおいても1である必要があります。この計算はビット演算子を用いて評価できますので、非常に高速に計算できます。そうは言っても、ハッシングによるFingerprintでは衝突が発生しますが、その後に同形判定は必ず行われますので、最終結果には影響を及ぼさないことになります。

次回、Frownsを使って、Fingerprint + SMARTSによる部分構造検索プログラムを作成したいと思います。


banner_02.gif
人気ブログランキング(クリックして応援してね)







posted by わばのり at 07:11| Comment(0) | TrackBack(0) | Frowns | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。