化学グラフジェネレータ

化学グラフ ジェネレーターは、特定の境界条件に準拠した化学構造のコンピューター表現を生成するソフトウェア パッケージです。このようなソフトウェア パッケージの開発は、ケミインフォマティクスの研究テーマです。化学グラフ ジェネレーターは、薬物設計における仮想ライブラリ生成、逆QSAR/QSPRと呼ばれる特定の特性を持つ分子設計、有機合成設計、逆合成、コンピューター支援構造解明(CASE)システムなどの分野で使用されています。CASE システムは、計算生物学の現在の分野である計算メタボロミクスにおける未知物質の構造解明で再び注目を集めています。

分子構造生成はグラフ生成問題の一分野である。 ^{[1]分子構造は、}原子価、結合多重度、フラグメント などの化学的制約を持つグラフである。これらのジェネレーターは、CASEシステムの中核である。ジェネレーターでは、分子式が基本的な入力である。実験データからフラグメントが得られた場合、それらも入力として使用して構造生成を加速することができる。最初の構造ジェネレーターは、化学的目的のために修正されたグラフジェネレーターのバージョンであった。最初の構造ジェネレーターの1つがCONGENであり、^{[2]もともとは}有機化学における最初の人工知能プロジェクトであるDENDRALプロジェクトのために開発された。^[3] DENDRALは、火星生命体を探すためにNASAが開始したマリナー計画の一環として開発されました。 ^{[4] [5] CONGENは、部分構造の重なりをうまく処理した。}原子ではなく部分構造間の重なりがビルディングブロックとして使用された。立体異性体の場合、重複検出のために対称群の計算が実行された。

DENDRALの後、分子構造の数学的合成と解析のためのツールである別の数学的手法MASS ^{[6]が報告されました。CONGENと同様に、MASSアルゴリズムは}隣接行列ジェネレーターとして機能しました。多くの数学的ジェネレーターは、Igor Faradjev ^[7]とRonald C. Readの順序的生成法^{[8]からの効率的な}分岐限定法の後継です。これらの報告は1970年代のものですが、これらの研究は今でも構造ジェネレーターの基本的な参考文献となっています。順序的生成法では、ベクトルなどのグラフ表現に対して特定の順序チェック関数が実行されます。たとえば、MOLGEN ^[9]は、隣接行列の行を埋めるときに降順チェックを実行します。この降順チェックは、入力の価数分布に基づいています。文献では、ジェネレーターを構造アセンブリと構造削減の2つの主要なタイプに分類しています。アルゴリズムの複雑さと実行時間が比較の基準となります。

生成プロセスは、分子式からの原子のセットから始まります。構造アセンブリでは、原子は組み合わせ的に接続され、すべての可能な拡張が検討されます。実験データからサブ構造が得られた場合は、これらのサブ構造から生成が開始されます。これらのサブ構造は、分子内の既知の結合を提供します。最も初期の試みの 1 つは、1975 年に Hidetsugu Abe によってパターン認識ベースの構造ジェネレータを使用して行われました。^{[10]このアルゴリズムには 2 つのステップがありました。1つ目は、低解像度の}スペクトルデータからサブ構造を予測すること、2 つ目は、一連の構築ルールに基づいてこれらのサブ構造をアセンブリすることです。Hidetsugu Abe と他の貢献者は、複数の構造生成方法を含むCASE ツールである CHEMICS [ 11] に関する最初の論文を発表しました。このプログラムは、定義済みの重複しないフラグメント ライブラリに依存しています。CHEMICS は、コンポーネントの複雑さに基づいて、プライマリからターラ二次コンポーネント セットと三次コンポーネント セットは、これらの一次コンポーネントから始めてレイヤーごとに構築されます。これらのコンポーネント セットはベクトルとして表され、プロセス内の構成要素として使用されます。

