Microsoft PowerPoint - lecture a.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - lecture a.pptx"

なおちかありはら
7 years ago
Views:

1 応用生命科学情報生命学第 3 回配列解析入門 7 月 14 日 ( 木 ) 3 時限目加藤有己大阪大学大学院医学系研究科講義資料授業目的情報科学と生命科学の融合領域である情報生命科学の基本的な手法を理解することを目的とする日程 3 時限目 4 時限目 6 月 30 日 ( 木 ) ゲノム配列決定とトランスクリプトーム ( 大島 ) 7 月 14 日 ( 木 ) 配列解析入門 ( 加藤 ) 7 月 21 日 ( 木 ) システムバイオロジー基礎 I ( 佐藤 ) 7 月 28 日 ( 木 ) 全ゲノム解析概説 ( 金谷 ) 新型シーケンサーを利用した転写制御機構の解析 ( 大島 ) RN 配列情報解析 ( 加藤 ) システムバイオロジー基礎 II ( 佐藤 ) 代謝シミュレーション概説 ( 金谷 ) 成績評価レポートおよび講義中に適宜行う小テストにより評価する 2 3 バイオインフォマティクス ( 生命情報学 ) Bonformatcan の仕事分子生物学のセントラルドグマ ( 現代版 ) 生物学と情報学の学際領域の学問分野目的生物データに対する情報解析技術の開発情報解析技術を利用した新たな生物学的知識の発見生物学の実験技術の革新 ( 例 : 次世代シークエンサー ) 大量のデータウェット ( 実験 ) とドライ ( 解析 ) の協力が不可欠データベース構築実験解析により得られた大量のデータを整備アルゴリズム開発数理的情報科学的手法を駆使して生物データを解析するアルゴリズムを開発データ解析既存のソフトウェアを使ってデータを網羅的に解析し生物学的知識を発見遺伝情報伝達の基本原理ゲノムエピゲノムトランスクリプトームプロテオーム DN 塩基配列 DN のメチル化ヒストンの修飾クロマチン構造 mrn, non codng RN タンパク質メタボロームフェノーム代謝物表現型生物配列 (bologcal sequence) 分子生物学データベース DN 配列 4 種類の塩基,,, からなる文字列例 : RN 配列 4 種類の塩基,,, U からなる文字列例 : UUUUUUUUU アミノ酸配列 ( タンパク質配列 ) 20 種類のアミノ酸,, D, E, F,, H, I, K, L, M, N, P, Q, R, S,, V, W, Y からなる文字列例 : PDVKVEYKYNDDDFVKVDKELFNRWN ( 注 ) 各文字はそれぞれ化学構造を持つ種類名称 URL 核酸配列 NBI 核酸配列 EN 核酸配列 DDBJ 配列リード SR RNファミリー Rfam 代謝ネットワーク KE

2 配列アラインメント配列が似ていれば機能も似ている配列アラインメント与えられた複数の配列において文字間の対応付けをとること ( またはその計算結果 ) 並べて比較するアラインメント本の配列ペアワイズアラインメント 3 本以上の配列マルチプルアラインメントペアワイズアラインメント配列 s, r に対するグローバルアラインメント各配列にギャップ記号 - を挿入して同じ長さにそろえた配列の組 (s, r ) 入力 s: r: 文字同士の対応関係の明確化 ( 注 ) ギャップ記号は同じ位置に並ばないアラインメント s : - - r : - 最適アラインメントアラインメントをスコアで定量化 DN 塩基に対するスコア関数 ( 一致不一致スコア ) アラインメント s - - r - アラインメントスコア S(s, r ) = w(, -) + w(, ) + w(, ) + w(-, ) + w(, ) + w(, ) + w(-, ) = = - 1 可能なアラインメントの中でスコア最大のものを求める単純な列挙法によるアプローチ動的計画法 (DP) による最適アラインメント DP の表とアラインメントグラフ仮定 : 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 指数個単純な列挙法では指数時間かかる! 効率良く最適解を探索する必要がある 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 不一致ギャップ初期化 (4, 0) 1 0, 0 0, 0 0,, 0, 0,, 反復 ( 漸化式 ) 1 1, 1, max, 1 1,1, (4, 0)

