論文の概要: ApHMM: Accelerating Profile Hidden Markov Models for Fast and
Energy-Efficient Genome Analysis
- arxiv url: http://arxiv.org/abs/2207.09765v1
- Date: Wed, 20 Jul 2022 09:16:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-21 13:07:30.386657
- 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)はバイオインフォマティクスの応用において、生物学的配列間の類似性を正確に識別するために広く用いられている。
Baum-Welchアルゴリズムは計算コストが高く、既存の研究はpHMMの固定設計のためにソフトウェアまたはハードウェアのみのソリューションを提供する。
pHMMに対するBaum-Welchアルゴリズムの計算およびエネルギーオーバーヘッドを大幅に削減できる最初のフレキシブル・アクセラレーション・フレームワークであるApHMMを提案する。
- 参考スコア（独自算出の注目度）: 8.350439097570943
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Profile hidden Markov models (pHMMs) are widely used in many bioinformatics
applications to accurately identify similarities between biological sequences
(e.g., DNA or protein sequences). PHMMs use a commonly-adopted and
highly-accurate method, called the Baum-Welch algorithm, to calculate these
similarities. However, the Baum-Welch algorithm is computationally expensive,
and existing works provide either software- or hardware-only solutions for a
fixed pHMM design. When we analyze the state-of-the-art works, we find that
there is a pressing need for a flexible, high-performant, and energy-efficient
hardware-software co-design to efficiently and effectively solve all the major
inefficiencies in the Baum-Welch algorithm for pHMMs.
We propose ApHMM, the first flexible acceleration framework that can
significantly reduce computational and energy overheads of the Baum-Welch
algorithm for pHMMs. ApHMM leverages hardware-software co-design to solve the
major inefficiencies in the Baum-Welch algorithm by 1) designing a flexible
hardware to support different pHMMs designs, 2) exploiting the predictable data
dependency pattern in an on-chip memory with memoization techniques, 3) quickly
eliminating negligible computations with a hardware-based filter, and 4)
minimizing the redundant computations. We implement our 1) hardware-software
optimizations on a specialized hardware and 2) software optimizations for GPUs
to provide the first flexible Baum-Welch accelerator for pHMMs. ApHMM provides
significant speedups of 15.55x-260.03x, 1.83x-5.34x, and 27.97x compared to
CPU, GPU, and FPGA implementations of the Baum-Welch algorithm, respectively.
ApHMM outperforms the state-of-the-art CPU implementations of three important
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.
- Abstract（参考訳）: プロファイル隠れマルコフモデル(pHMM)は、生物学的配列(例えばDNAやタンパク質配列)の類似性を正確に識別するために多くのバイオインフォマティクスアプリケーションで広く用いられている。
PHMMは、Baum-Welchアルゴリズム(英語版)と呼ばれる一般的で高精度な手法を用いて、これらの類似性を計算する。
しかし、Baum-Welchアルゴリズムは計算コストが高く、既存の研究は固定pHMM設計のためのソフトウェアまたはハードウェアのみのソリューションを提供する。
pHMMに対するBaum-Welchアルゴリズムのすべての主要な非効率性を効率的かつ効果的に解決するために、柔軟で高性能でエネルギー効率のよいハードウェア・ソフトウェア共同設計が必要であることが判明した。
pHMMに対するBaum-Welchアルゴリズムの計算およびエネルギーオーバーヘッドを大幅に削減できる最初のフレキシブルアクセラレーションフレームワークであるApHMMを提案する。
ApHMMはハードウェア・ソフトウェア共同設計を活用してBaum-Welchアルゴリズムの主な非効率性を解決する
1)異なるpHMM設計をサポートするフレキシブルハードウェアを設計する。
2) オンチップメモリにおける予測可能なデータ依存パターンをメモリ化手法で活用する。
3)ハードウェアベースフィルタによる無視可能な計算を迅速に除去し、
4)冗長計算の最小化。
私たちは
1)専用ハードウェアにおけるハードウェア・ソフトウェア最適化
2) GPUのソフトウェア最適化により、pHMMのための初めての柔軟なBaum-Welchアクセラレータを提供する。
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.03x-1.75x、1.03x-1.95xである。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。