IT 配列解析2補足資料 藤 博幸 BIO BLAST (BasicLocalAlignmentSearchTool) (1)問い合わせ配列のwordへの分割 (2)生成されたwordの有限オートマトンによる表現 100101100 (3)wordのヒットの部分からのギャップなしの拡張 BLASTgapなしのアラインメント 問い合せ配列 の断片 アラインメントスコア y 配列データベース E-value: 配列データベースの配列を、問い合せ配列と比較 した時にy以上のスコアを有する類似性を示す配列の本数 の期待値 P-value: 配列データベースの配列を、問い合せ配列と比較 した時にy以上のスコアを有する類似性が見いだされる確率 いずれも小さい方が良い。E-valueが目安として使われる ことが多い。 E-value,P-valueの計算 0 -1 S Y V T G P M N R T W Q T S K I I Y BLASTrandomwalk 0から出発し、ungappedalignemntの各サイト のアミノ酸対に対応するスコアを考え、 それを加算していく。加算した結果が-1以下 になったらrandomwalkは停止するものとする。 この時各サイトのアミノ酸対の出現 頻度は、比較する2本の配列における アミノ酸の出現頻度の積で表される ものとする(BLASTの帰無仮説)。 (1) BLAST random walkの停止するまでに表れる最大値Y（↓）がy以上である 確率はgeometric-like distribution となる。Prob(Y > y) ~ C exp(- λy) (2) 問い合わせ配列の長さをN１, データベースから取り出した配列の長さをN2、 BLAST random walkが停止するまでの平均のステップ数をAとする。すると、 二つの配列を比較する際、n = (N１N2 )/A 個程度のrandom walkが生じる。 n個のrandom walkのいづれにおいても得られた最高スコアがy以上で ある確率は、順位統計に従い以下のように計算される。 . Prob(Y >.y) = 1 - (1 - Cexp(-λ (y-1)))n = 1 - (1 - Cnexp(-λ (y -1))/n) n� = 1 - exp(-Cnexp(-λ (y -1))) = 1 - exp(-N１N2 Kexp (-λy )) �ここで K = (C/A) exp(-λ）である。 (3) (2) で2本の配列を比較した時にy以上のスコアが得られる確率が計算された。 � 次に、データベース中でy以上のスコアを有する配列の本数の期待値を � 求める。データベース中の配列のトータルの残基数をDとすると、長さのN2 � 配列がD / N2本含まれていると見なす事ができる。そのそれぞれが、確率 � 1 - exp(-N１N2 Kexp (-λy ))でy以上のスコアを有するので、二項分布を考え E-value = ((1 - exp(-N１N2 Kexp (-λy )) D) / N2 となる。 (4) 上記のy以上のスコアを有する配列の本数に関する二項分布は、E-valueを � 平均と分散としたポアソン分布で近似できるものとする。 � すると、y以上のスコアが得られる確率は、そのようなスコアを有する ��配列の本数が0本である確率を1から引くことで得られるので、 ��P-value = 1 - exp(-E-value) ��として計算される。 ※�実際はedge effectに関する補正など、種々の補正が行われるので、 ��必ずしも上の通りの計算ではない。また、複数のアラインメント ��については、Karlin-Altschulのsum statisticが利用される。� より詳しくは添付の参考資料参照 オリジナルのBLASTはgapを扱えない 検出配列はgapが入らない代わりに、断片化されて しまい出力が見づらい Gapを導入できるように拡張されたgappedBASTが 構築された １）gapped-BLASTの手続き� � � Step 1: 有限オートマトン生成まではBLASTに同じ� Step 2: データベース中の各配列に次の操作を行う� � 2-1) 有限オートマトンによるhitを検出(これもBLASTに同じ) � � 2-2) 同じ対角線上で十分近接した２個のhitから� ungapped extensionによりHSPを求め、そこからseedを� 決定して両側にgapped extension を行う。� 2-3) 有意性評価(E-value)をして出力 Two-Hits Strategy と Gapped Extension � � (1) Two-hit induced ungapped extensionによるHSPの検出� (1-1) hit検出� (1-2) second hit (C末側で、距離がA残基以内の同じ対角線上)検出� (1-3) second hitからungapped extensionによりHSP検出� � (2) seedとなる残基対の同定� (2-1) HSPが11残基対以上の時: HSP にそって11残基のセグメントの� スコア を計算し、最大値を示すセグメントの中間をseedとする。� (2-2) HSPが11残基より短い時:中間の残基対をseedとする。� � (3) gapped extension � seedより両側に動的計画法によりgapped extensionを実行� ただし、この時の動的計画法は、現在見ている残基対のスコアが、� それ以前に達成された最高スコアからXg以下にならないように実行される。� これは、ungapped extensionが、それ以前に達成された最高スコアからX以下� にならないように実行されることに対応している。� Two-HitsStrategy １ BLASTの各hitごとの ungappedextensionは 時間を要するので、 その部分を短縮 同じ対角線上に ある二つのhitとは FASTAでいう所の 同じオフセット値 を有するタプルに 相当する。 Two-HitsStrategy ２ SecondhitからBLAST 同様にungappedextension を行い、HSPを求める HSPが11残基以下の長さの時 その中点の残基対をseedとする。 HSPが11残基対より長い時 11残基対のウィンドウでスキャン し、最大スコアを示す領域を見つ けその中点の残基対をseedとする。 Two-HitsStrategy ３ Seedとなる残基対 ここを出発点として 両側にgappedextension してアラインメントを 構築する。 gappedextension Seedとなる残基対 seedより両側に動的計画法により� gapped extensionを実行� ただし、この時の動的計画法は、� Smith & Waterman法ではない。� 現在見ている残基対のスコアが、� それ以前に達成された最高スコア� からXg以下にならないように実行� される。� これは、ungapped extensionが、� それ以前に達成された最高スコア� からX以下にならないように� 実行されることに対応している。 BLASTの統計評価 PSI-BLASTの統計評価 gapなしのアラインメント （HSP） gapのあるアラインメント のスコア のスコア 分布関数は理論的に導かれている BLASTの評価法をもとに シミュレーションなどにより パラメータをフィットさせて使用 実用上は問題ないが、理論的には gapのあるアラインメントの統計理論は 不十分なものである。
© Copyright 2025 ExpyDoc