Craig Shelley と Morton Munk は、この分野で多数の CASE 論文を発表し、多大な貢献をしました。これらの論文の最初の論文では、構造ジェネレーター ASSEMBLE が報告されました。^[12]このアルゴリズムは、この分野における最も初期のアセンブリ方法の 1 つと考えられています。名前が示すように、このアルゴリズムは、重複する部分構造を組み立てて構造を構築します。ASSEMBLE は、「隣接原子タグ」を含めることで重複を克服します。ジェネレーターは純粋に数学的であり、スペクトル データの解釈を一切必要としません。スペクトル データは、構造のスコアリングと部分構造の情報に使用されます。ジェネレーターは、分子式に基づいて原子のペアの間に結合を形成し、すべての拡張が指定された制約に対してチェックされます。このプロセスをツリーと見なすと、ツリーの最初のノードは、スペクトル データによって部分構造が提供されている場合は、その部分構造を含む原子セットです。分子を結合で拡張することで、中間構造が構築されます。各中間構造は、生成ツリーのノードによって表すことができます。 ASSEMBLEは、使いやすさを考えてユーザーフレンドリーなインターフェースで開発されました。ASSEMBLEの2番目のバージョンは2000年にリリースされました。^[13]別のアセンブリ方法はGENOAです。^[14] ASSEMBLEや他の多くのジェネレータと比較して、GENOAは構成的な部分構造検索ベースのアルゴリズムであり、重複も考慮してさまざまな部分構造を組み立てます。

ジェネレータの効率と網羅性もデータ構造に関係している。以前の方法とは異なり、AEGIS ^[15]はリスト処理ジェネレータであった。隣接行列と比較して、リストデータはより少ないメモリを必要とする。このシステムではスペクトルデータが解釈されないため、ユーザーは入力としてサブ構造を提供する必要があった。構造ジェネレータは、HMBC、HSQC、その他のNMRデータなど、使用するデータの種類によっても異なる。LUCYは、未知分子のHMBCデータに基づくオープンソースの構造解明方法であり^[16]、最初にHMBC信号の解釈のすべての組み合わせが接続マトリックスに実装され、次に決定論的ジェネレータが欠落している結合情報を埋めることで完了する、網羅的な2段階構造生成プロセスを伴う。このプラットフォームは、任意のサイズの分子で構造を生成できるが、30個を超える重原子を含む分子式は、実際のアプリケーションには時間がかかりすぎる。この制限により、新しいCASEシステムの必要性が浮き彫りになった。 SENECAはLUCYの欠点を解消するために開発された。^[17]網羅的アプローチの限界を克服するために、SENECAは最適解を見つけるための確率的方法として開発された。このシステムは、シミュレーテッドアニーリングと遺伝的アルゴリズムという2つの確率的方法で構成される。まず、ランダムな構造が生成され、次にそのエネルギーが計算されて構造とそのスペクトル特性が評価される。この構造を別の構造に変換することにより、最適エネルギーに達するまでプロセスが続行される。生成において、この変換はジャン＝ルー・ファロンの規則に基づく方程式に依存している。^[18] LSD（構造決定のためのロジック）^{[19]は、フランスの科学者による重要な貢献である。このツールは、HMBCや}COSYデータなどのスペクトルデータ情報を使用して、すべての可能な構造を生成する。LSDは、一般公衆利用許諾書（GPL）の下でリリースされたオープンソースの構造ジェネレーターである。よく知られている商用CASEシステムであるStrucEluc ^[20]にも、NMRベースのジェネレーターが搭載されている。このツールはACD Labsのもので、特にMASSの開発者の一人であるMikhail Elyashbergが開発した。COCON ^[21]は別のNMRベースの構造生成ツールであり、構造生成に理論データセットを利用している。J-HMBCとJ-COSYを除くすべてのNMRタイプを入力として使用できる。

1994年、HuとXuは整数分割ベースの構造生成器を報告した。^[22]分子式をフラグメント、コンポーネント、セグメントに分解することは、整数分割の応用として実行された。これらのフラグメントは、構造生成器の構成要素として使用された。この構造生成器は、CASEシステムであるESESOCの一部であった。^[23]

