Zombie Compositions in Assembly Algebras and an Upper Bound on the Size of Chemical Space

技術要約：アセンブリ代数におけるゾンビ組成と化学空間のサイズに関する上限

問題提起
本論文は、構築の複雑さに伴って構築可能なオブジェクトの数がどのように増加するかという、分子化学、組合せデザイン、および回路複雑性の分野に関連する根本的な問いに取り組んでいる。具体的には、組み立て指数 $a$ を持つ分子の数 $N(a)$ に対して、二重指数関数的な上限を仮定した Morales Parra ら [7] の既存の枠組みを批判している。著者らは、以前の近似的な成長指数である約 0.73 という値は、組合せ論的に妥当な組成の大部分が、原子価（バレンス）および結合性（コネクティビティ）の制約により物理的に実現不可能であることを考慮していないため、化学空間のサイズを過大評価していると主張している。

手法
著者らは、オブジェクトの集合 $X$、ビルディングブロック $BB$、アセンブリ演算$\oplus$、および結合多重度$\nu$からなるタプル$(X, BB, \oplus, \nu)$ として定義される、**構成システム（construction systems）**と呼ばれる一般的な代数的枠組みを導入する。手法は、主に以下の3つの代数的および組合せ論的なステップで進行する：

1. トーリック幾何学とマトロイド： アセンブリ過程は、トーリックイデアル $I_A$ および トーリック多様体 $X_A$ へと写像される。特定のシステム（化学的、物理的、または論理的）の「規則」は、このイデアル内の二項関係として符号化される。著者らは、システムにトーリックマトロイド $M$ とブロックマトロイド $M^*$ を関連付けており、マトロイドのランクは、代数的に独立なビルディングブロックの座標数に対応する。ビルディングブロックに対する制約は、マトロイド操作（制限および削除）に対応することが示されている。
2. 解析的な境界： デザインシグネチャ $(m, \nu, n_0)$ とマトロイドランクを用いて、著者らは、列挙されたデータベースに依存することなく、$N(a)$ の解析的な境界を導出する。彼らは、成長指数 $\rho$ が $\log 2$ によって抑えられることを確立している。
3. 組成多面体とゾンビの除外： 型付きビルディングブロックと原子価の制約を持つシステムに対して、著者らは $\mathbb{R}^m$ 内の組成多面体 $P_{val}$ を定義する。この多面体は、次数要求と原子価制限を含む単一の線形不等式を通じて、実現可能性の制約を捉える。組成の範囲外にあるものは**「ゾンビ」**と呼ばれる。これらは、組合せ論的には妥当（stars-and-barsによるカウントを満たす）であるが、物理的には不可能である。著者らは、**エラート準多項式（Ehrhart quasi-polynomials）**を利用して、$P_{val}$ 内の整数点の数を数え上げ、実現可能な組成の正確な数を算出する。

主要な貢献

• 代数的枠組み： 本論文は、構成システムをトーリック幾何学における対象として定式化し、オブジェクトの存在を規定する「規則」が、外部の制約ではなく、トーリックイデアルに内在していることを示している。また、ビルディングブロックに対する制約が、ブロックマトロイド上のマトロイド操作に対応することを確立している。
• 正確な成長指数： 著者らは、頂点識別結合（$\nu(n_1, n_2) = n_1 n_2$）を持つシステムにおいて、正確な二重指数関数的成長指数が $\rho = \log 2 \approx 0.693$ であることを証明した。これは、バイナリアセンブリツリーからの上限と、Pólyaの木列挙法から得られる下限を一致させることで導出されており、以前のフィッティング値である 0.73 を置き換えるものである。
• ゾンビ分類とその健全性： 論文は「ゾンビ組成」の概念を導入し、その分類が健全（sound）（偽陽性ゼロ）であることを証明している。すなわち、ゾンビと宣言された組成は、物理的に実現不可能であることが保証される。この分類はまた、**保守的（conservative）**であり、真の実現不可能性の割合は、多面体が予測する割合と同等以上に高い。
• 洗練された上限： 素朴な stars-and-bars カウントを組成多面体のエラートカウントに置き換えることで、著者らは $N(a)$ に対する厳密にタイトな上限を導出している。

結果

• 分子グラフシステム ($m=19$)： 分子グラフのアセンブリシステム（19種類の結合タイプ、5種類の原子タイプ、原子価 1–4）にこの枠組みを適用すると、19種類のうち9種類の結合タイプが「ゾンビ生成子」（結合性の境界を超える原子価容量を消費するもの）であることが特定された。
• ゾンビの割合： 漸近的なゾンビ組成の割合は 94.1% ($z_\infty \approx 0.941$) と計算された。これは、組成空間の約6%のみが化学的に実現可能であることを意味する。
• 数値的影響： フィットされた指数（0.73）と正確な指数（$\log 2 \approx 0.693$）の差は、二重指数関数的領域において膨大な過大計上をもたらす。アセンブリ指数 $a=10$ において、以前の境界は洗練された境界を $10^{198}$ 倍上回る。$a=30$ では、その過大計上は9億4200万桁に達する。
• 計算による検証： 著者らは、エラート準多項式（周期12、次数18）の天井残留値を用いた動的計画法を用いて、サイズ $S=1$ から $48$までの実現可能な組成の正確な数 ($EP(S)$) を算出した。これらの結果は、ゾンビの割合が急速に収束することを裏付けている。

意義
本論文は、組成多面体が、従来のメソッドよりも化学空間のサイズに対して実質的にタイトで正確な上限を提供することを主張している。組成空間の94%が「ゾンビ」であることを特定することで、本フレームワークは、すべての組合せ的組成を数え上げることに起因する過大評価を修正している。成長指数が正確に $\log 2$ であるという結果は、下限と上限の間のギャップを解消し、指数がバイナリアセンブリモデルに固有であり、フィッティングされたパラメータに依存しないことを示している。著者らは、本フレームワークが一般的であり、有限のビルディングブロックとバイナリアセンブリを持つあらゆる構成システム（生体直交クリックケミストリーシステムや組合せ回路設計を含む）に適用可能であることを強調している。結論として、この「ゾンビ現象」は、計算上のアーティファクトではなく、初等的な原子価算術の結果であるとしている。