ＲＮＡ配列比較検索の方法

Size: px

Start display at page:

Download "ＲＮＡ配列比較検索の方法"

けんじわにべ
5 years ago
Views:

1 RNA 配列の比較アルゴリズム 1. 東京大学大学院新領域創成科学研究科 2. 産業技術総合研究所生命情報科学研究センター浅井潔

2 麹菌 Aspergillus oryzae 遺伝子発見パイプライン Contig sequences cdna sequences GlimmerM sim4 Mapped cdnas GeneDecoder training set blastx ALN join check / translate predicted genes RepeatMasker trnascan

3 転写産物 (RNA) の大部分は非コード領域!! Genome Biology 2004, 5:105

4 様々なタイプの機能性非コード RNA がある機能性 RNA もゲノム上にコードされている mirna の発見 RNAi(RNA 干渉 ) の開発 ncrna は生体内のネットワークの重要な要素の一つ mirna sirna

5 遺伝子の構造 ( 真核生物 ) 転写開始点転写終結点プロモータエキソンエキソンエキソンエキソンポリ A イントロンイントロンイントロン 5 3 開始コドン終止コドン

6 タンパク質コード遺伝子の発見法既知転写産物との類似性 DB 上の既知遺伝子 (DNA) で相同性検索 DB 上の既知タンパク質で相同性検索 cdna をゲノム DNA 配列に貼り付ける比較ゲノム保存領域 (synteny) は重要 ab initio 遺伝子発見統計的な情報を用いた遺伝子の確率モデル

7 タンパク質コード遺伝子の発見法既知転写産物との類似性アラインメントによる配列の比較動的計画法 (DP) BLAST 比較ゲノム ab initio 遺伝子発見統計的な情報を用いた遺伝子の確率モデルモデルによるゲノム DNA の局所検索

8 非コード RNA タンパク質コード遺伝子の発見法既知転写産物との類似性アラインメントによる配列の比較動的計画法 (DP) BLAST???? 比較ゲノムきわめて重要 (QRNA, RNAz) ab initio 遺伝子発見統計的な情報を用いた遺伝子の確率モデルモデルによるゲノム DNA の局所検索 However, is it OK to define the conserved region by sequence similarities?

9 RNA 配列情報解析の課題ゲノム配列からの既知 ncrna 発見 trnascan-se, Snoscan, Infernal cdna 配列からの ncrna 発見クラスタリング二次構造予測 (xxxfold) 比較ゲノム保存領域からの ncrna 発見保存領域抽出 ncrna 判定 (QRNA, RNAz) 特定モチーフを持つ ncrna 発見二次構造モチーフと特定配列標的予測

10 配列の比較 :2 次元 DP G K R F D C G K F D E C F(i, j) = max F(i-1, j-1) + s(x i, y j ) F(i, j-1) - d F(i-1, j) - d メモリ O(L 2 ) 計算時間 O(L 2 )

11 通常のアライメント法塩基配列の各位置が進化の過程でそれぞれ独立に他の塩基への置換を起こすというモデルに基づいている ClustalW など

12 二次構造をもつ RNA の進化塩基対をつくる塩基ペアは塩基対を保つような塩基置換の仕方 ( 共置換 ) をする離れた 2 点での塩基の進化は独立でない配列の相同性が低くなってくると従来のアライメント法はうまくいかなくなってくる

13 二次構造を考慮したアラインメント seq.1 A A C A G C A U C G U C G seq.2 C A G A U A C G G C U G G C U C A G C A A A C U G seq.1 G C U G C A A A G C U G seq.2 G C U C A G C A A A C U G seq.1 G C U G C U U A G C U G seq.2

14 二次構造を考慮したスコア seq.1 seq.2 seq.3 A A C A G C A U C G C U G U U A C G G C C A G A UxC CxU GxG C A G C A A A C U G seq.1 G C U G C U U A G C seq.2 G C U G C A A C U G seq.3 seq.1 seq.2 seq.3 seq.1 seq.3 seq.2

15 あらゆる RNA 配列情報解析の基礎 RNA 配列の比較配列の文字列としての類似性ステム部分の塩基対類似性非塩基対部分の配列類似性 RNA の二次構造の類似性二次構造が異なるどう比較するのか? 二次構造が分からないどう比較するのか?

