文献

J-GLOBAL ID：202202250299413588   整理番号：22A0982892

DNA配列のためのqフレームハッシュ比較に基づく厳密ストリングマッチングアルゴリズム【JST・京大機械翻訳】

q-frame hash comparison based exact string matching algorithms for DNA sequences

著者 (2件)： Karcioglu Abdullah Ammar (Department of Computer Engineering, Ege University, Izmir, Turkey) ,  Bulut Hasan (Department of Computer Engineering, Ege University, Izmir, Turkey)
資料名： Concurrency and Computation: Practice & Experience  (Concurrency and Computation: Practice & Experience)
巻： 34  号： 9  ページ： e6505  発行年： 2022年 
JST資料番号： W2542A  ISSN： 1532-0626  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： ストリングマッチングの重要性は,医学やバイオインフォマティクスのような多くの分野での応用による。探索をスピードアップするために,様々なストリングマッチングアルゴリズムを開発した。特に,ハッシュベースの正確なストリングマッチングアルゴリズムは,最も時間効率の良いものの一つである。ハッシュベース手法の効率はハッシュ関数に依存する。したがって,完全ハッシングはハッシュベースストリングマッチングにおいて本質的な役割を果たす。本研究では,2つのqフレームハッシュ比較ベース厳密ストリングマッチングアルゴリズム,Hq-QFおよびHqBM-QFを提案した。提案したアルゴリズムのDNA配列に対して無衝突完全ハッシュ関数を用いた。第一のアプローチでは,最後のqcharactersに対してハッシュ値マッチングの後,Hash-qアルゴリズムにおける特性比較をqフレームハッシュ比較で置き換えた。第2のアプローチでは,良好なサフィックスシフトテーブルにおける[数式:原文を参照]入力で指示されたシフトサイズを利用して,最初のアプローチを改善した。特性比較の数が最小化されるので,提案アルゴリズムの最悪ケース時間複雑性は[数式:原文を参照]である。両アプローチにおいて,qフレームハッシュ比較はトレードオフとしてほとんどの特性比較を置き換える。結果は,提案した方式が実行時間効率と特性比較の数に関してHash-qアルゴリズムより効率的であることを示した。Copyright 2022 Wiley Publishing Japan K.K. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  パターンマッチング ,  *マッチング ,  ハッシュ関数 ,  ハッシング
準シソーラス用語： 配列解析 ,  バイオインフォマティクス ,  *DNA配列 ,  実行時間 ,  複雑性 ,  *ストリングマッチング , 【Automatic Indexing@JST】

著者キーワード (6件)： DNA配列 ,  ハッシュ関数 ,  ハッシュベースのストリングマッチング ,  パターンマッチング ,  配列解析 ,  ストリングマッチングアルゴリズム

分類 (1件)： 計算機網  (JC03000K)

タイトルに関連する用語 (2件)： DNA配列 ,  マッチングアルゴリズム