アラインメントとは

配列解析アルゴリズム特論 渋谷 配列解析アルゴリズム特論 渋谷

文字列探索・比較（３）

渋谷

東京大学医科学研究所ヒトゲノム解析センター （兼）情報理工学系研究科コンピュータ科学専攻 http://www.hgc.jp/~tshibuya

配列解析アルゴリズム特論 渋谷 今日の話題

¦

アラインメント上級編

¿高度なギャップコスト ¿大規模なアラインメント ¿アラインメントの計算量 ¿パラメトリック解析 ¿座標列のアラインメント

配列解析アルゴリズム特論 渋谷 （復習） アラインメント

¦

動的計画法で計算

¿

格子状グラフにおける最長（短）路

¿

O(nm) - n, m: 配列長

A T G C A C T

ATGC-A--CT

配列解析アルゴリズム特論 渋谷 （アラインメントのバリエーション１） もう少し高度なギャップ・コスト

¦

生物配列では挿入・削除は連続して起こることが多い。

¦

開始ギャップコストの導入

¿a·l+b ¿通称、アファイン（非線形）ギャップペナルティー ¿計算時間はO(nm)で不変 （後藤アルゴリズム）

TAKEYABUYAKETA

TAKOYA----KIYA

l

配列解析アルゴリズム特論 渋谷

アファインギャップの場合の最適解計算

¦ 枝とノードの役割を逆転させたグラフを考えればよい

配列解析アルゴリズム特論 渋谷 cf. 道路ネットワークでの最短時間経路の計算 左側通行の場合、右折は時間がかかることが多い ↓ 道路の片側を１つのノード、交差点を枝とするグラフを作成する （進入禁止なども簡単に表現できる） というわけで(?) line graphは interchange graphともよばれる ことがある（らしい）

配列解析アルゴリズム特論 渋谷 （アラインメントのバリエーション２） Smith-Waterman

¦

ローカルな保存部位の発見

¿スコアが0を切ったらやり直し ¿用途によっては複数の解を出すようにする必要 u高いスコアのところからトレースバック 0以下だったら0にリセット 最大のスコアの ところからトレースバック

配列解析アルゴリズム特論 渋谷 （アラインメントのバリエーション３） Palindrome

¦

対角線近くでSWアルゴリズムを走らせる

¿適当な幅だけ計算すればよい 配列S 配列S 相補塩基によるアラインメント A-U, C-G, （G-U） が結合してこんな形 をとる

配列解析アルゴリズム特論 渋谷 （アラインメントのバリエーション４） より一般的なギャップコストの場合

¦

O(n

3

)かかる

¿さかのぼらないといけないため

¦

ギャップコストが凸関数の場合は

O(n

2

log n)が可能

¿きわめて自然な設定 すべて比較しないと 最短路かどうかわ からない

配列解析アルゴリズム特論 渋谷 凸なスコアとは

¦

ギャップペナルティが上に凸

¿ギャップが始まるとスコアの推移が下に凸になる ¿そうではないギャップペナルティーは意味があまりない（ことが多 い）ので、これは妥当な仮定

TACCGCATGAAGGTCCAATAGCCTTGCGTTCGCAATCGT

TACCACGTG---ギャップの始まり ギャップの長さ ギ ャ ッ プ ペ ナ ル テ ィ ー 0

配列解析アルゴリズム特論 渋谷 ギャップ関数が凸関数の場合の計算

¦

ギャップの計算時に、後ろのスコアをすべて更新する

¿ただし、勢力範囲のみを管理する u潜る点を探すのに２分探索(O(log n))をする必要がある u格子グラフの２つの方向それぞれに関して行う必要がある。 ¿全体の計算時間はO(n2 log n) 一度潜ると、二度と浮上しない 正確な値はここ以前までしか計算していないものとする 同じ形状 y=a+f(x-b) y=a'+f(x-b') 位置 ス コ ア の 変移 この変化点のリストを管理し、更新の際は 更新するべき場所を２分探索で探索する ここまでは 計算済み ギャップ の開始点 ココがミソ！

配列解析アルゴリズム特論 渋谷 ギャップコストがパタンとテキストで異なる場合もある

¦

RNA・cDNAマッピング