16 RNA の 2 次構造予測自由エネルギー最小化 ( 含 : 準最適構造 ) Nussinov & Jacobson ( Nussinov Algorithm, 1980) Mathews, Turner & Zuker (MFOLD, 2000) 配列比較解析相同 RNA 配列群が必要結果が初期整列に依存 Chiu and Kolodziejczak (1991) Eddy and Durbin (CM= プロファイル SCFG, 1994)

17 Secondary Structure Prediction of RNA gcaccggctaactccgtgccagcagccgcggtaatacggagggtgc gcaccggctaactccgtgccagcagccgcggtaatacggagggtgc

18 Secondary Structure Prediction of RNA gcaccggctaactccgtgccagcagccgcggtaatacggagggtgc gcaccggctaactccgtgccagcagccgcggtaatacggagggtgc

19 Secondary Structure Prediction of RNA gcaccggctaactc gcaccggctaactc

20 Nussinov アルゴリズム M(i,j) : maximum # of base pairs in (x i, x j ) M(i,j) = M(i+1, j) i i+1 j M(i,j) = M(i, j-1) i j-1 j M(i,j) = M(i+1, j-1) + 1 i+1 i j-1 j M(i,j) = max (M(i,k)+M(k+1,j)) k i k k+1 j

21 確率文脈自由文法 (SCFG) による RNA 二次構造予測 Σ = {a, c, g, u}, (x,y = a c g u) S = xs M(i,j) = M(i+1, j) i i+1 j S = Sx M(i,j) = M(i, j-1) i j-1 j S = xsy M(i,j) = M(i+1, j-1) + 1 i+1 i j-1 j S = SS M(i,j) = max (M(i,k)+M(k+1,j)) k i k k+1 j

22 SCFG の CYK アルゴリズム γ(i,j) : maxmum probability of (xi, xj) is parsed by S S = xs S = Sx S = xsy S = SS

23 RNA 二次構造予測の計算複雑度 M(i,j) = max (M(i,k)+M(k+1,j)) k i k k+1 j メモリ : M(i,j) for all position i,j = L 2 計算時間 : Iterate for all i,j,k = L 3

24 Turner のエネルギーパラメータースタックインターナルループヘアピンバルジヘアピンマルチループスタックヘアピン

25 RNA 配列比較の課題 2 本配列の比較共通二次構造の推定とアラインメント局所アラインメント ( 検索 ) 配列群のマルチプルアラインメント Marlet 配列群の共通二次構造予測二次構造付配列への構造アラインメント局所アラインメント ( 検索 ) 二次構造への構造アラインメント局所アラインメント ( 二次構造モチーフ検索 ) 配列クラスタリング特定 RNAのモデル局所アラインメント ( 特定 RNA 発見 ) 比較ゲノム保存領域からの機能性 RNA 発見

26 共通 2 次構造予測 Sankoff (1985) 2(N) 本の RNA の折畳み O(L 3N ) time, O(L 2N )space Gorodkin, Heyer & Stormo (FOLDALIGN, 1997) 2 本局所整列分岐構造なし塩基対の最大化 O(L 4 ) time 多重整列 : トーナメント法 + Greedy アルゴリズム Mathews & Turner (Dynalign, 2002) 自由エネルギー最小化 + 配列比較解析ステム間距離を M 以下 O(M 3 L 3 ) time Perriquet, Touzet & Dauchet (CARNAC, 2003) 局所配列類似性 + エネルギー + 塩基対共変

