論文の概要: Lossless Reductions and Hybrid Sampling for Phylogeny Using the Maximum Compatibility Criterion
- arxiv url: http://arxiv.org/abs/2610.18029v1
- Date: Tue, 13 Oct 2026 09:20:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-17 07:43:04.501629
- Title: Lossless Reductions and Hybrid Sampling for Phylogeny Using the Maximum Compatibility Criterion
- Title（参考訳）: 最大適合基準を用いた系統の無損失化とハイブリッドサンプリング
- Abstract要約: 相互に互換性のある文字の最大セットを保持することを目的とする系統的再構成のための基準を提供する。
Cherry (BMC Bioinformatics, 1827, 2017) によるリードアルゴリズムはこの表現を用いて最大互換文字集合を同定する。
- 参考スコア（独自算出の注目度）: 0.3262230127283452
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Maximum compatibility provides a criterion for phylogenetic reconstruction in which the objective is to retain a maximum set of mutually compatible characters. For binary characters, pairwise compatibility can be represented by a weighted graph whose vertices correspond to characters and whose edges connect compatible pairs. A leading algorithm by Cherry [BMC Bioinformatics, 18(1):127, 2017] uses this representation to identify maximum compatible character sets as maximum weight cliques. We formulate the problem as maximum weight independent set enumeration on the complement graph and use deterministic postprocessing to map sampled bit strings to maximal feasible solutions. To explore the prospects of quantum computational advantage, we further construct bespoke correction-in-the-loop Quantum Approximate Optimisation Algorithm instances and find that traditional Lagrange multiplier choices may not be optimal for the enumeration problem on noisy devices. We also introduce lossless graph reductions with reconstruction rules that preserve the complete set of optimal solutions. Our results indicate that graph reduction and sampling can be effectively combined to address the enumeration bottleneck in maximum compatibility phylogeny, while retaining exact reconstruction when the residual optimum set is completely resolved. We enhance Cherry's approach to maximum compatibility by introducing graph reduction techniques and quantum sampling. Our classical benchmarks show a clear difference between finding one optimum and recovering the optimum set in practice. We demonstrate the utility of our methods on graphs constructed from SARS-CoV-2 sequences.
- Abstract（参考訳）: 最大互換性は、相互に互換性のある文字の最大セットを保持することを目的として、系統的再構築のための基準を提供する。
二進文字に対しては、頂点が文字に対応し、エッジが互換性のあるペアを接続する重み付きグラフで表すことができる。
Cherry [BMC Bioinformatics, 18(1):127, 2017] によるリードアルゴリズムは、この表現を用いて、最大互換文字集合を最大重みの傾きとして識別する。
補グラフ上の最大ウェイト独立集合列挙法として問題を定式化し、決定論的後処理を用いてサンプルビット列を最大化可能な解にマッピングする。
量子計算の優位性の可能性を探るため、我々はさらに、ループ内量子近似最適化アルゴリズムのインスタンスを構築し、従来のラグランジュ乗算器の選択がノイズの多いデバイスにおける列挙問題に最適でないことを発見した。
また、最適解の完全な集合を保持する再構成規則による損失のないグラフの削減も導入する。
その結果,グラフの縮小とサンプリングを効果的に組み合わせて,残差最適集合が完全に解決された場合の正確な再構築を維持しながら,最大適合系統の列挙ボトルネックに対処できることが示唆された。
グラフ縮小法と量子サンプリングを導入することにより,Cherryの最大互換性に対するアプローチを強化する。
我々の古典的ベンチマークは、一つの最適点を見つけることと、実際に最適な点を回復することの間に明らかな違いを示している。
SARS-CoV-2配列から構築したグラフ上で,本手法の有効性を実証する。
関連論文リスト
- Binary Optimization with Complex Constraints via Quantum Approximate Multi-Objective Optimization [1.3827807729367585]
複雑な2次的目的や制約を持つ二項最適化問題のクラスは、多目的2次的非制約二項最適化問題として再定義できることを示す。
条件付きバリュー・アット・リスク制約の下でバイナリポートフォリオ最適化のアプローチを実証する。
論文 参考訳（メタデータ） (2026-09-12T08:07:15Z) - Towards a Hybrid Quantum Enhanced Solution for Densest k-Subgraph Problem [0.6649512409446104]
ガウスボソンサンプリング(GBS)の高密度k-グラフ問題(DkSP)への応用について検討する。
提案手法では, ほぼkに近いサンプルを, 実現可能なソリューションに変換し, 破棄する, 有効な古典的後処理戦略を導入する。
論文 参考訳（メタデータ） (2026-06-02T05:55:09Z) - Zeroth-Order Methods for Stochastic Nonconvex Nonsmooth Composite Optimization [51.63258496873442]
合成最適化問題に関するこれまでの研究は、滑らか性の主要な部分、あるいはこれら2つの近似滑らか性点をそれぞれ除外した機械学習の例を必要とする。
本研究では,この問題に対する2つの新しいアルゴリズムを提案する。
これらのアルゴリズムは数値実験により有効であることを示す。
論文 参考訳（メタデータ） (2025-10-06T02:35:42Z) - Optimal Multimarginal Schrödinger Bridge: Minimum Spanning Tree over Measure-valued Vertices [0.15469452301122175]
Multimarginal Schr"odinger Bridge (MSB) は、既知の統計と既知の相関構造を持つランダムベクトルの集合の最適結合を見つける。
最適MSBの計算は、測定値の頂点上での最小分散木問題の解に相当することがわかった。
論文 参考訳（メタデータ） (2025-09-12T18:15:42Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。
我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。
アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
論文 参考訳（メタデータ） (2022-10-31T17:59:29Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Optimizing embedding-related quantum annealing parameters for reducing
hardware bias [0.0]
各インスタンスが以前に選択した固定埋め込みを使用する場合、パラメータ最適化は問題のクラス全体に対して可能であることを示す。
具体的には、トレーニングフェーズにおいて、完全グラフの埋め込みEをアニールのハードウェアに固定し、次に次のパラメータ値のセットを調整するための最適化アルゴリズムを実行する。
テストフェーズでは、トレーニングフェーズ中に計算されたパラメータが、そのクラスからの他のグラフのランダムな選択にどれくらいうまく機能するかを推定する。
論文 参考訳（メタデータ） (2020-11-02T04:13:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。