跳轉到

10.1 分子指紋與高維漢明距離#

10.1.1 規模問題：百萬分子如何兩兩比較？#

藥物公司化學庫動輒 \(10^6\) – \(10^9\) 個分子。要找「與已知活性分子 最相似的候選」，需要兩兩比較結構。第八章的精確工具在此失效：

  • 圖同構判定昂貴（雖然實務可行，但「相似度」不是同構）；
  • 譜描述子（08.2）有同譜非同構陷阱且計算 \(O(n^3)\) ；
  • 單一拓撲指數（08.3）嚴重退化（不同分子同指數）。

1990 年代，Daylight Chemical Information Systems 的 James Wein 等人給出工程化的答案：分子指紋（molecular fingerprint）—— 把分子編碼成固定長度的位元向量（如 1024 或 2048 bits），用 漢明距離比較。數學上粗暴，效率上無敵，且意外地有深刻的 機率論後果。

10.1.2 Morgan 演算法：指紋的引擎#

Morgan 演算法（1965） 為每個原子計算不變量標籤的迭代 精煉過程：

  1. 初始標籤 = 原子種類（C、N、O…）等不變量；
  2. 每輪：新標籤 = (舊標籤, 鄰居標籤多重集) 的雜湊；
  3. 重複 \(t\) 輪後，每個原子標籤編碼了半徑 \(t\) 內的全部鄰域。

定理 10.1（ equivalence with WL test） Morgan 演算法與 Weisfeiler–Lehman 圖同構測試（1968）等價；兩圖 WL 標籤多重集 不同 \(\Rightarrow\) 兩圖必不同構。更驚人的是：

定理 10.2（Xu et al. 2019, GIN 論文） 圖神經網路（GNN） 的訊息傳遞機制至多與 WL 測試一樣強。亦即 1965 年的 Morgan 演算法是所有訊息傳遞型 GNN 的表達力上界——五十年前的化學資訊學 演算法成為現代深度學習的理論基準。

10.1.3 Daylight / ECFP 指紋的定義#

定義 10.1（展開式指紋，Extended-Connectivity Fingerprint, ECFP）

  1. 對每個原子跑 Morgan 演算法，得到半徑 \(0, 1, \dots, R\) 的 子結構標籤（每個標籤對應一個「以該原子為中心的局部環境」）；
  2. 每個標籤經雜湊函數 \(h\) 映到 \(\{0, 1, \dots, b-1\}\) ；
  3. 指紋為位元向量 \(f \in \{0,1\}^{b}\) ， \(f_{h(\text{label})} = 1\) （存在碰撞可能）。

常見設定： \(b = 1024\) 或 2048， \(R = 2\) （ECFP4）或 3（ECFP6）。 注意：這是位元集而非計數向量，丟失了「出現幾次」的資訊； 某些變體（FCFP、藥效指紋）把原子型別抽象為藥效特徵（氫鍵給體、 受體、芳香環等）。

10.1.4 漢明距離與 Tanimoto 係數#

定義 10.2（漢明距離） 對位元向量 \(f, g \in \{0,1\}^{b}\) ，

