文献

J-GLOBAL ID：201002255665828388   整理番号：10A0944105

計算幾何学的な手法を用いた高速相同性計算手法

Efficient Similarity Computation based on Computational Geometry Techniques

著者 (2件)： 松井鉄史 (国立情報学研) ,  宇野毅明 (国立情報学研)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2010  号： 2  ページ： ROMBUNNO.BIO-22,2  発行年： 2010年08月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 編集距離(レーベンシュタイン距離)は文字列の距離を表すモデルの一つであり,ゲノムの比較をする際に頻繁に使われている。その一方で,素朴な方法は文字列長の2乗の計算時間であること,近似なしの高速計算は難しいこと,配列比較で重要視される局所的な類似性を考慮せず,とびとびの対応である程度類似すると判断するという問題点もある。本稿では,局所的な類似性に基づいた新しい類似性の尺度とその高速な計算手法を提案する。直観的には,編集距離はいかに多くの同一な文字を,入れ替えなしで対応できるかであるが,提案する断片編集距離では,ハミング距離が閾値以下の(長さが固定された)短い文字列を対応させる。これにより局所的な類似性を持つ部分のみを考慮できる。また,多くの場合,このようなハミング距離が閾値以下の短い文字列の組は,配列上に連続して現れることから,連続した出現をひとまとまりにすることで入力データ量を減らすと共に,計算幾何学的な手法を使うことで距離を高速計算するアルゴリズムを提案する。計算実験の結果,既存手法では計算できないような巨大な配列に対しても,本アルゴリズムは短時間で計算が終了することを示す。(著者抄録)

シソーラス用語： *相同性 ,  *高速アルゴリズム ,  計算幾何学 ,  *情報理論 ,  *計算量 ,  局所性 ,  類似性 ,  Hamming距離 ,  閾値 ,  文字列 ,  配列 ,  大規模系 ,  高速化
準シソーラス用語： *編集距離

分類 (2件)： システム・制御理論一般  (IA02010H) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 計算幾何学 ,  手法 ,  相同性 ,  計算