27 2 本の RNA 配列からの共通二次構造の計算 γ(i 1,j 1,i 2,j 2, ) : 4 次元のDP 行列 (# of non-terminal is constant) γ(i 1,j 1,i 2,j 2 ) =max (γ(i 1,k 1,i 2,k 2 )+γ(k 1 +1,j 1,k 2 +1,j 2 ) ) k 1,k 2 メモリ :O(L 4 ) i 2 k 2 k 2 +1 j2 1 L 2 Y 計算時間 :O(L 6 ) S a S S b 1 i 1 j L k1 k X

28 長さの 6 乗の計算時間とは? 配列長が 2 倍になると 64 倍の計算時間配列長が10 倍になると100 万倍!! 1 分の100 万倍は約 2 年 Sankoffアルゴリズムでは 150 塩基の2 配列の共通二次構造の計算に10 分以上かかります

29 Stem Candidate Aligner for RNA For each nucleotide sequences, Extract stem candidates of a fixed length Decompose each stem candidates into two parts: 5 and 3 stem component (left SC and right SC) Sort all SCs as a sequence by their positions Pairwise alignment DP of SCSs Remove inconsistent stem matches Construct backbone of common secondary structure Alignment of remaining nucleotide

30 Stem Candidates gcaccggctaactccgtgccagcagccgcggtaatacggagggtgc gcaccggctaactccgtgccagcagccgcggtaatacggagggtgc Base-pairing probabilities are calculated by McCaskill s algorithm. Base pairs of low probabilities are not used

31 Stem fragments of a fixed length Stem candidates longer than the fixed length is treated as continuous stem fragments

32 Stem Candidate Aligner for RNA For each nucleotide sequences, Extract stem candidates of a fixed length Decompose each stem candidates into two parts: 5 and 3 stem component (left SC and right SC) Sort all SCs as a sequence by their positions Pairwise alignment DP of SCSs Remove inconsistent stem matches Construct backbone of common secondary structure Alignment of remaining nucleotide

33 Decomposition of stem fragments into stem components position sequence distance complementary confidence score stacking energy

34 Stem Candidate Aligner for RNA For each nucleotide sequences, Extract stem candidates of a fixed length Decompose each stem candidates into two parts: 5 and 3 stem component (left SC and right SC) Sort all SCs as a sequence by their positions Pairwise alignment DP of SCSs Remove inconsistent stem matches Construct backbone of common secondary structure Alignment of remaining nucleotide

35 gcaccggctaactccgtgccagcagccgcggtaatacggagggtgc Stem Component Sequence (SCS) gcaccggctaactccgtgccagcagccgcggtaatacggagggtgc 1 gcac 1 gcac 2 cacc 3 accg 5 cggc 6 ggct 11 actc 12 ctcc 13 tccg 14 ccgt 14 ccgt 15 cgtg 15 cgtg 16 gtgc 16 gtgc 17 tgcc 17 tgcc 24 agcc 25 gccg 27 cgcg 28 gcgg 29 cggt 30 ggta 35 tacg 36 acgg 37 cgga 38 ggag 41 gggt 42 ggtg 42 ggtg 43 gtgc 43 gtgc gtgc 16 gtgc 43 ggtg 42 cggt 29 gccg 25 agcc 24 gggt 41 ggag 38 cgga 37 gcgg 28 acgg 36 cgcg 27 tacg 35 gcac 1 gtgc 43 ggta 30 ggtg 42 ggct 6 cggc 5 cgtg 15 ccgt 14 accg 3 tgcc 17 cgtg 15 ccgt 14 tccg 13 ctcc 12 actc 11 cacc 2 tgcc 17 gcac 1 gtgc 16

36 Stem Candidate Aligner for RNA For each nucleotide sequences, Extract stem candidates of a fixed length Decompose each stem candidates into two parts: 5 and 3 stem component (left SC and right SC) Sort all SCs as a sequence by their positions Pairwise alignment DP of SCSs Remove inconsistent stem matches Construct backbone of common secondary structure Alignment of remaining nucleotide

37 Relations of two stem fragments no overlap parallel overlap r-continous overlap nested r ill-continous overlap r pseudoknot contradict overlap

38 Left-right consistency of the SC match in SCS alignment

39 Left-right consistency of the SC match in SCS alignment

40 Dependencies in DP of SCSs 1-continous 1-continous = SCs with same positions and different complementary partners

41 Computational Time

43 Scarna web server

44 Scarna web server

45 Acknowledgments Functional RNA Project of METI Grant-in-Aid for Scientific Research on Priority Area Comparative Genomics AIST, CBRC, BIRC JBIC The University of Tokyo

生命情報学

生命情報学 5 隠れマルコフモデル阿久津達也京都大学化学研究所バイオインフォマティクスセンター内容配列モチーフ最尤推定ベイズ推定 M 推定隠れマルコフモデル HMM Verアルゴリズム EMアルゴリズム Baum-Welchアルゴリズム前向きアルゴリズム後向きアルゴリズムプロファイル HMM 配列モチーフモチーフ発見配列モチーフ : 同じ機能を持つ遺伝子配列などに見られる共通の文字列パターン