WEKO3
アイテム
双方向r-index
https://ipsj.ixsq.nii.ac.jp/records/217765
https://ipsj.ixsq.nii.ac.jp/records/2177650b81cf83-931e-46b6-aa93-2d92a2dda567
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL22188002.pdf (932.4 kB)
|
Copyright (c) 2022 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-05-12 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 双方向r-index | |||||||||||
| タイトル | ||||||||||||
| 言語 | en | |||||||||||
| タイトル | Bi-directional r-indexes | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||
| 資源タイプ | technical report | |||||||||||
| 著者所属 | ||||||||||||
| 東京大学 | ||||||||||||
| 著者所属 | ||||||||||||
| Center for Biotechnology and Bioengineering／University of Chile | ||||||||||||
| 著者所属 | ||||||||||||
| 東京大学 | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| The University of Tokyo | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| Center for Biotechnology and Bioengineering / University of Chile | ||||||||||||
| 著者所属(英) | ||||||||||||
| en | ||||||||||||
| The University of Tokyo | ||||||||||||
| 著者名 |
荒川, 侑馬
× 荒川, 侑馬
× Gonzalo, Navarro
× 定兼, 邦彦
|
|||||||||||
| 論文抄録 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | 反復の多い文字列を効率的に圧縮する索引は，バイオインフォマティクスやバージョン管理されたリポジトリなどの分野において有用である．Burrows-Wheeler 変換 (BWT) の連長圧縮を用いて実現される r-index はそのような索引の一種であり，BWT における run の数を r としたとき，O(r) 語の空間計算量でパターンの出現位置を高速に検索することができる．この検索は，パターンの後方探索の過程で接尾辞配列のサンプルを保持し，そのサンプルからパターンの出現位置を全て計算するアルゴリズムにより実現される．本研究では，このアルゴリズムを発展させ，パターンを双方向に拡張可能かつ，探索の任意の時点でパターンの出現位置列挙が可能である双方向 r-index(br-index) を提案する．また，数値実験により，索引サイズ，および DNA のアラインメントを模した検索クエリの速度を評価する． | |||||||||||
| 論文抄録(英) | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | Indexing highly repetitive texts is important in fields such as bioinformatics and versioned repositories. The run-length compression of the Burrows-Wheeler transform (BWT) provides a compressed representation particularly well-suited to text indexing. The r-index is one such index. It enables fast locating of occurrences of a pattern within O(r) words of space, where r is the number of equal-letter runs in the BWT. Its mechanism of locating is to maintain one suffix array sample along the backward-search of the pattern, and to compute all the pattern positions from that sample once the backward-search is complete. In this paper we develop this algorithm further, and propose a new bi-directional text index called the br-index, which supports extending the matched pattern both in forward and backward directions, and locating the occurrences of the pattern at any step of the search, within O(r+rR) words of space, where rR is the number of equal-letter runs in the BWT of the reversed text. Our experiments show that the br-index captures the long repetitions of the text, and outperforms the existing indexes in text searching allowing some mismatches except in an internal part. | |||||||||||
| 書誌レコードID | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AN1009593X | |||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2022-AL-188, 号 2, p. 1-8, 発行日 2022-05-12 |
|||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||
| Notice | ||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||
| 出版者 | ||||||||||||
| 言語 | ja | |||||||||||
| 出版者 | 情報処理学会 | |||||||||||
