文献

J-GLOBAL ID：201902219451992419   整理番号：19A2416907

kミスマッチによる円形パターンマッチング【JST・京大機械翻訳】

Circular Pattern Matching with k Mismatches

著者 (9件)： Charalampopoulos Panagiotis (Department of Informatics, King’s College London, London, UK) ,  Kociumaka Tomasz (Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel) ,  Kociumaka Tomasz (Institute of Informatics, University of Warsaw, Warsaw, Poland) ,  Pissis Solon P. (CWI, Amsterdam, The Netherlands) ,  Radoszewski Jakub (Institute of Informatics, University of Warsaw, Warsaw, Poland) ,  Rytter Wojciech (Institute of Informatics, University of Warsaw, Warsaw, Poland) ,  Straszynski Juliusz (Institute of Informatics, University of Warsaw, Warsaw, Poland) ,  Walen Tomasz (Institute of Informatics, University of Warsaw, Warsaw, Poland) ,  Zuba Wiktor (Institute of Informatics, University of Warsaw, Warsaw, Poland)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11651  ページ： 213-228  発行年： 2019年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： kミスマッチ問題は,長さmのパターンPと長さnのテキストTのあらゆる長さmサブストリング間のHamming距離を計算することにある。多くの実世界応用において,Pのいかなる周期的シフトも関連パターンであり,したがって,Tのあらゆる長さmサブストリングの最小距離とPの任意の周期的シフトを計算することに関心がある。これは,kミスマッチ(k-CPM)問題との円形パターンマッチングである。この問題を解決するために多数の論文がなされているが,著者らの知る限りでは,平均ケース上限のみが知られている。本論文では,k-CPM問題に対する最初の自明でない最悪ケース上限を示した。具体的には,[数式:原文を参照]時間アルゴリズムと[数式:原文を参照]時間アルゴリズムを示した。後者のアルゴリズムは,k-ミスマッチ問題[Bringmannら,SODA2019]に対して最近開発された技術を拡張した方法で適用した。Copyright 2019 Springer Nature Switzerland AG Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *不整合 ,  *パターンマッチング ,  アルゴリズム ,  Hamming距離
準シソーラス用語： 最小距離 ,  テキスト , 【Automatic Indexing@JST】

分類 (2件)： 分子・遺伝情報処理  (JE15040B) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： ミスマッチ ,  円形 ,  パターンマッチング