epLSAP-Align：熵正則化 partial LSAP 的非順序結構比對

30 秒理解

把非順序 residue matching 寫成 entropy-regularized partial linear sum assignment，再以 Sinkhorn 類迭代求近似軟配對。

核心問題

非順序 residue matching 能否寫成顯式含 gap 的最佳化問題，並用可調參數控制 coverage 與幾何 fidelity？

直覺

epLSAP-Align 把每個殘基配給另一殘基或 gap，將離散 partial assignment 放寬成軟機率矩陣，再用 Sinkhorn 反覆正規化求解；entropy 權重控制配對分散程度，因而調整對齊多寡。

為什麼重要

它對 non-sequential alignment 的 coverage–fidelity 交換給出清楚數學旋鈕，並在七資料集多數取得最佳 structure overlap；但原文沒有 FAST，且『最佳 SO』不等同同時最小 RMSD與最大 Nali。

閱讀前置

• 理解 permutation/assignment matrix 與 gap 在 alignment 的意義。
• 知道 entropy regularization 與 Sinkhorn scaling 的直覺。
• 能同時解讀 Nali、RMSD、SO 與 reference agreement。

paper-specific guide · plain → technical → input → output → source

逐步方法導讀

1. 01 · 用 gap-bi-permutation 表示部分配對

   在兩條殘基列表各加一個 gap 節點；每個真實殘基只能配一個殘基或 gap，而多個未對齊殘基可以流向 gap。

   論文語言: 以 (m+1)×(n+1) binary gap-bi-permutation X 表示 correspondence，row/column constraints 保證一對一或 gap matching；similarity S 加入 residue scores 與 gap penalties，轉成非負 cost C 的 partial LSAP。

   輸入: 已疊合結構的 residue similarity matrix 與 gap penalty。

   輸出: 帶 gap 的離散 partial assignment 問題。

   邊界: 它解的是給定 superposition 下的 correspondence；初始疊合仍由 TM-align 或 MICAN 提供。

   PDF pp. 2–3, §2.1.1 and Equations 1–4

2. 02 · 以 entropy-regularized pOT 求軟解

   先容許每格是 0 到 1 的配對質量，不急著做硬選擇；Sinkhorn 將 row/column 質量反覆校正到合法，最後再取每列或每欄最大值。

   論文語言: binary X 放寬為 gap-bi-stochastic P，目標為 Σ(CijPij + λ^-1 Pij log Pij)。Sinkhorn 在 O(n²) 近似 entropy-regularized partial optimal transport；row/column inference 各產生 alignment，預設選 TM-score 較高者。

   輸入: cost matrix C、λ、收斂閾值與最大迭代數。

   輸出: 軟 assignment P 與去除重複後的 residue pairs。

   邊界: 保證的是 regularized relaxation 的收斂，不是原始離散 LSAP 的無條件精確全域解。

   PDF pp. 3–4, §2.1.2 and Equations 5–6

3. 03 · 接上 TM-align/MICAN 並調 coverage

   先用既有方法決定兩個蛋白怎麼疊，再用 epLSAP 重配殘基；改 λ 可以讓 alignment 偏向多配一些或只留更可信的 pairs。

   論文語言: epLSAP-TM 與 epLSAP-MICAN 使用兩種 superposition，SP-score 建 similarity matrix，預設 λ=100、ε=.5、Tmax=5000。Nali 表 coverage、RMSD 表 fidelity、SO 為 3.5 Å threshold 下的 overlap。

   輸入: TM-align 或 MICAN transform 與 SP-score matrix。

   輸出: non-sequential alignment 及 Nali/RMSD/SO。

   邊界: 原文內部對 λ 方向的描述不一致：公式與 §2.1.3 說較小 λ 偏 coverage、較大 λ 偏 fidelity；§3.5 卻說較大 λ 加重 entropy，並報 Nali、RMSD 都隨 λ 增加。三者不能全部照字面同時成立，應核對實作或勘誤，不能自行替作者消除矛盾。

   PDF p. 4, §2.1.3–2.3; PDF p. 6, §3.5

關鍵結果

在 HOMSTRAD、MALIDUP/MALISAM、RIPC 與 difficult cases 展示非順序匹配的準確—速度折衷。

逐節證據導讀

論文事實、本站判讀與教學模型分開標示。

paper-fact

Table 1 如何讀 coverage–fidelity

在 MALIDUP，epLSAP-TM 為 Nali 89／RMSD 2.42／SO 75.8%，USalign2(fNS) 為 93／2.75／74.5%；epLSAP 少對 4 residues，但 RMSD 與 SO 較佳。

在 RIPC，epLSAP-TM 是 157／2.58／65.5%，USalign2(fNS) 是 179／3.30／65.2%；SO 幾乎相同但操作點不同。這正說明『最佳 SO』不能被翻成『Nali 與 RMSD 各自皆最佳』。

原文定位: PDF pp. 5–6, Table 1 and §3.1

paper-fact

reference agreement 與速度說了什麼

MALIDUP-ns/MALISAM-ns 的 EQR agreement 中，epLSAP-MICAN 為 66.6%／38.0%，高於 MICAN 52.2%／34.1%；RIPC 則 USalign2(sNS) 81.2% 明顯最高，受一個 72-pair 大案例影響。