3 トレースバックコラム : アルゴリズムと計算量最終結果 (4, 0) 頂点から頂点 (n, m) への最大重みパス最適アラインメント - 最終結果 F(n, m) の値は最適アラインメントのスコア最適スコアを実現するアラインメントそのものは? F(n, m) から逆にたどりながらアラインメントを後ろから前へと計算 ( トレースバック ) 漸化式の計算過程で最大値を与える頂点 ( 位置 ) を記憶すればよい (n, m) 計算量を入力サイズ n の関数で表現計算機環境や実装プログラムに依存しないアルゴリズムの効率を計る尺度漸近的増加率が大きい項で代表例 : 4n 3 +3n 2 +2n+1 O(n 3 ) O(n 2 ) 時間のアルゴリズムは O(n 3 ) 時間のアルゴリズムより優れている Needleman Wunsch のアルゴリズムの計算量アフィンギャップスコア線形ギャップとアフィンギャップの比較漸化式において添え字の動く範囲を考える時間計算量 ( どれだけの計算時間が必要か?) O(nm) n mのとき O(n 2 ) 領域計算量 ( どれだけのメモリが必要か?) O(nm) n mのとき O(n 2 ) 1 n 1 m ギャップはバラバラよりも固まって出現する傾向が大きい線形ギャップスコア vs. アフィンギャップスコア線形ギャップスコアアフィンギャップスコアギャップ開始ギャップ伸長 e -e -e ただし d > e > 0 アフィンギャップスコアはより現実に即したスコアギャップスコア関数をグラフ化すると理解しやすい線形ギャップスコア : アフィンギャップスコア : 0 1 k アフィンギャップスコアを用いたアラインメントアルゴリズム 3 種類のテーブル M, I x, I y を用いた動的計画法いずれも s 1 s と r 1 r のアラインメントスコアを表す s と r がマッチグローバル vs. ローカル全体でのアラインメント長い配列の比較では必ずしも全体としては類似していないローカルアラインメントの単純な計算法各配列の全ての部分文字列の組に対してグローバルアラインメントを計算その中で最も高いスコアとなるアラインメントを出力 s 時間計算量領域計算量はともに O(nm) s とギャップがマッチ r とギャップがマッチ連続した部分領域間のアラインメント ( ローカルアラインメント ) r O(nm) O(n 2 ) O(m 2 ) = O(n 3 m 3 ) 時間! グローバル sの部分列アラインメントの個数 r の部分列の個数

4 ローカルアラインメントアルゴリズム Smth Warterman のアルゴリズム (1981) DP の漸化式最適スコアは F(, ) の中での最大値トレースバックは最大値から始めて 0 になる時点で終了時間計算量領域計算量はともに O(nm) ローカルアラインメントの例 DPテーブルスコア関数, 1 1 ローカルアラインメント -,, 1 スコア行列 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] 局所的に類似する配列検索データベース中の配列と数百万回のアラインメント O(nm) 時間アルゴリズムでは時間がかかりすぎる! 最適性を犠牲にして高速に類似配列を検索 ( ヒューリスティクス ) FS [Lpman & Pearson 1985] BLS [ltschul et al. 1990] BLS: Basc Local lgnment Search ool BLS におけるシード 2 段階伸長法 BLS サーバーを使ってみよう両配列のドットマトリックス上で完全一致 ( または非常に類似したギャップなしの ) 領域 ( シード ) で同じ対角線上にある近接ペアを検出 Query arget 第 1 段階 : シードのペアを対角線方向に沿ってギャップを含めず前後に伸長統計的に有意なアラインメントのみを考慮 HSP (Hgh scorng Segment Par) 第 2 段階 : HSP を連結させて DP によるギャップありローカルアラインメント統計的有意度を計算 Query arget シードだけに着目して HSP を構成するため探索空間の大幅な削減が可能 [ltschul et al. 1997] 塩基配列なら Nucleotde BLS を選択アミノ酸配列なら Proten BLS を選択

5 Standard Nucleotde BLS の入力画面 Nucleotde BLS サーバーの出力画面まとめ問い合わせ配列入力データベース選択アラインメントスコアの分布配列アラインメントはバイオインフォマティクスで古くから使われ今なお有用である手法グローバルアラインメントローカルアラインメント動的計画法 (DP) は配列解析を支える根幹技術の 1 つ大量の配列検索のためのヒューリスティクスアラインメント結果実行参考文献阿久津達也バイオインフォマティクスの数理とアルゴリズム共立出版 2007 年吉川寛伊藤隆司上野直人佐々木裕之中井謙太ゲノム科学の基礎岩波書店 2009 年日本バイオインフォマティクス学会バイオインフォマティクス事典共立出版 2006 年 Durbn, R., Eddy, S., Krogh,. and Mtchson,., Bologcal Sequence nalyss, ambrdge Unversty Press,

Microsoft PowerPoint - lecture a.pptx

Microsoft PowerPoint - lecture a.pptx 本日 (3 時限目 ) の内容バイオインフォマティクス ( 生命情報学 ) 応用生命科学情報生命学第 3 回配列解析入門生物学と情報学の学際領域の学問分野目的生物データに対する情報解析技術の開発情報解析技術を利用した新たな生物学的知識の発見生物学の実験技術の革新 ( 例 : 次世代シークエンサー ) 大量のデータウェット ( 実験 ) とドライ ( 解析 ) の協力が不可欠 2 3