第2回講義ノート

アルゴリズムと情報処理
（第２回）
慶應義塾大学生命情報学科
榊原康文
ゲノム科学におけるソートプログラム利用の例

類似遺伝子のデータベース上の相同性検索



相同性検索プログラムは配列が類似している遺伝子を
探索する
ゲノムデータベースには，何千万～何億という遺伝子配
列が登録されている
BLASTは代表的な相同性検索プログラム

BLASTはスコアの高い類似遺伝子から表示
入力配列
■DNA配列
■アミノ酸配列
類似遺伝子
や
アノテーション
ID1:ACGGTTC
ID2:GGGAACT
……
ID1000:
CATGAGG
ゲノムデータベース
ＢＬＡＳＴによる高スコアの遺伝子リスト表示




BLASTは，入力配列と相同性の高いスコアから順に類似
遺伝子を「並び替えたリスト」を表示する
スコアには，「ビットスコア」と「E-Value」という２つのスコア
が用いられる
何千万という遺伝子に対してスコアを計算して，そのスコア
の高い順に並び替えてリストを作成するためには，何千万
の遺伝子を高速にソートするプログラムが必要になる
BLASTは通常この作業を数秒で計算して結果を返す
Score
Sequences producing significant alignments:
(bits)
gi–129369–sp–P04637–P53˙HUMAN Cellular tumor antigen p53
703
gi–129367–sp–P13481–P53˙CERAE Cellular tumor antigen p53
679
gi–3024332–sp–P56424–P53˙MACMU Cellular tumor antigen p53 679
gi–3024331–sp–P56423–P53˙MACFA Cellular tumor antigen p53 677
gi–10720194–sp–Q9TTA1–P53˙TUPGB Cellular tumor antigen p53 654
gi–10720190–sp–O36006–P53˙MARMO Cellular tumor antigen p53 612
gi–2842741–sp–Q95330–P53˙RABIT Cellular tumor antigen p53 612
E
Value
0.0
0.0
0.0
0.0
0.0
e-175
e-175
分割統治法：アルゴリズム設計スキーマ

分割統治法の定義：
① アルゴリズムを設計する上での有効なスキーマ（技法）の
一つ
② Divide and Conquer Method
③ 「与えられた問題をより小さな幾つかの部分問題に分割し，
各々を解いた後で，それらの部分解を統合して元の問題
の解を得る」

分割統治法のソート問題への応用：
① マージソート
② クイックソート
マージソート

マージとは：
–
１
１
与えられた2つのソート済みの配列 A[1],...,A[m] と
B[1],...,B[n] から，これらを統合した1つのソートされた
配列 C[1],..., C[m+n] を作る手続き
２
２
３
３
４
５
５
６
６
８
１
１
２
３
３
８
４
１０
１
２
２
５
３
６
４
１５
７
８
１０１５
計算時間は O(m + n)
マージソート

マージソート：
①
入力配列： A[1],...,A[n] が与えられる
②
n2k と仮定する（長さ n が2の巾乗になっている）
（そうでない場合は，高々 n1 個までのダミー要素（値は∞）を付加えて２
の巾乗にする）
１
７
２３４
２１０１
５
６
＋
６７８
∞ ∞ ∞
③
入力配列をk回分割することで要素一つだけからなる部分配列がn個
できる
④
2つの配列を次々にマージしていく
⑤
この操作を繰り返してk回行うと最終的に長さn2kのソートされた配列
が最終的に得られる
マージソート
n2k
klog n
（誤り）
14, 18, 21, 37
マージソートの計算量

マージソートの計算量解析：
k回
参考：
バブルソートの計算
時間は O(n2)
クイックソート
クイックソート：

