論文の概要: ApHMM: Accelerating Profile Hidden Markov Models for Fast and
Energy-Efficient Genome Analysis
- arxiv url: http://arxiv.org/abs/2207.09765v2
- Date: Sat, 21 Oct 2023 21:42:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 14:55:26.533452
- Title: ApHMM: Accelerating Profile Hidden Markov Models for Fast and
Energy-Efficient Genome Analysis
- Title（参考訳）: aphmm:高速かつエネルギー効率の高いゲノム解析のためのプロファイル隠れマルコフモデル
- Authors: Can Firtina, Kamlesh Pillai, Gurpreet S. Kalsi, Bharathwaj Suresh,
Damla Senol Cali, Jeremie Kim, Taha Shahroodi, Meryem Banu Cavlak, Joel
Lindegger, Mohammed Alser, Juan G\'omez Luna, Sreenivas Subramoney, Onur
Mutlu
- Abstract要約: プロファイル隠れマルコフモデル(pHMM)は、DNAやタンパク質配列などの生物学的配列間の類似性を識別するために、様々なバイオインフォマティクス応用に広く用いられている。
Baum-Welchアルゴリズムは計算集約的であり、既存のソリューションはpHMMを固定したソフトウェアのみまたはハードウェアのみのアプローチを提供する。
ApHMMは,pHMMに対するBaum-Welchアルゴリズムに関連する計算オーバーヘッドとエネルギーオーバーヘッドを大幅に削減する,最初のフレキシブル・アクセラレーション・フレームワークである。
- 参考スコア（独自算出の注目度）: 7.989065035839646
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Profile hidden Markov models (pHMMs) are widely employed in various
bioinformatics applications to identify similarities between biological
sequences, such as DNA or protein sequences. In pHMMs, sequences are
represented as graph structures. These probabilities are subsequently used to
compute the similarity score between a sequence and a pHMM graph. The
Baum-Welch algorithm, a prevalent and highly accurate method, utilizes these
probabilities to optimize and compute similarity scores. However, the
Baum-Welch algorithm is computationally intensive, and existing solutions offer
either software-only or hardware-only approaches with fixed pHMM designs. We
identify an urgent need for a flexible, high-performance, and energy-efficient
HW/SW co-design to address the major inefficiencies in the Baum-Welch algorithm
for pHMMs.
We introduce ApHMM, the first flexible acceleration framework designed to
significantly reduce both computational and energy overheads associated with
the Baum-Welch algorithm for pHMMs. ApHMM tackles the major inefficiencies in
the Baum-Welch algorithm by 1) designing flexible hardware to accommodate
various pHMM designs, 2) exploiting predictable data dependency patterns
through on-chip memory with memoization techniques, 3) rapidly filtering out
negligible computations using a hardware-based filter, and 4) minimizing
redundant computations.
ApHMM achieves substantial speedups of 15.55x - 260.03x, 1.83x - 5.34x, and
27.97x when compared to CPU, GPU, and FPGA implementations of the Baum-Welch
algorithm, respectively. ApHMM outperforms state-of-the-art CPU implementations
in three key bioinformatics applications: 1) error correction, 2) protein
family search, and 3) multiple sequence alignment, by 1.29x - 59.94x, 1.03x -
1.75x, and 1.03x - 1.95x, respectively, while improving their energy efficiency
by 64.24x - 115.46x, 1.75x, 1.96x.
- Abstract（参考訳）: プロファイル隠れマルコフモデル(pHMM)は、DNAやタンパク質配列などの生物学的配列間の類似性を識別するために、様々なバイオインフォマティクス応用に広く用いられている。
pHMMでは、シーケンスはグラフ構造として表現される。
これらの確率はその後、シーケンスとpHMMグラフの類似点を計算するために使用される。
Baum-Welchアルゴリズムは、それらの確率を利用して類似度スコアを最適化し、計算する。
しかし、Baum-Welchアルゴリズムは計算集約的であり、既存のソリューションはpHMMを固定したソフトウェアのみまたはハードウェアのみのアプローチを提供する。
pHMMに対するBaum-Welchアルゴリズムの主な非効率性に対処するために、フレキシブルで高性能でエネルギー効率のよいHW/SW共同設計の緊急ニーズを特定する。
ApHMMは,pHMMに対するBaum-Welchアルゴリズムに関連する計算オーバーヘッドとエネルギーオーバーヘッドを大幅に削減する,最初のフレキシブル・アクセラレーション・フレームワークである。
ApHMMはBaum-Welchアルゴリズムの主要な非効率性に取り組む
1)様々なpHMM設計に対応するフレキシブルハードウェアの設計。
2) オンチップメモリによる予測可能なデータ依存パターンのメモリ化手法
3)ハードウェアベースのフィルタを用いて、無視可能な計算を迅速にフィルタリングし、
4)冗長計算の最小化。
ApHMMはBaum-WelchアルゴリズムのCPU、GPU、FPGAの実装と比較して15.55x - 260.03x, 1.83x - 5.34x, 27.97xの大幅な高速化を実現している。
ApHMMは3つの主要なバイオインフォマティクスアプリケーションで最先端のCPU実装より優れている。
1)エラー訂正
2)タンパク質ファミリー探索、及び
3) それぞれ1.29x - 59.94x, 1.03x1.75x, 1.03x - 1.95xの多重配列アライメントを行い,64.24x - 115.46x, 1.75x, 1.96xのエネルギー効率を向上した。
関連論文リスト
- An efficient solution to Hidden Markov Models on trees with coupled branches [0.0]
木上の隠れモデル(HMM)のフレームワークを拡張して、データのツリーのような構造が結合されたブランチを含むシナリオに対処する。
本研究では,木系HMMと分岐した分岐木に対する確率,復号化,パラメータ学習問題を効率的に解くプログラミングアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-06-03T18:00:00Z) - All-to-all reconfigurability with sparse and higher-order Ising machines [0.0]
オール・ツー・オールのネットワーク機能をエミュレートする多重アーキテクチャを導入する。
適応並列テンパリングアルゴリズムの実行は、競合するアルゴリズムと事前ファクターの利点を示す。
pビットIMのスケールされた磁気バージョンは、汎用最適化のための最先端技術よりも桁違いに改善される可能性がある。
論文 参考訳（メタデータ） (2023-11-21T20:27:02Z) - Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。
本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。
具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-28T16:53:41Z) - ClaPIM: Scalable Sequence CLAssification using Processing-In-Memory [1.6124241068249217]
ClaPIMは、ハイブリッド・イン・クロスバーとニア・クロスバー・メムリシティブ・イン・メモリ(PIM)の概念に基づくスケーラブルなDNA配列分類アーキテクチャである。
Kraken2と比較すると、ClaPIMはより高度な分類品質(F1スコアの最大20倍)を提供し、1.8倍のスループット向上を示す。
論文 参考訳（メタデータ） (2023-02-16T13:30:36Z) - A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive
Coding Networks [65.34977803841007]
予測符号化ネットワークは、ベイズ統計学と神経科学の両方にルーツを持つ神経科学にインスパイアされたモデルである。
シナプス重みに対する更新規則の時間的スケジュールを変更するだけで、元の規則よりもずっと効率的で安定したアルゴリズムが得られることを示す。
論文 参考訳（メタデータ） (2022-11-16T00:11:04Z) - HybMT: Hybrid Meta-Predictor based ML Algorithm for Fast Test Vector
Generation [2.1028463367241033]
HybMT は EPFL ベンチマーク回路の故障カバレッジを損なうことなく、CPU 時間で 56.6% の低下を示した。
HybMTはまた、最高のMLベースのアルゴリズムよりも126.4%高速化されている。
論文 参考訳（メタデータ） (2022-07-22T19:38:25Z) - Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for
Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を与えられた永続図計算の効率的なアルゴリズムを提案する。
我々はこのアルゴリズムを離散モース理論の設定内で表現し、考慮すべき入力単純さの数を著しく削減する。
また、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
論文 参考訳（メタデータ） (2022-06-27T10:54:24Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Predictive Coding Approximates Backprop along Arbitrary Computation
Graphs [68.8204255655161]
我々は、コア機械学習アーキテクチャを予測的符号化に翻訳する戦略を開発する。
私たちのモデルは、挑戦的な機械学習ベンチマークのバックプロップと同等に機能します。
本手法は,ニューラルネットワークに標準機械学習アルゴリズムを直接実装できる可能性を高める。
論文 参考訳（メタデータ） (2020-06-07T15:35:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。