生命情報学入門 配列のつなぎ合わせと再編成 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター 講義予定 • • • • • 5月24日:タンパク質立体構造予測法 5月31日:タンパク質立体構造予測演習 6月7日:機械学習を用いたタンパク質の分類法 6月14日:タンパク質の分類法演習 6月21日:配列のつなぎ合わせと再編成 講義の内容 • 配列のつなぎ合わせ – 等長断片からの配列決定 – 最短共通拡大文字列 • ゲノム再編成 – 逆位によるソーティング（符号なしの場合） – 逆位によるソーティング（符号ありの場合） 配列のつなぎ合わせ 配列のつなぎあわせ • ゲノム配列の決定 – 32億文字を一度に決めるのは無理 – （制限酵素を使って）短く切って、つなぎ合わせる CTCACTCAAAGGCGGTAATACGGTTATCCACAGAATCAGGGGATAA 元の配列 酵素を使って切断 CTCACTCAAAGGCGGTAA GGTAATACGGTTATCCAC TATCCACAGAATCAGGGGATAA つなぎあわせ CTCACTCAAAGGCGGTAATACGGTTATCCACAGAATCAGGGGATAA 等長断片からの配列決定 問題の定式化 データ： 同じ長さの配列断片 問題： それぞれの配列断片のみがちょうど１回づつ 出てくるような配列はあるか？ ACA ACT CAC CTG ACA ACT CAC CAG ACACTG なし 一筆書きとオイラー オイラーの定理（有向グラフ版） 次のどちらかの条件を満たす時、一筆書きができる (a) どの点についても • 入って来る矢印の数 ＝ 出て行く矢印の数 (b) ２点以外は上と同じで、残りの点は、それぞれ以下を満たす • 入って来る矢印の数 ＝ 出て行く矢印の数－１ • 入って来る矢印の数－１ ＝ 出て行く矢印の数 (a) (b) オイラーパス問題への変換 • 最初の２文字に対応する点から、最後の2文字に対応する点に 矢印を引く。 一筆書きできれば解あり、できなければ解なし データ AAA, AAC, ACC, CAA, CAC, CCA, CCC AAA A A CAA CA AAC CAC AC ACC C C CCC CCA CAAACCCAC 例題の解答 ACA ACT CAC CTG ACA ACT CAC CAG AC CA CT TG AC CA CT AG ただし、実際には誤りがあったり、断片の長さが同じではないので、 このままでは使えない。様々な工学的な工夫が必要 最短共通拡大文字列問題 問題の定式化 データ： 配列断片 問題： それぞれの配列断片を（重なりありで）つなぎ わせてできる一番短い文字列を見つけよ ACGTACAGTCAG ACGT 12文字 GTAC CAGT GTCAG GTACGTCAGT 10文字で 最短 問題の解き方（１） 着目点：断片の並べ方を決めると（その順番での）最短 拡大文字列が一意に決まる（なるべく左につめるよう につなげていく） ⇒ 並び方をみつければ良い pref(a,b): 断片 a の後に断片 b をつなげた時の a の中 で b と重ならない部分の長さ ovlp(a,b):断片 a の後に断片 b をつなげた時の a と b の重なっている部分の長さ a = CAGTC b = GTCAG CAGTC pref(a,b)=2 GTCAG ovlp(a,b)=3 問題の解き方（2） 断片の並べ方（s1,s2,s3,…,sn）を決めた後の 最短拡大文字列の長さ ＝ prefの総和 ＋ovlp(sn,s1) GTAC s1 pref(si,si+1) ACGT s2 GTCAG s3 CAGT s4 GTAC s1 GTACGTCAGT ovlp(sn,s1) 巡回セールスマン問題への変換 s2 ACGT 2 2 s1 GTAC 3 (=pref(GTAC, CAGT)) 2 4 4 2 4 5 (=pref(GTCAG, ACGT)) GTCAG s3 4 2 CAGT 4 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困難） • 転座、重複などを許した様々なパターン の問題が研究されている まとめ • 等長断片のつなぎ合わせ ⇒ 一筆書きへの変換 • 拡大最短共通文字列 ⇒ 巡回セールスマン問題への変換 • ゲノム再編成 ⇒ 最小回数の逆位による順列の 並び換え（ソーティング）
© Copyright 2024 ExpyDoc
