ECFPとは何か

1 ECFPとは何か Hiroaki Gotoh

フィンガープリントの特徴と概要 2 • 分子のフィンガープリントの特徴は、あらかじめ定義されたパターンを使 用するのではなく、一連のルールを考慮してその場で生成 • フィンガープリントは構造キーとは対照的に、特定のビットの意味は事前 に定義されていない。 • 固定長に変更するために、異なる構造が同じビットになることもある。 トポロジカル 等価性 を考慮して フラグメント を作成 Morganアルゴリズム The Generation of a Unique Machine Description for Chemical Structures-A Technique Developed at Chemical Abstracts Service J. Chem. Doc. 1965, 5, 2, 107–113 https://doi.org /10.1021/c160017a018 ECFP Extended-Connectivity Fingerprints J. Chem. Inf. Model. 2010, 50, 5, 742–754 https://doi.org/10.1021/ci100050 t 2024年5月閲覧

• https://doi.org/10.1021/ci100050t
• https://doi.org/10.1021/c160017a018

Extended-Connectivity Fingerprints; ECFP 3 Morgan アルゴリズム等によってFingerprintを算出する方法は Morgan FingerprintsやCircular FingerprintsやExtended-Connectivity Fingerprints と呼ばれる。 ECFPアルゴリズムは、標準的なMorganアルゴリ 0100000010000 ズムにいくつかの変更を加えている 1100010000010 0000110000100 0001000001000 0100000100000 1. 初期原子識別子と各反復後のすべての識別子を リストにする。 2. ECFPアルゴリズムは、中間原子識別子を破棄 するのではなく、それらを保持。 部分構造 を捉える 1と0の ベクトル に変換 Extended-Connectivity Fingerprints J. Chem. Inf. Model. 2010, 50, 5, 742–754 https://doi.org/10.1021/ci100050 t 2024年5月閲覧 3. ECFPの生成は識別子の一意性が達成された後 ではなく、あらかじめ決められた数で終了。 4. ハッシュ化スキームで、分子間で比較可能な識 別子を生成。

• https://doi.org/10.1021/ci100050t

ECFPの概要 4 ①Radiusごとに構造や原子を認識 半径 Radius ②認識した構造パターンを数字で識別 Radius2 (Diameter 4) Radius0 7346039 1559650422 1559650422 -1100000244 1572579716 -10741416 Radius1 (Diameter 2) 直径 Diameter Radius0 (Diameter 0) どれが等価な 原子かを決める Identifiers (識別子) Radius1 Radius2 863188371 -1793471910 -1789102870 -1708545601 -932108170 2099970318 -87618679 1112638790 -627599602 ③識別した数字ごとに1と0のビットベクトルに変換 Identifier list representation: • 部分構造を固定長の ビットベクトルに変換 ハッシュ関数 (hash function) あるいは要約関数 • Bit collisions (重複)が 生じることもある 01000000100001100010000010000011000010000010000010000100000100 • 全て0のBitが生じる 7346039 1559650422 -1100000244 1572579716 -10741416 863188371 -1793471910 -1789102870 -1708545601 -932108170 2099970318 -87618679 1112638790 -627599602 Fixed-length binary representation 固定長のビットベクトル

ECFPで選べる特徴など 5 半径(radius) 0 1 Bit長 (Bits) 1 0 0 1024や2048 に設定 1 2 • このパラメータはECFPの支配的なパラメータで、考慮する原子 近傍の数と最大サイズを制御する。識別子リスト表現の長さと 固定長ビット列表現の "1 "ビット数を制御します。 • よく使用されるのは、半径2。RogersとHahnによると、類似性 検索やクラスタリングには半径4で十分である。より大きな制限 値を使用することで、より詳細な構造を利用できる。 • このパラメータは、ビット列表現の長さを指定する。 • よく使用される長さは1024や2048。長さが大きいとビットの衝突の 可能性が低くなるため、情報の損失が少なくなる。しかし、より大き な指紋を扱うには、より多くの計算時間とストレージスペースが必要 となる。