–
Q-SORT(A, p, q) : 入力配列A[1],...,A[n] の中で，p番目からq番目の
要素からなる部分配列をソートして返す
ここで， A[1],...,A[n] 中のp番目からq番目の要素からなる部分配列
をA[p..q]で表す
–
PARTITION(A, p, q) :
① 枢軸要素の値 a を適当に決める
② 与えられたA[p..q]を2つの部分配列A[p..r]とA[r+1..q]に分割し，
A[p..r]のどの要素も a より小さく，A[r+1..q]のどの要素も a 以上
に大きくして，その時の r の値を返す
–
Q-SORT(A, 1, n) を呼び出すことにより，入力配列A[1],...,A[n] が
ソートされる
クイックソート
PARTITION(A, p, q) ：

①
枢軸要素（pivot） : A[r+1..q]の要素の最小値 a （すなわち，2つの分割
を定める境界となる値）
–
枢軸要素の選択の方法：

配列要素を左から見ていって異なる最初の値の大きい方をとる
（配列の左端の要素の値をとる，の改良版）
–

ランダムに1つ選ぶ

ランダムに3つの値を選びその中央値をとる
（例題）
A[1]
A[10]
3
2
0
5
8
3
4
1
3
2
2
2
0
1
8
3
4
5
3
3
＜３
r
≧３
枢軸要素＝３
PARTITION

PARTITION(A, p, q) ：
②
2つのポインタ変数 i, j を用意し，各々最左i=pと最右j=qの要素位置か
ら出発して，各々右・左へと進みながら各要素と a とを比較していく
③
ポインタ i の探索する要素がa≦A[i]であり，かつポインタ j の探索する
要素がa＞A[j]となる最初の地点を見つけ，A[i]とA[j]とを入れ換える
④
この比較探索と交換を2つのポインタが出会うまで続ける
⑤
出会いの地点の1つ左の要素の位置が値 r として返される
⑥
計算時間は，O(n)．
PARTITIONの実行例
枢軸要素＝３
A[1]
3
(a) 開始
2
0
5
8
3
4
A[10]
1
3
2
i
(b) ３と２を交換
j
3
2
0
2
8
3
4
1
2
0
5
8
3
4
i
i>j より終了
2
2
0
1
8
j i
3
4
出会いと終了
2
j
1
２回目の交換地点
(d) i=5, j=4となり，
3
最初の交換地点
i
(c) ５と１を交換
5
3
3
3
3
j
5
クイックソートプログラム
（訂正版）
procedure Q-SORT(A, p, q)
begin
if p < q then ;
r := PARTITION(A, p, q) ;
Q-SORT(A, p, r) ;
Q-SORT(A, r+1, q) ;
end
procedure PARTITION(A, p, q)
var i, j , a ;
begin i := p ; j := q ;
a を A[p, q] の中から適当に選んでくる ;
while i ≦ j do ;
while A[i] < a do i := i + 1 ;
while A[j] ≧ a do j := j  1 ;
if i ≦ j then;
A[i] と A[j] を交換する ;
i := i + 1 ; j := j  1 ;
r := i  1 ;
end
procedure Q-SORT(A, p, q)
begin
if p < q then ;
r := PARTITION(A, p, q) ;
Q-SORT(A, p, r) ;
Q-SORT(A, r+1, q) ;
end
クイックソートの実行例
Q-SORT(A, 1, 10)
r := 4
Q-SORT(A, 1, 4)
r := 2
Q-SORT(A, 1, 2)
Q-SORT(A, 3, 4)
Q-SORT(A, 1, 1) となり，
条件 p=1<q=1 は成り立た
ないので，何もせずに
returnとなる
r := 1
Q-SORT(A, 5, 10)
クイックソートの計算量

クイックソートの計算量解析：
平均実行時間は O(n log n) であり，定数係数が極めて小さ
いので実用的でよく用いられる
⇒うまく２分割されると深さが log n となるため

最悪実行時間：クイックソートは n 個の要素を最悪実行時間
O(n2) でソートする
最悪の入力例：
0
1
2
3
4
5
6
7
8
9
（枢軸要素の選択で，配列要素を左から見ていって異なる
最初の値の大きい方をとる，の場合）

Download Report