論文の概要: 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のエネルギー効率を向上した。
関連論文リスト
- Replicable Learning of Large-Margin Halfspaces [50.330457600322084]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳(メタデータ) (2024-02-21T15:06:51Z) - Efficient Convex Algorithms for Universal Kernel Learning [50.877957471649395]
カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。
従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。
本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-15T04:57:37Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。