これは「文字列アルゴリズム Advent Calendar 2016」18日目の記事です。
はじめに
この記事では文字列からSUS, MUSと呼ばれる特徴的な部分を見つけ出す研究について紹介します。
Unique Substring
文字列にはDNA配列(A, T, G, C)や文章などがあります。それらの文字列にとって一度しか出現しない(ユニークな)部分文字列は、重要な意味を持つ可能性があります。例えば、DNA配列でユニークな配列は特徴のある遺伝情報を持つはずです。
ユニークな部分文字列を見つける事は、部分文字列が短いほど難しくなります。例えば"山田"がユニークな部分文字列であったとして、それに一文字追加した"山田優"は必ずユニークですが、一文字削った"山"はユニークでないことがあります。
"山田優は山へ芝刈りに行く"
下記のような短くてユニークな部分文字列を見つけ出す研究が行われました。
Minimal Unique Substring
文字列に対して、ユニークな部分文字列であり、一文字でも削るとユニークでなくなるものをMUSと定義します。
ユニークな部分文字列は必ずMUSを内包するので、ユニークな部分文字列の素と言えます。
長さ$n$の文字列の全てのMUSを$O(n)$時間で列挙できます。
上図の例では、文字列$T$のMUSを示しています。$T$[7..10]="baab"に注目すると、前一文字削った$T$[8..10]="aab"は$T$[1..3]に出現し、後一文字削った$T$[7..9]="baa"は$T$[11..13]に出現します。
Suffix TreeやLCP arrayを用いたアルゴリズムが知られています。
Shortest Unique Substring
文字列と文字列上のある位置が与えられ、その位置を含むユニークな部分文字列をSUSと定義します。
長さ$n$の文字列に前処理を$O$($n$)時間ですることで、クエリ位置$p$の全てのSUSを$O(|SUS(p)|)$時間で列挙できます。($SUS(p)$は$p$に対するSUSの集合)
SUSを見つけることはRNAのプライマー設計に役立ちます。RNAはある特定のDNA配列に張り付き、その周辺を複製します。
http://www.mls.sci.hiroshima-u.ac.jp/smg/education/replication.html
連長圧縮(RLE)された文字列に対してSUSを探索する研究が知られています。
おわりに
今回初めて記事の投稿してみました。
分かりやすいか、内容に不足がないか不安ですが、
少しでも文字列に興味を持っていただけたら幸いです。
参考文献
- Pei, J., Wu, W.C.H., Yeh, M.Y.: On shortest unique substring queries. In: Proc. ICDE. pp. 937–948 (2013)
- Haubold, B., Pierstorff, N., Wiehe, T.: Genome comparison without alignment using shortest unique substrings. BMC Bioinformatics 6(123) (2005)
- Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Shortest Unique Substring Queries on Run-Length Encoded Strings, Proc. the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
- Atalay Mert Ileri1, M. Oguzhan Kulekci2, Bojian Xu, Shortest Unique Substring Query Revisited, 25th Annual Symposium (CPM 2014)
- Kazuya Tsuruta, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Shortest Unique Substrings Queries in Optimal Time, Proc. 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), LNCS 8327, 503-513, 2014.01.