一連の確率的生成器が Jean-Loup Faulon によって報告されました。ソフトウェア MOLSIG ^[24]は、標準ラベル付けと重複チェックのためにこの確率的生成器に統合されました。 ^[25]他の多くの生成器と同様に、ツリーアプローチは Jean-Loup Faulon の構造生成器の骨組みです。ただし、すべての可能な拡張を考慮すると、組み合わせ爆発が発生します。この網羅性に対処するために、順序立った生成が実行されます。OMG ^[26] 、 MOLGEN、Jean-Loup Faulon の構造生成器^[27]などの多くのアセンブリアルゴリズムは、順序立った生成方法です。Jean-Loup Faulon の構造生成器は、原子に対する同値クラスに依存しています。同じ相互作用タイプと要素を持つ原子は、同じ同値クラスにグループ化されます。分子内のすべての原子を拡張するのではなく、各クラスの 1 つの原子が他の原子に接続されます。以前のジェネレーターと同様に、Julio Peironcely の構造ジェネレーター OMG は、原子とサブ構造を入力として受け取り、幅優先探索法を使用して構造を拡張します。このツリー拡張は、すべてのブランチが飽和構造に到達すると終了します。

OMGは、Brendan McKayのNAUTYパッケージの標準拡張法に基づいて構造を生成します。このアルゴリズムは標準ラベル付けを計算し、1つの結合を追加して構造を拡張します。拡張を標準的に保つために、標準結合が追加されます。^[28] NAUTYはグラフ標準ラベル付けの効率的なツールですが、OMGはMOLGENよりも約2000倍遅いです。^[29]問題は、すべての中間構造の保存にあります。その後、OMGは並列化され、開発者はPMG（Parallel Molecule Generator）をリリースしました。^[30] MOLGENは1つのコアのみを使用してPMGよりも優れていますが、コアの数を10に増やすことでPMGはMOLGENよりも優れています。

構成的探索アルゴリズムは、Igor Faradjev のアルゴリズムなどの分岐限定法であり、メモリの問題に対する追加のソリューションです。分岐限定法は行列生成アルゴリズムです。以前の方法とは対照的に、これらの方法では、中間構造を構築せずにすべての接続行列を構築します。これらのアルゴリズムでは、正準基準と同型性チェックは、数学的群論の自己同型群に基づいています。MASS、SMOG ^[31]、および Ivan Bangov のアルゴリズム^{[32] は、}文献の良い例です。MASS は数学的合成の方法です。まず、特定の分子式のすべての接続行列を構築します。次に、原子価を行列生成の入力として使用します。行列は、制約と価数に関して原子間のすべての可能な相互作用を考慮して生成されます。構成的探索アルゴリズムの利点は、メモリ使用量が少ないことです。SMOG は MASS の後継です。

これまでの方法とは異なり、MOLGENは計算群論の応用として数学者のグループによってクローズドソースプラットフォームとして開発された、唯一維持されている効率的な汎用構造生成器です。MOLGENは秩序だった生成方法です。MOLGENにはさまざまなバージョンが開発されており、さまざまな機能を提供しています。ユーザーのニーズに基づいて、さまざまな種類の入力を使用できます。たとえば、MOLGEN-MS ^{[33]を使用すると、ユーザーは未知の分子の}質量分析データを入力できます。他の多くのジェネレータと比較して、MOLGENはさまざまな角度から問題にアプローチします。MOLGENの主な特徴は、すべての中間構造を構築せず、重複を生成せずに構造を生成することです。

