論文の概要: SDSR: A Spectral Divide-and-Conquer Approach for Species Tree Reconstruction

• arxiv url: http://arxiv.org/abs/2603.10215v1
• Date: Tue, 10 Mar 2026 20:31:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-12 16:22:32.681691
• Title: SDSR: A Spectral Divide-and-Conquer Approach for Species Tree Reconstruction
• Title（参考訳）: SDSR : 種木再構成のためのスペクトル除算とコンカレントアプローチ
• Authors: Ortal Reshef, Ofer Glassman, Or Zuk, Yariv Aizenbud, Boaz Nadler, Ariel Jaffe,
• Abstract要約: SDSRは,スペクトルグラフ理論に基づく種木再構成のための拡張性のある分割・縮小手法である。 SDSRは,種木復元アルゴリズムをサブルーチンとして組み合わせることで,実行時の大幅な節約効果が得られた。 理論解析により, SDSRとCA-MLやASTRALなどの共通種木法を組み合わせると, 最大10倍高速な実行環境が得られることが示された。
• 参考スコア（独自算出の注目度）: 6.093463322686422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recovering a tree that represents the evolutionary history of a group of species is a key task in phylogenetics. Performing this task using sequence data from multiple genetic markers poses two key challenges. The first is the discordance between the evolutionary history of individual genes and that of the species. The second challenge is computational, as contemporary studies involve thousands of species. Here we present SDSR, a scalable divide-and-conquer approach for species tree reconstruction based on spectral graph theory. The algorithm recursively partitions the species into subsets until their sizes are below a given threshold. The trees of these subsets are reconstructed by a user-chosen species tree algorithm. Finally, these subtrees are merged to form the full tree. On the theoretical front, we derive recovery guarantees for SDSR, under the multispecies coalescent (MSC) model. We also perform a runtime complexity analysis. We show that SDSR, when combined with a species tree reconstruction algorithm as a subroutine, yields substantial runtime savings as compared to applying the same algorithm on the full data. Empirically, we evaluate SDSR on synthetic benchmark datasets with incomplete lineage sorting and horizontal gene transfer. In accordance with our theoretical analysis, the simulations show that combining SDSR with common species tree methods, such as CA-ML or ASTRAL, yields up to 10-fold faster runtimes. In addition, SDSR achieves a comparable tree reconstruction accuracy to that obtained by applying these methods on the full data.
• Abstract（参考訳）: 種群の進化の歴史を表す木を復元することは系統学の重要な課題である。 複数の遺伝マーカーからのシーケンスデータを用いてこのタスクを実行すると、2つの重要な課題が生じる。 1つ目は、個々の遺伝子の進化の歴史と種間の不一致である。 第二の課題は計算であり、現代の研究には何千もの種が含まれている。 ここでは、スペクトルグラフ理論に基づく種木再構成のための拡張性のある分割対コンカレントアプローチであるSDSRを提案する。 このアルゴリズムは、種を所定の閾値以下になるまで、再帰的にサブセットに分割する。 これらのサブセットのツリーは、ユーザ・ちょうせん種木アルゴリズムによって再構成される。 最後に、これらのサブツリーはマージされ、完全なツリーを形成する。 理論的には,多種合体 (MSC) モデルに基づくSDSRの回復保証を導出する。 ランタイムの複雑性分析も行います。 SDSRは,種木再構成アルゴリズムをサブルーチンとして組み合わせることで,同じアルゴリズムを全データに適用した場合と比較して,大幅な実行時節約が得られることを示す。 実験により,不完全系統分類と水平遺伝子導入を用いたベンチマークデータセット上でSDSRを評価した。 理論解析により, SDSRとCA-MLやASTRALなどの共通種木法を組み合わせると, 最大10倍高速な実行環境が得られることが示された。 さらに、SDSRは、これらの手法を全データに適用することによって得られるものと同等の木の復元精度を達成する。

関連論文リスト

• PhyloGFN: Phylogenetic inference with generative flow networks [57.104166650526416]
  本稿では,系統学における2つの中核的問題に対処するための生成フローネットワーク(GFlowNets)の枠組みを紹介する。 GFlowNetsは複雑な構造をサンプリングするのに適しているため、木トポロジー上の多重モード後部分布を探索し、サンプリングするのに自然な選択である。 我々は, 実際のベンチマークデータセット上で, 様々な, 高品質な進化仮説を生成できることを実証した。
  論文  参考訳（メタデータ） (2023-10-12T23:46:08Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods [10.289846887751079]
  木構造を改変しないポストホックアルゴリズムである階層収縮(Hierarchical Shrinkage, HS)を導入する。 HSは、他の正規化技術と併用しても、決定木の予測性能を大幅に向上させる。 すべてのコードとモデルはGithubにある本格的なパッケージでリリースされている。
  論文  参考訳（メタデータ） (2022-02-02T02:43:23Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。 RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。 我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
  論文  参考訳（メタデータ） (2021-06-02T01:37:52Z)
• Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
  スペクトルトップダウン・リカバリ (STDR) は、大きな潜在木モデルを推定するための分割・コンカレントアプローチである。 STDRの分割ステップは非ランダムです。 代わりに、観測されたノードに関連する適切なラプラシア行列のFiedlerベクトルに基づいている。 私達はSTDRが統計的に一貫性があることを証明し、高い確率で木を正確に回復するために必要なサンプルの数を縛ります。
  論文  参考訳（メタデータ） (2021-02-26T02:47:42Z)
• nTreeClus: a Tree-based Sequence Encoder for Clustering Categorical Series [0.0]
  本稿では,nTreeClusというクラスタリングシーケンスデータに対するモデルに基づく新しいアプローチを提案する。 この新しい表現を採用することで、分類的時系列に固有のパターンを考慮し、シーケンスをクラスタ化する。 合成および実際のデータセット、タンパク質配列、カテゴリー時系列を用いた経験的評価は、nTreeClusが最先端のアルゴリズムよりも競合的あるいは優れていることを示した。
  論文  参考訳（メタデータ） (2021-02-20T03:58:17Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  本研究では,高次元scRNA-seqデータから意味のある木構造を同定する手法を提案する。 次に、低次元空間におけるデータのツリー構造を強調する木バイアスオートエンコーダDTAEを紹介する。
  論文  参考訳（メタデータ） (2021-02-11T08:48:48Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。 Katiyarら。 (2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。 統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
  論文  参考訳（メタデータ） (2021-01-22T01:57:35Z)
• Spectral neighbor joining for reconstruction of latent tree models [5.229354894035374]
  我々は,潜在木図形モデルの構造を復元する新しい手法であるSpectral Neighbor Joiningを開発した。 我々はSNJが一貫したものであることを証明し、推定された類似性行列から木回復を正すのに十分な条件を導出する。 SNJは,他の再建法と比較して,多数の葉や長い縁を持つ樹木を正確に復元するために,サンプルを少なくする。
  論文  参考訳（メタデータ） (2020-02-28T05:13:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。