①Radiusごとに構造や原子を認識 6 [A]C(=[A])[A] -1100000244 Radius0 (Diameter 0) A: any atom 全ての 重原子で 計算 ECFP_0 半径0に含まれる 原子情報 0: 7346039 1: 1559650422 2: 1559650422 3: -1100000244 4: 1572579716 5: -10741416 標準的な「ECFP」フィンガープリントの初期原子識別子は、 原子情報を使用 初期原子情報は、分子内の原子の 6 つの特性。 ①「重い」（非水素）原子である近傍原子の数 ② 価数から水素の数を引いた値 ③ 原子番号 ④ 原子質量 ⑤ 原子電荷、および付着水素の数（暗黙的および明示的） ⑥ 原子が少なくとも1つの環に含まれているかどうか 1と2は、初期で同じ数字 になる。①から⑥が全て同じ これらをもとに配列を作成しハッシュ化されて1つの32 ビット整数になる。

②与えられた原子に対する結合情報を1回反復 Radius1 (Diameter 2) [A]CC(=O)N Radius0 (Diameter 0) Radius 1 ECFP_2 全ての 重原子で 計算 半径1に含まれる 原子と結合情報 計算した情報は保持 + 結合情報を加味して追加 0: 7346039 1: 1559650422 2: 1559650422 3: -1100000244 4: 1572579716 5: -10741416 0: 863188371 1: -1793471910 2: -1789102870 3: -1708545601 4: -932108170 5: 2099970318 結合の情報が反映されて、初期で同じ だった1と2が異なる数字になる。 7 -1708545601 1. 整数の配列が初期化され、反復番号(検討した半径)と原子 の識別子が格納される。 2. 結合順（単結合、二重結合、三重結合、芳香族）と各結合 原子の現在の識別子を用いて、結合原子を決定論的な順序に 並べ替える。芳香族性の計算には、標準的なHückel4n+2法 が使用されます。 3. 各アタッチメントについて、アタッチメント識別子と結合 順が配列に付加される。 4. その原子が立体原子である可能性があるが、まだ曖昧さが なく、すべての結合原子が異なる識別子を持つ場合、その原 子は曖昧さがないとマークされ、マークされた立体化学に応 じて、立体化学フラグが配列に付加される。(ステップ4は、 立体化学指紋が要求された場合のみ実行される)。 5. 配列はハッシュ化されて1つの32ビット整数になる。これ が原子の新しい識別子となる。

②拡張して計算 8 Radius2 (Diameter 4) [A]CCC(=O)N 1112638790 Radius0 (Diameter 0) Radius1 (Diameter 2) Radius2 (Diameter 4) Radius3 (Diameter 6) <ECFP_0> 7346039 1559650422 1559650422 -1100000244 1572579716 -10741416 <ECFP_2> 7346039 1559650422 1559650422 -1100000244 1572579716 -10741416 863188371 -1793471910 -1789102870 -1708545601 -932108170 2099970318 <ECFP_4> 7346039 1559650422 1559650422 -1100000244 1572579716 -10741416 863188371 -1793471910 -1789102870 -1708545601 -932108170 2099970318 -87618679 1112638790 -627599602 <ECFP_6> 7346039 1559650422 1559650422 -1100000244 1572579716 -10741416 863188371 -1793471910 -1789102870 -1708545601 -932108170 2099970318 -87618679 1112638790 -627599602 Radius1 (Diameter 2) Radius0 (Diameter 0) 全ての 重原子で 計算 ECFP_4 半径2に含まれる 原子と結合情報 は算出 されない で計算 済み • より大きい半径は小さい半径のフィンガープリントのビッ トをすべて含み、場合によって新しい識別子を付加 • ECFP_4 と ECFP_6 が同じリストを含んでいる。(最終的 な反復で新しい識別子が発見されなかったため)。

