抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ストリング処理や計算生物学のような様々な分野で多様な応用があるので,与えられたストリングにおける特性サブストリング(例えば,最大反復,最小固有サブストリング,最小存在単語)は重要な研究トピックである。特性サブストリングのためのいくつかの計数アルゴリズムが提案されてきたが,それらの空間利用が入力ストリングの長さに比例するので,それらは空間効率ではない。最近,ランレングス符号化Burrows-Wheeler変換(RLBWT)はストリング処理においてますます注目され,RLBWTのための様々なアルゴリズムが開発されている。しかし,RLBWTを有する特性サブストリングのための計数アルゴリズムを開発することは,課題のままである。本論文では,RLBWTに基づく特性サブストリングに対する最初の計数アルゴリズムであるr-enum(RLBWTベース計数)を提示した。O(nloglog(n/r))時間におけるR-enumランと,RLBWTにおけるランのストリング長nと数rの作動空間のO(rlogn)ビットを用いて,rは,高反復ストリング(すなわち,多くの反復を有するストリング)に対してnより著しく小さいと予想される。高反復ストリングのベンチマークデータセットを用いた実験により,r-enumの結果は以前の結果よりも空間効率が高いことを示した。さらに,100のヒトゲノムの300-ギガバイトストリングで実験を行うことにより,巨大なストリングへのr-enumの適用性を実証した。【JST・京大機械翻訳】
