パス誘導確率的勾配降下によるパンゲノームグラフレイアウト

動機：完全なゲノムの可用性が高まると、モデルが集団全体でゲノムの変動を研究する必要があります。パンゲノームグラフは、複数のゲノム間の完全なゲノムの類似性と多様性をキャプチャします。それらを理解するには、それらを見る必要があります。視覚化には、人間の読み取り可能なグラフレイアウトが必要です。グラフが低い（例えば2つの）次元描写に埋め込まれています。Pangenomeグラフの潜在的な過度のサイズのため、これは重要な課題です。 結果：それに応じて、新しいグラフレイアウトアルゴリズム：パス誘導確率勾配降下（PG-SGD）を紹介します。PG-SGDは、パンゲノムグラフで表されるゲノムをパスとして使用し、ノードのペア間のゲノム距離をサンプリングする埋め込み位置システムとして使用します。これにより、確率勾配降下（SGD）によるグラフ図面の以前のバージョンで見られる二次コストが回避されます。実装は、ギガベーススケールのパンゲノームグラフの低次元レイアウトを効率的に計算し、生物学的特徴を発表することを示します。 可用性：MITオープンソースライセンスの下でフリーソフトウェアとしてリリースされるODGIにPG-SGDを統合しました。ソースコードはhttps://github.com/pangenome/odgiで入手できます。

MOTIVATION: The increasing availability of complete genomes demands for models to study genomic variability within entire populations. Pangenome graphs capture the full genomic similarity and diversity between multiple genomes. In order to understand them, we need to see them. For visualization, we need a human readable graph layout: A graph embedding in low (e.g. two) dimensional depictions. Due to a pangenome graph's potential excessive size, this is a significant challenge. RESULTS: In response, we introduce a novel graph layout algorithm: the Path-Guided Stochastic Gradient Descent (PG-SGD). PG-SGD uses the genomes, represented in the pangenome graph as paths, as an embedded positional system to sample genomic distances between pairs of nodes. This avoids the quadratic cost seen in previous versions of graph drawing by Stochastic Gradient Descent (SGD). We show that our implementation efficiently computes the low dimensional layouts of gigabase-scale pangenome graphs, unveiling their biological features. AVAILABILITY: We integrated PG-SGD in ODGI which is released as free software under the MIT open source license. Source code is available at https://github.com/pangenome/odgi.