③識別子の解釈と数字として要約 9 識別子の解釈 • フィンガープリント計算時に、各識別子が 表す部分構造に関する情報が利用可能 • この例では、左側に示すブチルアミドを使 用しています。ECFP_6フィンガープリント のビットは1列目に示されています。 • 2番目の列には、対応するECFP_6ビットで 表された原子の集合が含まれています。(最 後の列は、抽出された部分構造のSMARTS 表現で、結合の接合は "A "原子で示される。 数字として要約 (イメージ図) Identifier list representation 7346039 1559650422 -1100000244 1572579716 -10741416 863188371 -1793471910 -1789102870 -1708545601 -932108170 2099970318 -87618679 1112638790 -627599602 ハッシュ関数 (hash function) あるいは要約関数 0100000001011001001000000101000010000110010000000000000100 10, 12, 13, 16, 19, Fixed-length binary representation 固定長のビットベクトル この例だと2, 26, 28, 33, 38, 39, 42, 61が１で (この場合 64) 他は0になる。 • 部分構造を固定長の ビットベクトルに変換 • Bit collisions (重複)が 生じることもある • 全て0のBitが生じる

実際に得られる結果とまとめ 10 2048にビットを固定しRadiusだけを0から3に変更した結果 3種類追加 同一 6種類追加 Radius 3 Radius 0 Radius 1 Radius 2 5種類 この分子の場合、原子数6 だが、5種類 C1 C2 O4 C3 C0 Radius 0 では等価 C5 14種類 11種類 Radius1で追加された6種類 C5 C0 C1 C2 C3 それぞれの原子から半径1 直径2のフラグメント Radius2で追加された3種類 O4 C1 C2 C3 それぞれの原子から半径2 直径4のフラグメント 14種類 Radius3で追加 されるものはない。 Diameter6よりも 分子が小さい この結果は、80, 140, 294, 545, 650, 794, 807, 962, 1057, 1171, 1357, 1564, 1898, 1917が1。他は0。

ビットの衝突の具体例について Radius 2で64 Bits Radius 2で2048 Bits １４種類 衝突がない 14 が 1 2034が 0 ようにに要約 11 80 ((1, 0), (2, 0)) 140 ((5, 1),) 294 ((0, 1),) 545 ((3, 2),) 650 ((4, 0),) 794 ((1, 1),) 807 ((3, 0),) 962 ((2, 2),) 1057 ((0, 0),) 1171 ((5, 0),) 1357 ((1, 2),) 1564 ((2, 1),) 1898 ((3, 1),) 1917 ((4, 1),) 64 だと 衝突 する １3種類 13 が 1 51 が 0 ビット数が多すぎると意味のない0が増える それぞれ、中心原子と半径を表示 コンパクト に要約 ビット数が少なすぎる と衝突が増える 2 ((2, 2),) 10 ((4, 0),) 12 ((5, 1),) 13 ((1, 2),) 16 ((1, 0), (2, 0)) 19 ((5, 0),) 26 ((1, 1),) 28 ((2, 1),) 33 ((0, 0), (3, 2)) 38 ((0, 1),) 39 ((3, 0),) 42 ((3, 1),) 61 ((4, 1),)

他の分子との比較 12 Radius 2で2048 Bits Radius 2で2048 Bits 80 １４種類 ((1, 0), (2, 0)) 140 ((5, 1),) 294 ((0, 1),) 545 ((3, 2),) 650 ((4, 0),) 794 ((1, 1),) 807 ((3, 0),) 962 ((2, 2),) 1057 ((0, 0),) 1171 ((5, 0),) 1357 ((1, 2),) 1564 ((2, 1),) 1898 ((3, 1),) 1917 ((4, 1),) 同じビット 数ならば 比較可能 同じ部分構造 は同一の数字 9種類 は共通 それぞれ、 中心原子と 半径を表示 １6種類 41 ((3, 1),) 80 ((1, 0), (2, 0)) 294 ((0, 1),) 345 ((5, 1),) 584 ((3, 2),) 650 ((4, 0),) 794 ((1, 1),) 807 ((3, 0),) 899 ((2, 2),) 1057 ((0, 0), (6, 0)) 1152 ((5, 0),) 1357 ((1, 2),) 1430 ((6, 1),) 1564 ((2, 1),) 1917 ((4, 1),) 2013 ((5, 2),)

ビットベクトルのまとめ 13 Structure keys Fingerprints 特徴 予め部分構造の辞書を作成しておき、 それに該当する構造があれば1を、な ければ0のビットを立てる手法 ある大きさまでのサイズの原子やフラグメン トを全て列挙して、それらをハッシュ(要約) 関数を用いて0 or 1のビットに変換する手法 欠点 予め定義していない部分構造は捉える ことはできない ハッシュ化する際に、異なる構造同士が同じ ビットに割り当てられる「衝突」が起こって 情報が欠落することがある 代表例 MACCS keys ECFP 代表例 の特徴 166ビットは無料。960ビットは有料。 半径とBit長を設定可能でユーザーが設定可 能 (1024や2048が多い) 決められた ものだけ 数える 1 0 1 1 0 決められた数のビット 0 全て列挙 決められた 数に変換 0と１次元の記述子