\[ d_H(f, g) = \#\{k : f_k \ne g_k\} = |f \oplus g|, \]

其中 \(\oplus\) 為逐位元 XOR。漢明距離使 \(\{0,1\}^b\) 成為度量空間 （離散超立方體 \(\{0,1\}^b\) 的圖距）。

化學實務中更常用 Tanimoto（Jaccard）係數：

\[ T(f, g) = \frac{|f \cap g|}{|f \cup g|} = \frac{c}{a + b - c}, \]

其中 \(a = |f|\) 、 \(b = |g|\) 、 \(c = |f \cap g|\) 為共同為 1 的位元數。 \(T \in [0, 1]\) ，1 表相同。兩者的關係：當 \(|f| = |g| = s\) 時，

\[ T = 1 - \frac{d_H}{2s - c}, \qquad \text{（同權重時）} \quad T \approx 1 - \frac{d_H}{a + b}. \]

為什麼捨漢明取 Tanimoto？ 化學分子的「1 位元」遠少於 「0 位元」（稀疏性：2048 bits 中通常只有 20–60 個 1）。若用 漢明距離，兩個全無共同子結構的分子距離只差幾個 bit；Tanimoto 只計交集與聯集，對稀疏集合理論上更公平。這是度量選擇必須匹配 資料分佈的教科書案例。

10.1.5 機率後果：生日悖論與碰撞率#

指紋雜湊會碰撞（兩個不同子結構映射到同一位元）。設分子有 \(k\) 個子結構、指紋長 \(b\) ，至少一次碰撞的機率近似為

\[ P(\text{碰撞}) \approx 1 - \exp\!\left(-\frac{k(k-1)}{2b}\right). \]

以 \(k = 50\) 、 \(b = 2048\) 代入： \(P \approx 1 - e^{-0.60} \approx 45\%\) ！ 近半數分子有碰撞。為何 ECFP 仍然成功？因為碰撞對所有分子 近似均勻發生，故 Tanimoto 相似度的排序幾乎不受影響——機器 學習只需要排序，不需要絕對值。這種「有偏但保序」的雜湊哲學， 與 Bloom filter、count-min sketch 一脈相承。

import math
import hashlib

def morgan_labels(n_atoms, bonds, atom_types, rounds=2):
    """Morgan/WL 標籤精煉"""
    adj = [[] for _ in range(n_atoms)]
    for i, j in bonds:
        adj[i].append(j); adj[j].append(i)
    labels = list(atom_types)
    for _ in range(rounds):
        new = []
        for i in range(n_atoms):
            nb = sorted(labels[j] for j in adj[i])
            key = f"{labels[i]}|{nb}"
            new.append(hashlib.md5(key.encode()).hexdigest()[:8])
        labels = new
    return labels

def ecfp_fingerprint(n_atoms, bonds, atom_types, bits=2048, radius=2):
    labels = morgan_labels(n_atoms, bonds, atom_types, rounds=radius)
    fp = [0] * bits
    for lab in labels:
        idx = int(hashlib.md5(lab.encode()).hexdigest(), 16) % bits
        fp[idx] = 1
    return fp

def tanimoto(f, g):
    a, b, c = sum(f), sum(g), sum(x and y for x, y in zip(f, g))
    return c / (a + b - c)

# 乙醇 vs 二甲醚（氫壓縮：C-C-O vs C-O-C）
f_eth = ecfp_fingerprint(3, [(0,1),(1,2)], ["C","C","O"])
f_dme = ecfp_fingerprint(3, [(0,1),(1,2)], ["C","O","C"])
print(f"Tanimoto(乙醇, 二甲醚) = {tanimoto(f_eth, f_dme):.3f}")

# 碰撞機率曲線
for k in [20, 50, 100]:
    p = 1 - math.exp(-k * (k - 1) / (2 * 2048))
    print(f"k={k} 子結構, b=2048: P(碰撞) ≈ {p:.1%}")

10.1.6 高維幾何的意外性質：集中不等式#

漢明空間 \(\{0,1\}^b\) 上的隨機向量有一個反直覺的性質。設 \(f, g\) 為獨立、各位元以機率 \(p\) 為 1 的隨機指紋，則

\[ \mathbb{E}[d_H(f,g)] = 2p(1-p)\,b, \qquad \mathrm{Var}[d_H] = 2p(1-p)\big(1 - 2p(1-p)\big)\, b, \]

故相對變異 \(\frac{\sigma}{\mu} \sim \frac{1}{\sqrt{b}}\) —— 維度越高，隨機分子對的距離越集中在期望值附近（高維集中 現象，concentration of measure）。實務後果：在 \(b = 2048\) 的 空間中，「隨機相似」幾乎沒有變化，因此任何偏離隨機基線的 相似度都是強訊號。這正是虛擬篩選（virtual screening）的統計 基礎：在十億分子中，Tanimoto > 0.7 的相似度意味著 \(10^{-30}\) 量級的隨機機率。

應用層級（相似的經驗法則）：

Tanimoto 化學詮釋
\(> 0.85\) 同系物，活性常可轉移（相似性原理）
\(0.5\) – \(0.85\) 「鄰居區」，需實驗確認
\(< 0.3\) 基本上是隨機對

10.1.7 章末小結#

  1. Morgan 演算法（1965）= WL 測試，是所有訊息傳遞 GNN 的表達力 上界（Xu et al. 2019）——化學資訊學先於深度學習五十年。
  2. ECFP 指紋 = Morgan 標籤經雜湊壓入位元向量；碰撞率可達 40% 以上，但因均勻發生而「保序」，排序型應用不受影響。
  3. 漢明距離定義了離散超立方體上的度量；化學實務偏好 Tanimoto， 因為指紋極稀疏、度量須匹配分佈。
  4. 高維集中現象使隨機相似度近乎常數，令偏離基線的相似度成為 統計上極顯著的訊號——虛擬篩選的概率論基礎。

下一步：指紋把分子變成了 \(\{0,1\}^{2048}\) 中的點。10.2 將 把整個化學空間變成 \(\mathbb{R}^d\) 中的幾何：主成分、嵌入、以及 性質預測回歸模型——「化學空間」從比喻變成可導航的地圖。