七資料集平均 CPU time：epLSAP-TM .313 秒、USalign2(sNS) .404、USalign2(fNS) .615。前一比較確為快 22.5%；但 Table 3 的 .313 對 .615 依算式是少 49.1%，原文正文卻寫 44.9%。這裡同時保留表格、算術與原文聲稱的差異；epLSAP-TM 仍遠慢於 sequential TM-align .074 與 SSM .008。

原文定位: PDF pp. 6–7, Tables 2–3 and §3.2–3.3

project-reading

為何這篇不能直接回答 FAST 勝負

比較器包含 USalign2、FTAlign、MICAN、SPalignNS、CLICK、TM-align、SSM，沒有 FAST。任務也特別允許 non-sequential correspondence，與 FAST 的 sequential/global 設計邊界不同。

它可以列為『值得重跑 FAST 的現代候選』，尤其因為顯式報 Nali 與 RMSD；但在完成同資料、同 superposition、同 coverage policy 的實驗前，只能標成 indirect-modern。

原文定位: PDF pp. 4–5, §2.4–2.5 and Table 1

研究設計與評估

資料與樣本

MALIDUP、MALISAM、人工 non-sequential 版 MALIDUP-ns/MALISAM-ns、RIPC、64-difficult-case、HOMSTRAD，共七資料集。

比較基準

• non-sequential：USalign2 fNS/sNS、FTAlign、MICAN、SPalignNS、CLICK。
• sequential/context：TM-align 與 SSM。

指標

Nali

對齊殘基數，代表 coverage。
邊界: 最大化 Nali 可能納入不可信 pairs。

RMSD

疊合後 aligned pairs 的幾何 fidelity。
邊界: 只挑最近 pairs 可讓 RMSD 很低但 coverage 很小。

SO / EQR

SO 統計 3.5 Å 內結構 overlap；EQR 統計與人工 reference 共用的 residue pairs。
邊界: SO 閾值與 reference annotation 都會改變排名。

論文報告的結果

epLSAP variants 在七資料集多數取得最佳或近最佳 SO，並比 USalign2 快；但各方法落在不同 Nali/RMSD 操作點，且 FAST 未參賽。

PDF pp. 5–7, Tables 1–3 and §3.1–3.5

teaching-model · not a reported experiment

教學例（不是論文實驗）

一個 gap 節點如何避免硬塞配對

序列 u 有 4 個 residues，v 有 3 個；其中 u4 在空間上與任何 v residue 都很遠。

1. 傳統完整 assignment 若沒有 gap，可能被迫把 u4 配到某個 v，污染 RMSD。
2. epLSAP 增加 gap row/column，容許 u4→gap，同時其他三對維持一對一。
3. 調整 entropy 權重會改變軟矩陣質量是否集中，因而改變最後保留的 pairs 數；需用 Nali、RMSD、SO 一起選操作點。

帶走什麼: 顯式 gap 讓『不對齊』成為模型內合法選項，而不是事後刪除的補丁。

indirect-modern

相對 FAST 的證據邊界

原文未納入 FAST；只能定位為現代 non-sequential 候選，不能宣稱同指標勝 FAST。

合法來源與取用

9 pages · SHA-256 21991a9734f7b476cf7fa6c44e4af1d5252bbdfd03bb259ae1753c90662cee4b

CC BY 4.0 正式開放全文。

Europe PMC open-access PDF

限制與防誤讀

• 熵正則化與部分指派超參數會改變稀疏度和匹配數。

證據定位清單

1. PDF pp. 2–4, §2.1 and Fig. 1
2. PDF pp. 4–5, §2.2–2.5
3. PDF pp. 5–6, Table 1 and §3.1
4. PDF pp. 6–7, Tables 2–3 and §3.2–3.6

理解檢查

1. epLSAP-TM 在 RIPC 的 Nali 157 少於 USalign2 的 179，還能說較好嗎？

   答案: 只能在指定複合指標下說；它 RMSD 2.58 較低、SO 65.5% 略高，但 coverage 較少。

   不同 operation points 不宜壓成無條件排名。

2. Sinkhorn 收斂是否等於原始離散問題全域精確解？

   答案: 不等於；它求 entropy-regularized continuous relaxation，再離散化。

   論文的『global optimality』需放在該 relaxed formulation 與 solver 語境理解。

3. 這篇已直接超越 FAST 嗎？

   答案: 沒有，FAST 未納入比較。

   可當重跑候選，但目前只是 indirect-modern evidence。

讀完標準: 從 Table 1 選兩個資料集，把 epLSAP-TM 與 USalign2(fNS) 畫成 (Nali, RMSD) 點，另以 SO 標色，說明哪個結論會隨效用函數改變。

本篇詞彙表

partial LSAP

容許部分元素配 gap 的線性總和指派問題。

Sinkhorn algorithm

反覆縮放 rows/columns，以有效求 entropy-regularized transport 的方法。

structure overlap

本篇為 aligned pairs 中距離≤3.5 Å 的百分比。

EQR

演算法與人工 reference alignment 共同包含的 residue pairs 數。