この分野では、2021年までの最近の研究は船津公人研究グループによるものです。組み立て法の一種として、リングシステムや原子フラグメントなどのビルディングブロックが構造生成に使用されます。^[34]すべての中間構造は、あらゆる方法でビルディングブロックを追加することによって拡張されます。重複数を減らすために、ブレンダン・マッケイの標準パス拡張法が使用されます。生成時の組み合わせ爆発を克服するために、適用領域とリングシステムは逆QSPR / QSAR分析に基づいて検出されます。^[35]適用領域、またはターゲット領域は、QSPR / QSARからの生物学的および医薬品活性情報に基づいて記述されます。^[36]その研究では、単調に変化した記述子（MCD）を使用して適用領域を記述します。中間構造のすべての拡張に対して、MCDが更新されます。MCDの使用により、生成プロセスでの探索空間が削減されます。 QSPR/QSARベースの構造生成では、生成された構造の合成可能性が欠如しています。生成時に逆合成パスを使用すると、生成プロセスがより効率的になります。たとえば、RetroPath ^[37]と呼ばれるよく知られたツールは、与えられた反応ルールに基づく分子構造の列挙と仮想スクリーニングに使用されます。 ^{[38]そのコアアルゴリズムは幅優先法であり、各ソース化合物に反応ルールを適用して構造を生成します。構造生成と列挙は、Brendan McKayの標準拡張法に基づいて実行されます。RetroPath 2.0は、異性体変換、列挙、QSAR、}メタボロミクスなど、さまざまなワークフローを提供します。

これらの数学的構造生成法に加えて、生成オートエンコーダモデル^{[39] [40]}などのニューラルネットワークの実装は、この分野の新しい方向性です。

これらのアセンブリ方法とは異なり、削減方法では、原子ペア間のすべての結合を作成し、ハイパーグラフを生成します。次に、グラフのサイズが制約に関して縮小されます。まず、ハイパーグラフ内のサブ構造の存在が確認されます。アセンブリ方法とは異なり、生成ツリーはハイパーグラフから開始し、各ステップで構造のサイズが縮小します。結合はサブ構造に基づいて削除されます。サブ構造がハイパーグラフ内になくなった場合、サブ構造は制約から削除されます。ハイパーグラフによるサブ構造の重複も考慮されました。最も初期の削減ベースの構造ジェネレーターは COCOA ^[41]であり、徹底的かつ再帰的な結合除去方法です。生成されたフラグメントは、円形の指紋^[42]や原子シグネチャ^[43]に匹敵する、ストレージを最適化するために原子中心のフラグメントとして記述されます。構造を保存するのではなく、各原子の最初の隣接原子のリストのみが保存されます。削減方法の主な欠点は、ハイパーグラフのサイズが非常に大きいことです。実際、構造が不明な分子の場合、ハイパー構造のサイズが非常に大きくなり、実行時間が比例して増加します。

Simona Bohanec による構造生成器 GEN ^[44]は、構造の組み立てと構造の縮小という 2 つのタスクを組み合わせています。COCOA と同様に、問題の初期状態はハイパー構造です。組み立てと縮小の両方の方法には利点と欠点があり、GEN ツールは生成ステップでこれらの欠点を回避します。言い換えると、構造の縮小は構造制約が提供されている場合に効率的であり、構造の組み立ては制約がない場合の方が高速です。まず、無駄な接続が削除され、次にサブ構造が組み立てられて構造が構築されます。このように、GEN はこれらの方法を組み合わせることで、より効率的に制約に対処します。GEN は禁止構造を作成する接続を削除し、次にサブ構造情報に基づいて接続マトリックスを埋めます。この方法では、サブ構造間の重複は受け入れられません。マトリックス表現で構造が構築されると、飽和分子が出力リストに格納されます。COCOA 法はさらに改良され、新しいジェネレーター HOUDINI が構築されました。^[45]これは2つのデータ構造に依存しています。1つはハイパー構造内のすべての結合を表す化合物の正方行列を構築し、もう1つはサブ構造表現を使用して原子中心のフラグメントをリスト化する方法です。構造生成では、HOUDINIはすべての原子中心のフラグメントをハイパー構造にマッピングします。

化学構造を表すグラフでは、頂点と辺はそれぞれ原子と結合を表します。結合順序は辺の多重度に対応し、結果として化学グラフは頂点と辺にラベルが付けられたグラフになります。頂点と辺にラベルが付けられたグラフは、化学グラフとして記述されます。ここで、は頂点、つまり原子の集合であり、は結合を表す辺の集合です。 ${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle E}$