¿パタンにはギャップがよく入る u特にGT-AGギャップのペナルティーを小さく u細かいギャップは好ましくない＝affine gapを用いる ¿テキスト側にはあまり入らない ¿アルゴリズムはほとんど同じままで対応可能

large gap = splice site

High similarity 95% - 99%

very simple splicing signals

reference

genome GT AG

配列解析アルゴリズム特論 渋谷 （アラインメントのバリエーション５） 外側のギャップについて

¦

無視したい場合と無視できない場合がある。

全体を比較したい→普通のアラインメント つなげていきたい このギャップは無視 DNAアセンブリ 遺伝子比較 A T G C A C T

ATGC-A--CT

外周を別扱いにすればよいだけ

配列解析アルゴリズム特論 渋谷 大規模なアラインメント

¦

大規模になるとそのまま計算することは難しい

¿染色体のＤＮＡの長さは数百Mbp (bp=base pair(塩基ペア)）

¦

対処法

¿Hirschberg Algorithm u時間計算量はそのままで、空間計算量を減らす ¿Crochemore-Landau-ZivUkelson Algorithm u時間計算量自体を減らす ’ ただし、あまり実用性はない ¿ヒューリスティックによる解法 uハッシュ、接尾辞配列等で、小さな一致を列挙する uそれらを組み合わせておおまかなアラインメントを作成 u微調整は通常のＤＰで行う など

配列解析アルゴリズム特論 渋谷 空間計算量を線形にする

¦

スコアだけを計算するならば、空間計算量は線形

¿このままではトレースバックができない ¿トレースバックも可能にする方法→Hirschberg Algorithm A T G C A C T

ATGC-A--CT

忘れてよい 一列記憶するだけで、スコアは計算可能

配列解析アルゴリズム特論 渋谷

Hirschberg Algorithm (1)

¦ 両側から（無記憶）ＤＰを行って、真ん中の列まで計算する ¦ 最長（短）路が真ん中の列のどこを通るのかを計算する ¿ 始点～それぞれの点、それぞれの点～終点の距離を足したものを比較 し、一番長（短）いノードを選べばよい！ (O(n)時間）

4

-3

5

2

1

7

3

-6

2

-3

4

1

12

3

-3

1

配列解析アルゴリズム特論 渋谷

Hirschberg Algorithm (2)

¦

それを

O(log m)回繰り返せば、最長（短）路の計算が可能

¿空間計算量はO(n+m)に収まる！ 4 -3 5 2 1 7 3 -6 2 -3 4 1 12 3 -3 1 この点を最長（短）路 が通ることはその前 の計算でわかってい る！ （この場所は最後ま で記憶しておく）

配列解析アルゴリズム特論 渋谷 ２に収束

Hirschberg Algorithm (3)

¦

時間計算量は？

¿

O(nm) × (1+1/2+1/4+1/8+ …) = O(nm)

¿

すなわち変わらない！

u小さい問題であれば、倍程度遅くなる u通常のアルゴリズムでメモリが足りない場合や、2次 キャッシュサイズ等の関係で、実際の計算が逆に速くなる 可能性も十分あり得る 4 -3 5 2 1 7 3 -6 2 -3 4 1 12 3 -3 1 次のレベルで計算する面積は半分！

O(nm + n) = O(nm)

配列解析アルゴリズム特論 渋谷

アラインメントの時間計算量を O(n2)より小さくすることは可能か？

¦

SETHの仮定の元では

O(n

2−ε

)の実現は不可能

¿SETHの元でO(dO(1)·n2−ε)で解けない問題として知られている「正

規ベクトル問題」（Orthogonal Vectors Problem）から還元

¦

SETH (Strong Exponential Time Hypothesis: 強指数時間

仮説)

[Impagliazzo & Paturi 2001]

¿n 変数、m 節からなるSATは O(mO(1)2(1 − ε)n) で解くことは不可能、

という仮説

[Backurs & Indyk 2015]

0 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1 0 0 1 1 0 1 1 0 1 0

A

B

内積が 0 の組を見つける d (= Θ(log n)) n n

配列解析アルゴリズム特論 渋谷 O(n2−ε_{)の実現は不可能だったとしても、多少は頑張れる？！}

¦

通常のＤＰには無駄な計算が「少し」含まれる

¿その無駄を省くことで O(n2/log n) アルゴリズムが存在 （Crochemore-Landau-ZivUkelson） uただし、アルファベットサイズが固定の場合

¿Backurs & Indyk の「 O(n2−ε)の実現は不可能」と矛盾しない

き し ゃ の き し ゃ が き し ゃ で き し ゃ す る も も も す も も も も も の う ち 「ももも」と「きしゃ」の比較が多い →無駄な計算をしている可能性あり

配列解析アルゴリズム特論 渋谷 Crochemore-Landau-ZivUkelson (1)

¦

LZ78圧縮

¿既出文字列を利用した圧縮 u繰り返しが多かったり、文字に偏りがあったりすると圧縮しやすい ¿圧縮率は uエントロピーに比例

uランダムな場合のサイズは O(n log s/log n)

’ s : アルファベットサイズ

とてもまともなとまとももともとまともなとまとではなかった

4, も 6, ま 3, も 4, と 6, と 8, な 5, と 9, か

配列解析アルゴリズム特論 渋谷 Crochemore-Landau-ZivUkelson (2)

¦

LZ78圧縮に基づくアラインメントグラフの分割

ATCGATATCATCGATGATCGTCTATTATA

A C A G T A G C A A G

配列解析アルゴリズム特論 渋谷 Crochemore-Landau-ZivUkelson (3)

¦

CLZアルゴリズム

¿各ブロックに対して距離行列を作る u実際には右下のノードのみを作成し、他の部分は他へのポインタ で作成する uブロックごとに、O（縦の長さ＋横の長さ）の計算量が必要

u全体の計算量はO(nm'+n'm) → O(n2/log n)

’ n',m'は圧縮サイズ ¿その行列を利用して全体の最長路を計算する uこれもO(nm'+n'm)でできる！←SMAWK algorithm 距離行列 DIST[i,j] DIST行列の大きさは(p+q-1)(p+q-2)だ が、ここで管理（＋計算）するのは右 下の1ノードのみ i j q p

配列解析アルゴリズム特論 渋谷

Crochemore-Landau-ZivUkelson (4)

¦

{D

_ij

}がMonge Arrayであれば、

¿O(n+m)時間でmax_j {p_i+D_ij}をすべての i に対して計算可能！

uSMAWK algorithm [Aggarwal, et al., '87]

Monge性： i > i', j > j' のとき D_ij+D_j'j' ≥ D_ij'+D_i'j が成り立つこと。 （この時、最大出力に 対応する枝を交わら ないように選ぶことが できる。さらに、任意 の入力をいくつか省 いても同じことが成立 する。） Maxをとる

{p

_i

}

距離行列

{D

_ij

}

j 足し算 n入力 m出力 minimumを求めたい場合は、正負を反転すれば同じ議論が可能

配列解析アルゴリズム特論 渋谷 Crochemore-Landau-ZivUkelson (5)

¦

アラインメントグラフのMonge性

交わるような最長（短）路がある場合、 まで のパス長は同じ筈 ＝ 交わらない最長路にすることができる アファインギャップコストには 残念ながら対応できない 原点からu, vへのそれぞれの 最長路のブロック内の軌跡 u v

配列解析アルゴリズム特論 渋谷 SMAWK Algorithm (1) ¦ いくつかノードを削除して、半分の大きさの問題を 作成 ¿ 出力側の偶数番目を削除 ¿ 入力側も次のルーチンで削除（線形時間） u 偶数番目の出力には明らかに使われない入力を削 除している ¥ それに対して、解を求める ¥ 削除したノードに関しては、上の結果を用いて全 体で線形時間で計算可能 ¥ すると  F(n) = F(n/2) + O(n) → O(n) REDUCE(d) { while (k<n) { if d(k, k) ≥ d(k, k+1) {k++;} else {delete_input(k); k--;} } } 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 Max 入力 出力

配列解析アルゴリズム特論 渋谷 SMAWK Algorithm (2)

¦

Reduce Routine

≥ 1 2 3 1 2 3 while (k<n) { if d(k, k) ≥ d(k, k+1) k++; else {delete_input(k); k--;} } Input 2をなくすると、これも なくなるので、やり直し 使われることは ないため input output < ≥ 1 2 3 1 2 3 delete input output

配列解析アルゴリズム特論 渋谷 SMAWK Algorithm (3)

¦

ノード数が元の半分である問題を、再帰的にアルゴリズム

を適用して解くことで、（元の）奇数番目の解が得られる。

1 2 3 4 5 6 1 2 3 4 5 6 ≥ ≥ ≥ ≥ ≥ ≥ 7 8 Input 8以降はMonge性によりOutput 6 以外のノードへは寄与しない ＝ 線形時間でチェック可能 Input Output 9 Input 7は削除してよい 半分（以下）のサイズ の問題になる ＝ 再帰的に解く

配列解析アルゴリズム特論 渋谷 SMAWK Algorithm (4)

¦

偶数番目の計算

1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 Output 2への最大値は この間から探せばよい ＝ 全体で線形時間 Output 1への最大値 Output 3 への 最大値 Input Output

配列解析アルゴリズム特論 渋谷 SMAWK Algorithm (5)

¦

全体の計算時間を

f(n)とすると

¿

f(n) = f(n/2) + O(n)

¿

これは

O(n)となる！

uさまざまなアルゴリズムでこのテクニックが用いられる ’ 中央値を求めるアルゴリズム ’ suffix array/treeを作成するアルゴリズム 𝑓𝑓 𝑛𝑛 ≤ 𝑓𝑓 𝑛𝑛_{2 + 𝑐𝑐𝑛𝑛} ≤ 𝑓𝑓 𝑛𝑛₄ + 𝑐𝑐 𝑛𝑛 + 𝑛𝑛₂ ≤ 𝑓𝑓 𝑛𝑛₈ + 𝑐𝑐 𝑛𝑛 + 𝑛𝑛₂ + 𝑛𝑛₄ … ≤ 𝑓𝑓(𝑐𝑐𝑐𝑐𝑛𝑛𝑐𝑐𝑐𝑐) + 2𝑐𝑐𝑛𝑛収束 c はコンスタント

配列解析アルゴリズム特論 渋谷 それでも解けない大きな問題は？： Match Chaining

¦

短い（殆ど）一致している部分文字列をつなげる

¿k 個の数列から昇順の最長（重み付き）subsequenceを計算 uO(k log k) usubstring: 連続している部分 / subsequence: 連続していなくてよい 頑張れば重なりも考慮できるが、 ここでは重なりはないものとする

配列解析アルゴリズム特論 渋谷

Longest Increasing Subsequence (1)

¦

Young Tableaux アルゴリズム

[A. Young, 1900]

¿Binを作成し最初の数字を入れる ¿２番目以降（新しく入れる数字＝n） u_{n よりも小さい数字を含まない一番左のbinを探し、それに入れる} ubinに入れることができなければ新しいbinを右端に作成する ¿後ろからtrace back uなるべく上（後ろのものより小さいものの中で最も大きいもの）を選ぶ

入力：

35 18 49 17 59 93 22 63 84 62 43 38

35 18 17 49 22 59 43 38 93 63 84 62

bin1 bin2 bin3 bin4 bin5

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 84より小さくとも、84よりも後に入力 されたものも存在する可能性がある このbinの中で、84より小さい 最大のものは、「必ず」84より 前に入力されたもの

配列解析アルゴリズム特論 渋谷

Longest Increasing Subsequence (2)

¦

このアルゴリズムはなぜ正しい？

¿

Young tableauxはそれぞれの数字で終了する

increasing sequence のうち最長のものを「すべて」

管理している

¿

新たに数字を追加する際には、各binの一番下の値

を見ればよい

u途中のものを見ても長いものは作れない

入力：

35 18 49 17 59 93 22 63 84 62 43 38

35 18 17 49 22 59 43 38 93 63 84 62

bin1 bin2 bin3 bin4 bin5

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12

配列解析アルゴリズム特論 渋谷

Longest Increasing Subsequence (3)

¦

計算量

(入力長をkとする） ¿入れるbinを探す u横方向の二分探索で O(log k) ¿trace backで一つ前を探す u縦方向の二分探索で O(log k) ¿全体の計算時間 uO(k log k) それぞれ（最大）k回行う必要

入力：

35 18 49 17 59 93 22 63 84 62 43 38

35 18 17 49 22 59 43 38 93 63 84 62

bin1 bin2 bin3 bin4 bin5

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12

配列解析アルゴリズム特論 渋谷 ここで、突然ですが、「鳩ノ巣原理 (Pigeonhole Principle)」とは？ ¦ 鳩がn羽、巣がm個 → ¿ 𝑛𝑛/𝑚𝑚 羽以上いる巣が必ず１つある ¿ 𝑛𝑛/𝑚𝑚 羽以下しかいない巣が必ず1つある ¦ 例 ¿ 鳩が６羽、巣が５つ → ２羽以上いる巣が必ず１つある ¿ 鳩が４羽、巣が５つ → 空の巣が必ず１つある ¿ 鳩が１１５羽、巣が２０ → ５羽以下しかいない巣が必ず1つある ない！

配列解析アルゴリズム特論 渋谷 （豆知識） 長さ n の数列には必ず 𝒏𝒏以上の長さのLISまたはLDSが存在する！

¦

l: 数列 {a

₁

, a

₂

, …, a

_n

}のLIS長

¿ただし、数列中の数字はすべて相異なるものとする

¦

l

_i

: 最後の数字が

a

_i

である IS のうち最長のもの (subLIS) の

長さ

¦

d

_k

:

l

_i

=k となる i の個数

¿d_p≥n/l となる p が存在 （鳩ノ巣原理）

¦

このとき、長さが

d

_p

であるDSが必ず存在する

¿すなわち、LDSの長さは d_p 以上、ということ！ 同じ長さのsubLIS DSになっている

ということは？

配列解析アルゴリズム特論 渋谷

Weighted Longest Increasing Subsequence

¦

重みつきの場合に欲しいルーチン

計算する順序

配列解析アルゴリズム特論 渋谷

Dynamic Range Maximum Query (RMQ) Problem (1) ¦ 集合Σ （最初は空集合） ¿ アイテム {I₁, I₂, ... , I_k} を挿入・削除していく ¿ それぞれのアイテム (I_i) は以下の値を持つ uPosition p_i uSize c_i ¦ 問題 ¿ 現地点で、[a, b] で最大のアイテムは？ ¦ アルゴリズム ¿ AVL木を使う ¿ O(log k) で、アップデート、問い合わせのどちらもが可能 ¿ ちなみにStaticであれば、O(1) （線形時間の前処理）も可能 Position a b output Size [Shibuya et al, 2003]

配列解析アルゴリズム特論 渋谷

Dynamic RMQ Algorithm (2)

a No need to check b

O(log k)nodes to check

position

¦

AVL木

[Adelson-Velskil & Landis 1962]

¿平衡木

uあるノードの子供の高さは高々１しか違わない

¿ノード (↔ item)

uIn-order traverse ↔ ポジション順

uそれぞれのノードが最大の子孫へのポインタを持つ

¦

O(log k) time for

¿Range maximum query

¿アップデート

uアイテムの挿入

配列解析アルゴリズム特論 渋谷 アラインメントのその他の問題

¦

パラメータを変えて計算したい

¿スコア表やギャップペナルティーは何を使えばよいのか、結 果を見ないと結局わからない、ということがあるため。 ¿でも無駄な計算はしたくない。

¦

立体構造アラインメント

¿座標列への拡張

¦

2本だけではなく、3本以上を同時に並べて比較したい

¿系統関係があり、その系統関係がわかっているならば２本毎 の比較でよいが、機能が類似しているだけで系統関係がな い、あるいはあっても不明である場合などは、「同時」に比較 したい。

配列解析アルゴリズム特論 渋谷 Parametric Analysis (1)

¦

アラインメントのスコアのパラメータ

¿スコア行列 ¿ギャップ（開始・延長・etc.）

¦

これらのパラメータを一つだけ変数（

x）と考えた場合、

アラインメントのスコアは

ax + b と表せる

REAFSQAIWRATFAQVPESRSLFKR--AEAFS-ALW--KFPQVPNFFSLFKGKS

配列解析アルゴリズム特論 渋谷 Parametric Analysis (2)

¦

パラメータの範囲内であれば、存在し得る解をすべて

求めることが、その数に比例した手間で計算可能

x Score a₁x+b₁ a₂x+b₂ a₃x+b₃ a₄x+b₄ パラメータ x の変化 に従っての（最適解と は限らない）ある解１ のスコアの変化

配列解析アルゴリズム特論 渋谷 Parametric Analysis (3)

¦

変化させるパラメータが複数の場合でも同様な解析

が可能

x y ２．この直線上で1次元の場合と同様の ことができる （右側・左側にεずらしたところで解析） 解１ 解2 １．まず、境界上で１次元のパラメトリック探索を行う

配列解析アルゴリズム特論 渋谷

タンパク質構造アラインメント

配列解析アルゴリズム特論 渋谷 配列のアラインメントとの違い ¦ DPが（そのままでは）使えない ¿ A[1..n]とB[1..m]の最適なアラインメント uA[i]とB[j]が並べられている、とする uA[1..i]とB[1..j]の最適なアラインメントがそのアラインメントの一部となってい るとは限らない ¦ 最適化するスコアが必ずしも明確でない ¿ 各原子（塩基）の様々な属性 u座標： 回転、平行移動を考慮しなければならない u原子名あるいは残基名 u水素結合等の有無 u特徴的な構造の中にあるかどうか（αへリックス等） ¿ ギャップの扱いは更に難しい ¿ 配列上の塩基の順序の扱い u配列上の順序は関係ない、とする場合もある u「近い原子」を結んだグラフの比較、と考える、など。 ¦ というわけで、難しいため、様々なヒューリスティックが用いられる。

配列解析アルゴリズム特論 渋谷

"Alternating Superposition and DP" Algorithm

1.

適当に

r 組の原子の対応付けを行う。

2.

それから最適なＲＭＳＤをとる

RとTを計算する。

3.

それに従ってすべての原子を移動する。

4.

すべての点の間の距離を求める。

5.

それをもとにＤＰでアラインメントを求め、新たな原

子の対応付けを決定する。

• 距離の二乗和（あるいは単なる和）が最小になるように。

6.

変化がなければ、あるいは一定回数以上計算すれ

ば、終了。

7.

対応付けされた原子の中から近い組み合わせの

トップ

r 個を選び、２へ。

配列解析アルゴリズム特論 渋谷

Double Dynamic Programming

¦

すべての

i, j の組に対して、A[i]とB[j]が対応していると

した場合のアラインメントを計算する

¿ヒューリスティックな計算 u高速に正確な「予測」をすることが求められる。 uここでもなんらかのDPで計算する。 ’ 計算量はかなり大きいことになる。 u高速化のため、適当にランダムにサンプルした原子に対して計算す ることもある。

¦

その

nm個のアラインメントの解から、A[i]、B[j]の組が

どの程度選ばれやすいかを適当に数値化する

¦

その数値を用いてDPでアラインメントを求める

配列解析アルゴリズム特論 渋谷

Contact Map Overlap Problem

¦

立体構造をグラフで表現して、グラフ同士を比較

¿残基間の距離がある値以下であるもの同士を枝で結ぶ ¿アラインメントにおいてu, vが対応し、u'、v'も対応するとし たとき、次のことがいえるものとする u(u, u') が存在⇔(v, v')が存在 ¿そのようなアラインメントの中で対応数（あるいはなんらか のスコア）が最大のものを見つける uＮＰ困難 u整数計画法などで解く

配列解析アルゴリズム特論 渋谷 Protein Threading

¦

3次元座標列と文字列のアラインメント

¿タンパク質構造の形はだいたい1000種類程度 ¿そのどれに当てはまりやすいかを計算することでアミノ酸 配列情報からの三次元構造予測ができる uエネルギーが小さくなるように、配列を当てはめる L K f(_{L, K, d)} d 近いところのエネ ルギーを計算 A N V -ギャップ ペナルティー W H -P -G E I Q E P V G これもＮＰ困難

配列解析アルゴリズム特論 渋谷 まとめ

¦

ここまで

¿アラインメントのいろいろ

¦

次回以降の話題

¿マルチプルアラインメント ¿文字列に対する索引とそれを利用した検索 uTextに対してなんらかの前処理を行う → 接尾辞木・接尾辞配列