本日 (3 時限目 ) の内容 バイオインフォマティクス ( 生命情報学 ) 応用生命科学 情報生命学第 3 回配列解析入門 生物学と情報学の学際領域の学問分野 目的 生物データに対する情報解析技術の開発 情報解析技術を利用した新たな生物学的知識の発見 生物学の実験技術の革新 ( 例 : 次世代シークエンサー ) 大量のデータ ウェット ( 実験 ) とドライ ( 解析 ) の協力が不可欠 2 3 バイオインフォマティクスで求められること 分子生物学のセントラルドグマ ( 現代版 ) 生物配列 (bologcal sequence) データベース構築 分子生物学的実験解析により得られた大量のデータを整備 アルゴリズム開発 数理的 情報科学的手法を駆使して 生物データを解析するアルゴリズムを開発 データ解析 既存のソフトウェアを使ってデータを網羅的に解析し 生物学的知識を発見 遺伝情報伝達の基本原理 ゲノム エピゲノム トランスクリプトーム プロテオーム メタボローム フェノーム DN 塩基配列 DN のメチル化 ヒストンの修飾クロマチン構造 mrn, non codng RN タンパク質 代謝物 表現型 DN 配列 4 種類の塩基,,, からなる文字列 例 : RN 配列 4 種類の塩基,,, U からなる文字列 例 : UUUUUUUUU アミノ酸配列 ( タンパク質配列 ) 20 種類のアミノ酸,, D, E, F,, H, I, K, L, M, N, P, Q, R, S,, V, W, Y からなる文字列 例 : PDVKVEYKYNDDDFVKVDKELFNRWN ( 注 ) 各文字はそれぞれ化学構造を持つ 4 5 6 分子生物学データベース 本日 (3 時限目 ) の内容 配列アラインメント 種類 名称 URL 核酸配列 NBI http://www.ncb.nlm.nh.gov/ 核酸配列 EN http://www.eb.ac.uk/ena 核酸配列 DDBJ http://www.ddb.ng.ac.p/ 配列リード SR http://www.ncb.nlm.nh.gov/sra/ RNファミリー Rfam http://rfam.xfam.org/ 代謝ネットワーク KE http://www.genome.p/kegg/ 配列が似ていれば機能も似ている 配列アラインメント 与えられた複数の配列において文字間の対応付けをとること ( またはその計算結果 ) 並べて比較する アラインメント 7 月 13 日 ( 木 ) 3 時限目加藤有己大阪大学大学院医学系研究科講義資料はこちら http://www.med.osakau.ac.p/pub/rna/ykato/lecture/bonfo17/ -- - 2 本の配列 ペアワイズアラインメント 3 本以上の配列 マルチプルアラインメント 7 8 9
ペアワイズアラインメント 配列 s, r に対するグローバルアラインメント 各配列にギャップ記号 - を挿入して同じ長さにそろえた配列の組 (s, r ) 入力 s: r: 文字同士の対応関係の明確化 ( 注 ) ギャップ記号は同じ位置に並ばない アラインメント s : - - r : - 最適アラインメント アラインメントをスコアで定量化 DN 塩基に対するスコア関数 ( 一致 不一致スコア ) アラインメント s - - r - アラインメントスコア S(s, r ) = w(, -) + w(, ) + w(, ) + w(-, ) + w(, ) + w(, ) + w(-, ) = - 1 + 1 + 1-1 - 1 + 1-1 = - 1 可能なアラインメントの中でスコア最大のものを求める 単純な列挙法によるアプローチ 仮定 : s = r = n (s も r も長さが同じ ) アラインメントにおいて各配列の文字をギャップを無視し先頭から1 個ずつ交互に取り出して得られる列 ( 挿入列 ) は 元のアラインメントと1 対 1 対応 例 s 1 s 2 s 3 - s r 1 - r 2 r 1 r 1 s 2 s 3 r 2 r 3 ( 長さ2n) 3 挿入列の総数 (= 可能なアラインメントの総数 )!! Strlng の公式! 2 指数個 単純な列挙法では指数時間かかる! 効率良く最適解を探索する必要がある 10 11 12 動的計画法 (DP) による最適アラインメント DP の表とアラインメントグラフ s = s 1 s 2 s n, r = r 1 r 2 r m : 入力配列 Needleman Wunschのアルゴリズム (1970) F(, ): s[1..] と r[1..] に対する最適アラインメントスコア 初期化 反復 ( 漸化式 ) DP は部分問題の解からより大きな問題の解を効率よく計算する手法 DP (dynamc programmng) table (4, 0) (0, 5) 各文字は と の間に置く F(, ) の値に対応 lgnment graph (4, 0) 1 (0, 5) w(s, r ) が基本単位となるように矢印と重みを書き込む ここでは一致 1 不一致 ギャップ 13 14 15 初期化 0 (4, 0) 1 0, 0 0, 0 0,, 0, 0,, 反復 ( 漸化式 ) 0 1 1, 1, max, 1 1,1, (4, 0) 最終結果 0 1 1 0 0 0 1 0 (4, 0) 0 2 1 0 1 3 頂点 から頂点 (n, m) への最大重みパス 最適アラインメント - ( 注 ) この時点では最大重みパスがどれなのか不明 16 17 18
トレースバック コラム : アルゴリズムと計算量 Needleman Wunsch のアルゴリズムの計算量 最終結果 F(n, m) の値は最適アラインメントのスコア 最適スコアを実現するアラインメントそのものは? F(n, m) から逆にたどりながらアラインメントを後ろから前へと計算 ( トレースバック ) 漸化式の計算過程で最大値を与える頂点 ( 位置 ) を記憶すればよい 0-5 1 0 0 0 1 0 0 2 1 0 1 3 (n, m) 計算量を入力サイズ n の関数で表現 計算機環境や実装プログラムに依存しないアルゴリズムの効率を計る尺度 漸近的増加率が大きい項で代表 例 : 4n 3 +3n 2 +2n+1 O(n 3 ) O(n 2 ) 時間のアルゴリズムは O(n 3 ) 時間のアルゴリズムより優れている 漸化式において 添え字の動く範囲を考える 時間計算量 ( どれだけの計算時間が必要か?) O(nm) n mのとき O(n 2 ) 領域計算量 ( どれだけのメモリが必要か?) O(nm) n mのとき O(n 2 ) 1 n 1 m 19 20 21 アフィンギャップスコア ギャップはバラバラよりも固まって出現する傾向が大きい 線形ギャップスコア vs. アフィンギャップスコア 線形ギャップスコアアフィンギャップスコア ギャップ開始 ギャップ伸長 - - - - -e -e -e ただし d > e > 0 アフィンギャップスコアはより現実に即したスコア 22 線形ギャップとアフィンギャップの比較 ギャップスコア関数をグラフ化すると理解しやすい 線形ギャップスコア : 0 アフィンギャップスコア : 1 0 0 1 k 23 アフィンギャップスコアを用いたアラインメントアルゴリズム 3 種類のテーブル M, I x, I y を用いた動的計画法 いずれも s 1 s と r 1 r のアラインメントスコアを表す 時間計算量 領域計算量はともに O(nm) s と r がマッチ s とギャップがマッチ r とギャップがマッチ 24 グローバル vs. ローカル ローカルアラインメントアルゴリズム ローカルアラインメントの例 全体でのアラインメント 長い配列の比較では必ずしも全体としては類似していない 連続した部分領域間のアラインメント ( ローカルアラインメント ) Smth Warterman のアルゴリズム (1981) DP の漸化式 DPテーブル 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 2 1 0 0 2 0 0 0 1 1 2 1 0 0 0 0 0 2 1 1 0 ローカルアラインメント - 類似 最適スコアは F(, ) の中での最大値 トレースバックは最大値から始めて 0 になる時点で終了 時間計算量 領域計算量はともに O(nm) スコア関数, 1 1,, 1 25 26 27
スコア行列 w(x, y) DN 塩基 一致 不一致スコア タンパク質アミノ酸 類似度を反映したスコア 多数のアラインメントからスコアを算出 M: ある確率分布に従ってギャップなしアラインメントを生成するモデル p ab : アミノ酸 (a, b) が同じ列に出現する確率 各列は独立に生成される R: 2 本の配列をランダムに生成するモデル q a : アミノ酸 a が出現する確率 s, r: ともに長さ n のアミノ酸配列 スコア行列の導出 オッズ比 ( アラインメント (s, r) がランダムな場合と比較してどの程度出現しやすいかを表す ):,, 対数オッズ比 スコア関数 対数オッズ比 = アラインメントスコア p ab, q a は実際のアラインメントから出現頻度を計算 ( にわとりと卵 ) 応用例 : PM 行列 [Dayhoff et al., 1978], BLOSUM 行列 [Henkoff & Henkoff, 1992] 本日 (3 時限目 ) の内容 28 29 30 ホモロジー検索 データベースに対する類似配列の検索 問い合わせ配列 配列データベース 局所的に類似する配列検索 類似配列 データベース中の配列と数百万回のアラインメント O(nm) 時間アルゴリズムでは時間がかかりすぎる! 最適性を犠牲にして高速に類似配列を検索 ( ヒューリスティクス ) FS [Lpman & Pearson, 1985] BLS [ltschul et al., 1990] BLS: Basc Local lgnment Search ool 両配列のドットマトリックス上で完全一致 ( または非常に類似したギャップなしの ) 領域 ( シード ) で 同じ対角線上にある近接ペアを検出 Query arget BLS におけるシード 2 段階伸長法 第 1 段階 : シードのペアを対角線方向に沿ってギャップを含めず前後に伸長 統計的に有意なアラインメントのみを考慮 HSP (Hgh scorng Segment Par) 第 2 段階 : HSP を連結させて DP によるギャップありローカルアラインメント 統計的有意度を計算 Query arget シードだけに着目して HSP を構成するため 探索空間の大幅な削減が可能 31 32 33 BLS サーバーを使ってみよう Standard Nucleotde BLS の入力画面 Nucleotde BLS サーバーの出力画面 http://blast.ncb.nlm.nh.gov/ [ltschul et al., 1997] 塩基配列なら Nucleotde BLS を選択 アミノ酸配列なら Proten BLS を選択 問い合わせ配列入力 アラインメントスコアの分布 データベース選択 アラインメント結果 実行 34 35 36
まとめ 参考文献 配列アラインメントはバイオインフォマティクスで古くから使われ 今なお有用である手法 グローバルアラインメント ローカルアラインメント 動的計画法 (DP) は配列解析を支える根幹技術の 1 つ 大量の配列検索のためのヒューリスティクス 阿久津達也 バイオインフォマティクスの数理とアルゴリズム 共立出版 2007 年 吉川寛 伊藤隆司 上野直人 佐々木裕之 中井謙太 ゲノム科学の基礎 岩波書店 2009 年 日本バイオインフォマティクス学会編 バイオインフォマティクス入門 慶應義塾大学出版会 2015 年 Durbn, R., Eddy, S., Krogh,. and Mtchson,., Bologcal Sequence nalyss, ambrdge Unversty Press, 1998 37 38