グラフ理論では、頂点の次数とは接続の数です。化学グラフでは、原子の最大次数はその原子価であり、化学元素が形成できる結合の最大数です。たとえば、炭素の原子価は 4 です。化学グラフでは、原子が原子価に達すると飽和します。グラフは、各頂点のペアの間に少なくとも 1 つのパスがある場合に接続されています。化学混合物^{[46]は多くの}化学者の主な関心事の 1 つですが、計算量の爆発的な増加により、多くの構造ジェネレーターは接続された化学グラフのみを出力します。したがって、目的は完全に飽和した分子を生成することであるため、接続性チェックは構造生成の必須の中間ステップの 1 つです。分子は、そのすべての原子が飽和している場合に飽和します。

要素の集合に対して、順列とはこれらの要素を並べ替えることである。^[47]以下に例を挙げる。

この表の 2 行目は、1 行目の順列を示しています。順列の乗算と は、以下に示すように、関数合成として定義されます。 ${\displaystyle a}$${\displaystyle b}$

${\displaystyle (a*b)(x)=a(b(x))}$

2 つの順列の組み合わせも順列です。群 は、次が成り立つように 定義された結合二項演算を伴う要素の集合です。${\displaystyle G}$ ${\displaystyle *}$${\displaystyle G}$

• のすべての要素に対して、を満たす要素が存在します。${\displaystyle I}$${\displaystyle G}$${\displaystyle g*I=g}$${\displaystyle g}$${\displaystyle G}$

• G の各元に対して、単位元に等しい元が存在します。${\displaystyle g^{-1}}$${\displaystyle g*g^{-1}}$

群の位数は、群の要素の数です。 は整数の集合であると仮定します。関数合成演算の下では、は対称群、つまり X 上のすべての順列の集合です。 のサイズが の場合、 の位数はです。集合系は、有限集合とその部分集合(集合のブロックと呼ばれる)で構成されます。集合系を保存する順列の集合は、グラフの自己同型を構築するために使用されます。自己同型は、グラフの頂点を順列化します。言い換えると、グラフをそれ自体にマッピングします。このアクションは、辺頂点保存です。 がグラフの辺で、 がの順列である場合、 ${\displaystyle X}$${\displaystyle Sym(X)}$${\displaystyle X}$${\displaystyle n}$${\displaystyle Sym(X)}$${\displaystyle n!}$ ${\displaystyle X}$${\displaystyle (u,v)}$${\displaystyle G=(V,E)}$${\displaystyle a}$${\displaystyle V}$

${\displaystyle a({u,v})=(a(u),a(v))}$

の順列はグラフの自己同型であり、 ${\displaystyle a}$${\displaystyle V}$${\displaystyle G=(E,V)}$

${\displaystyle a(u,v)}$はの要素であり、 はの要素です。${\displaystyle E}$${\displaystyle {(u,v)}}$${\displaystyle E}$

グラフの自己同型群は と表記され、上のすべての自己同型の集合である。分子グラフでは、正準ラベリングと分子対称性検出は自己同型群の実装である。この分野ではInChI ^[48]やALATIS ^[49]などのよく知られた正準ラベリング手法があるが、 NAUTYは自己同型群の計算と正準ラベリングによく使用されるソフトウェアパッケージである。 ${\displaystyle G}$${\displaystyle Aut(G)}$${\displaystyle V}$

利用可能なソフトウェア パッケージとそのリンクを以下に示します。

• 簡略化された分子入力ラインエントリシステム

この記事は、 CC BY 4.0ライセンス（2021）（査読者レポート） の下、以下のソースから改変されました： Mehmet Aziz Yirik、Christoph Steinbeck （2021年1月5日） 。「化学グラフジェネレーター」。PLOS Computational Biology。17（1）：e1008504。doi：10.1371 / JOURNAL.PCBI.1008504。ISSN 1553-734X。PMC  7785115。PMID 33400699。Wikidata  Q104747658  。 

• ウィキメディア・コモンズの化学グラフに関連するメディア