生命情報学入門 配列のつなぎ合わせと再編成 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

講義予定 5月24日:タンパク質立体構造予測法 5月31日:タンパク質立体構造予測演習 6月7日:機械学習を用いたタンパク質の分類法 6月14日:タンパク質の分類法演習 6月21日:配列のつなぎ合わせと再編成

講義の内容 配列のつなぎ合わせ ゲノム再編成 等長断片からの配列決定 最短共通拡大文字列 逆位によるソーティング（符号なしの場合） 逆位によるソーティング（符号ありの場合）

配列のつなぎ合わせ

配列のつなぎあわせ ゲノム配列の決定 32億文字を一度に決めるのは無理 （制限酵素を使って）短く切って、つなぎ合わせる CTCACTCAAAGGCGGTAATACGGTTATCCACAGAATCAGGGGATAA 元の配列 酵素を使って切断 CTCACTCAAAGGCGGTAA GGTAATACGGTTATCCAC TATCCACAGAATCAGGGGATAA つなぎあわせ CTCACTCAAAGGCGGTAATACGGTTATCCACAGAATCAGGGGATAA

等長断片からの配列決定

なし 問題の定式化 ACA CAC ACT CTG ACACTG ACA CAC ACT CAG データ： 同じ長さの配列断片 問題： それぞれの配列断片のみがちょうど１回づつ 出てくるような配列はあるか？ ACA CAC ACT CTG ACACTG ACA CAC ACT CAG なし

一筆書きとオイラー オイラーの定理（有向グラフ版） 次のどちらかの条件を満たす時、一筆書きができる (a) (b) (a) どの点についても 入って来る矢印の数 ＝ 出て行く矢印の数 (b) ２点以外は上と同じで、残りの点は、それぞれ以下を満たす 入って来る矢印の数 ＝ 出て行く矢印の数－１ 入って来る矢印の数－１ ＝ 出て行く矢印の数 (a) (b)

CAAACCCAC A C A A C C C A AAC AAA CAC ACC CAA CCC CCA オイラーパス問題への変換 データ 最初の２文字に対応する点から、最後の2文字に対応する点に矢印を引く。　一筆書きできれば解あり、できなければ解なし データ AAA, AAC, ACC, CAA, CAC, CCA, CCC A C A A AAC AAA CAC CAA ACC CCA CCC C C C A CAAACCCAC

例題の解答 ACA CAC ACT CTG ACA CAC ACT CAG AC CA CT TG AC CA CT AG ただし、実際には誤りがあったり、断片の長さが同じではないので、 このままでは使えない。様々な工学的な工夫が必要

最短共通拡大文字列問題

問題の定式化 ACGTACAGTCAG 12文字 ACGT GTAC CAGT GTCAG 10文字で 最短 GTACGTCAGT データ： 配列断片 問題： それぞれの配列断片を（重なりありで）つなぎわせてできる一番短い文字列を見つけよ ACGTACAGTCAG 12文字 ACGT GTAC CAGT GTCAG 10文字で 最短 GTACGTCAGT

問題の解き方（１） b = GTCAG a = CAGTC CAGTC GTCAG 着目点：断片の並べ方を決めると（その順番での）最短拡大文字列が一意に決まる（なるべく左につめるようにつなげていく） ⇒　並び方をみつければ良い pref(a,b): 断片 a の後に断片 b をつなげた時の a の中で b と重ならない部分の長さ ovlp(a,b):断片 a の後に断片 b をつなげた時の a と b の重なっている部分の長さ a = CAGTC b = GTCAG CAGTC ovlp(a,b)=3 GTCAG pref(a,b)=2

問題の解き方（2） GTAC ACGT GTCAG CAGT GTAC GTACGTCAGT s1 s2 s3 s4 s1 断片の並べ方（s1,s2,s3,…,sn）を決めた後の 最短拡大文字列の長さ ＝ prefの総和 ＋ovlp(sn,s1) GTAC s1 ovlp(sn,s1) pref(si,si+1) ACGT s2 GTCAG s3 CAGT s4 GTAC s1 GTACGTCAGT

巡回セールスマン問題への変換 ACGT GTAC GTCAG CAGT GTACGTCAGT s2 2 5 2 2 4 s1 s3 4 4 (=pref(GTCAG, ACGT)) 2 2 4 s1 GTAC GTCAG s3 4 4 4 2 2 3 4 (=pref(GTAC, CAGT)) CAGT s4 2+2+2+2+ovlp(CAGT,GTAC)=10 GTACGTCAGT

等長断片の場合との比較 等長断片の場合 ・オイラーパス（一筆書き）問題へ変換 ・すべての辺をちょうど１回通る ・効率良く計算可能 拡大最短共通文字列の場合 ・巡回セールスマン問題へ変換 ・すべての頂点をちょうど１回通る ・効率の良い計算は難しい（NP困難）

ゲノム再編成

ゲノムの概要構造は染色体の融合・分裂や部分配列の大規模な逆位・転座・重複により進化 ゲノム再編成 ゲノムの概要構造は染色体の融合・分裂や部分配列の大規模な逆位・転座・重複により進化 二種類の生物を比較して進化の過程を復元

逆位によるソーティング

逆位によるソーティング（符号なしの場合） ゲノム構造： 1からnまでの数字の順列 逆位：連続した部分列を反転 問題：与えられた順列を (1,2,3,4,…,n) にするための最短の逆位系列を計算 6 4 1 5 2 3 1 4 6 5 2 3 1 4 3 2 5 6 1 2 3 4 5 6

逆位によるソーティング（符号ありの場合） ゲノム構造： 1からnまでの数字の順列。ただし、各数字は符号（遺伝子の方向）がつく 逆位：反転した場合、符号も反転 キャベツ 1 -5 4 -3 2 1 -5 4 -3 -2 1 -5 -4 -3 -2 カブ 1 2 3 4 5

逆位によるソーティング 符号ありの場合 符号なしの場合 高速に計算可能 でも、アルゴリズムはかなり複雑 高速な計算は難しい（NP困難） 転座、重複などを許した様々なパターンの問題が研究されている

まとめ 等長断片のつなぎ合わせ ⇒ 一筆書きへの変換 拡大最短共通文字列 ⇒ 巡回セールスマン問題への変換 ゲノム再編成 　⇒　一筆書きへの変換 拡大最短共通文字列 　⇒　巡回セールスマン問題への変換 ゲノム再編成 　⇒　最小回数の逆位による順列の 　　　　並び換え（ソーティング）