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

(1)

ＲＮＡ配列の比較アルゴリズム

１．東京大学大学院新領域創成科学研究科２．産業技術総合研究所生命情報科学研究センター

(2)

Aspergillus oryzae遺伝子発見パイプライン

cDNA sequences Contig sequences blastx sim4 GeneDecoder GlimmerM ALN Mapped cDNAs join predicted genes check / translate tRNAscan RepeatMasker training set 麹菌

(3)

Genome Biology 2004, 5:105

(4)

miRNA siRNA

様々なタイプの機能性非コードRNAがある

機能性ＲＮＡもゲノム上にコードされている

miRNAの発見、RNAi（ＲＮＡ干渉）の開発

(5)

遺伝子の構造（真核生物）

転写開始点プロモータエキソン転写終結点ポリＡ開始コドン _コドン終止

5

_‘_‘

3

_‘_‘ エキソンエキソンエキソンイントロンイントロンイントロン

(6)

タンパク質コード遺伝子の発見法

• 既知転写産物との類似性

– ＤＢ上の既知遺伝子（ＤＮＡ）で相同性検索 – ＤＢ上の既知タンパク質で相同性検索 – cDNAをゲノムＤＮＡ配列に「貼り付ける」

• 比較ゲノム

– 保存領域（synteny）は「重要」

• “ab initio” 遺伝子発見

– 統計的な情報を用いた遺伝子の確率モデル

(7)

タンパク質コード遺伝子の発見法

• 既知転写産物との類似性

• 比較

ゲノム

• “ab initio” 遺伝子発見

– 統計的な情報を用いた遺伝子の確率モデルアラインメントによる配列の比較動的計画法（ＤＰ） BLAST モデルによるゲノムＤＮＡの「局所検索」

(8)

タンパク質コード遺伝子の発見法

• 既知転写産物との類似性

• 比較ゲノム

– きわめて重要(QRNA, RNAz)

• “ab initio” 遺伝子発見

– 統計的な情報を用いた遺伝子の確率モデルアラインメントによる配列の比較動的計画法（ＤＰ） BLAST？？？？モデルによるゲノムＤＮＡの「局所検索」

非コードRNA

However, is it OK to define the “conserved region” by sequence similarities ?

(9)

ＲＮＡ配列情報解析の課題

• ゲノム配列からの既知ncRNA発見

– tRNAscan-SE, Snoscan, Infernal

• cDNA配列からのncRNA発見

– クラスタリング、二次構造予測（xxxfold）

• 比較ゲノム保存領域からのncＲＮＡ発見

– 保存領域抽出、ncRNA判定（QRNA, RNAz）

• 特定モチーフを持つncRNA発見

– 二次構造モチーフと特定配列。標的予測

(10)

配列の比較：2次元DP

G K F D E C G K R F D 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（L2）計算時間 O（L2）

(11)

通常のアライメント法

• 塩基配列の各位置が、進化の過程で、それぞれ独立に他の塩基への置換を起こすというモデルに基づいている。

(12)

二次構造をもつRNAの進化

• 塩基対をつくる塩基ペアは、塩基対を保つよ

うな塩基置換の仕方（共置換）をする。

• →離れた２点での塩基の進化は独立でない。

• 配列の相同性が低くなってくると従来のアライ

メント法はうまくいかなくなってくる。

(13)

二次構造を考慮したアラインメント

seq.1 seq.2 A G C A U C G A A C G G C A A C C G U G C U _U G A G C U C A G C A A A C U G G C U G C U U A G C U G seq.2 seq.1 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

(14)

二次構造を考慮したスコア

C A A U G C C U G G x x x seq.3 seq.1 seq.2 seq.3 seq.1 seq.2 seq.3 A A A G C C A U C G seq.1 seq.2 C U U U G A C G G C G C U G C A A C U G seq.3 C A G C A A A C U G seq.1 G C U G C U U A G C seq.2

(15)

あらゆるＲＮＡ配列情報解析の基礎

ＲＮＡ配列の比較

• 配列の文字列としての類似性

– ステム部分の塩基対類似性 – 非塩基対部分の配列類似性

• ＲＮＡの二次構造の類似性

– 二次構造が異なる → どう比較するのか？ – 二次構造が分からない→ どう比較するのか？

(16)

RNAの２次構造予測

• 自由エネルギー最小化（含：準最適構造）

– Nussinov & Jacobson (“Nussinov Algorithm, 1980) – Mathews, Turner & Zuker (MFOLD, 2000)

• 配列比較解析

– 相同RNA配列群が必要、結果が初期整列に依存 – Chiu and Kolodziejczak (1991)

(17)

10 ₂₀ ₃₀ ₄₀

Secondary Structure Prediction of RNA

gcaccggctaactccgtgccagcag

ccgcggtaatacggagggtgc

(18)

gcaccggctaactccgtgccagcag ccgcggtaatacggagggtgc 10 ₂₀ ₃₀ ₄₀ 10 20 30 40 gcaccggctaactccgtgccagcagccgcggtaatacggagggtgc

(19)

gcaccggctaactc

(20)

• M(i,j) : maximum # of base pairs in (x

_i

, … x

_j

)

– M(i,j) = M(i+1, j) – M(i,j) = M(i, j-1)

– M(i,j) = M(i+1, j-1) + 1

– M(i,j) = max (M(i,k)+M(k+1,j))

k

Nussinov アルゴリズム

j i+1 i j-1 i j j-1 i+1 j i i k k+1 j

(21)

確率文脈自由文法（SCFG）による

ＲＮＡ二次構造予測

Σ = {a, c, g, u}, (x,y = a|c|g|u) S = xS S = Sx S = xSy S = SS M(i,j) = M(i+1, j) M(i,j) = M(i, j-1) M(i,j) = M(i+1, j-1) + 1

M(i,j) = max (M(i,k)+M(k+1,j))

j i+1 i j-1 i j j-1 i+1 j i i k k+1 j k

(22)

SCFGのCYK アルゴリズム

γ(i,j) : maxmum probability of

(xi, … xj) is parsed by S

S = xS S = Sx S = xSy S = SS

(23)

ＲＮＡ二次構造予測の

計算複雑度

• M(i,j) = max (M(i,k)+M(k+1,j))

– メモリ: M(i,j) for all position i,j = L2 – 計算時間: Iterate for all i,j,k = L3

i k k+1 j

(24)

Turnerのエネルギーパラメーター

ヘアピンスタック _ヘアピンスタックマルチループヘアピンバルジインターナルループ

(25)

ＲＮＡ

配列比較

の課題

• ２本配列の比較 – 共通二次構造の推定とアラインメント – 局所アラインメント（検索） • 配列群のマルチプルアラインメント • 配列群の共通二次構造予測 • 二次構造付配列への構造アラインメント – 局所アラインメント（検索） • 二次構造への構造アラインメント – 局所アラインメント（二次構造モチーフ検索） • 配列クラスタリング • 特定ＲＮＡのモデル – 局所アラインメント（特定ＲＮＡ発見） • 比較ゲノム保存領域からの機能性ＲＮＡ発見 Marlet

(26)

共通２次構造予測

• Sankoff (1985)

– ２(N)本のRNAの折畳み。O(L3N_{) time, O(L}2N_)space

• Gorodkin, Heyer & Stormo (FOLDALIGN, 1997)

– ２本局所整列、分岐構造なし、塩基対の最大化、O(L4_{) time}

– 多重整列：トーナメント法＋ Greedy アルゴリズム

• Mathews & Turner (Dynalign, 2002)

– 自由エネルギー最小化＋配列比較解析 – ステム間距離をM以下 O(M3 _L3_{) time}

• Perriquet, Touzet & Dauchet (CARNAC, 2003)

(27)

２本のＲＮＡ配列からの

共通二次構造の計算

γ

_(i

₁

_,j

₁

_,i

₂

_,j

_2,

_{) : 4 次元のDP行列}

(# of non-terminal is constant)

γ(i₁,j₁,i₂,j₂) =max (γ(i₁,k₁,i₂,k₂)+γ(k₁+1,j₁,k₂+1,j₂) ) i₂ j₂ k₂ k₂+1 1 L₂ S_a Sb i₁ j1 1 L₁ k₁ k₁+1

S

k₁,k₂ X Y

メモリ：O(

L

4

)

計算時間：O(

L

6

)

(28)

長さの６乗の計算時間とは？

• 配列長が２倍になると６４倍の計算時間

• 配列長が１０倍になると１００万倍！！

• １分の１００万倍は約２年

• Sankoffアルゴリズムでは、１５０塩基の２

配列の共通二次構造の計算に１０分以上

かかります、、、

(29)

S

tem

C

andidate

A

ligner 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 gcaccggctaactccgtgccagc agccgcggtaatacggagggtgc 10 20 30 40 10 20 30 40

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

(32)

S

tem

C

andidate

A

ligner for

RNA

(33)

Decomposition of stem fragments

into stem components

position sequence distance complementary confidence score stacking energy

(34)

S

tem

C

andidate

A

ligner for

RNA

5’ and 3’ stem component (left SC and right SC) – Sort all SCs as a sequence by their positions

(35)

gcaccggctaactccgtgccagcagccgcggtaatacggagggtgc gcac cggctaactccgtgccagcagccgcggtaatacggagggtgc 10 ₂₀ ₃₀ ₄₀ 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 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 11 38 36 22 16 14 26 22 20 10 18 8 16 11 23 9 21 14 16 8 10 22 9 16 18 20 22 26 36 21 38 23 －－－－－－－－－－－－－－－－－ 10 20 30 40

(36)

S

tem

C

andidate

A

ligner for

RNA

(37)

Relations of two stem fragments

r r r-continous overlap ill-continous overlap no overlap parallel nested pseudoknot overlap contradict overlap

(38)

Left-right consistency

(39)

Left-right consistency

(40)

Dependencies in DP of SCSs

1-continous

(41)

(42)

(43)

Scarna web server

(44)

Scarna web server

(45)

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

ＲＮＡ配列の比較アルゴリズム

Aspergillus oryzae遺伝子発見パイプライン

様々なタイプの機能性非コードRNAがある

遺伝子の構造（真核生物）

5

5

3

3

タンパク質コード遺伝子の発見法

• 既知転写産物との類似性

• 比較ゲノム

• “ab initio” 遺伝子発見

タンパク質コード遺伝子の発見法

• 既知転写産物との類似性

• 比較

ゲノム

• “ab initio” 遺伝子発見

タンパク質コード遺伝子の発見法

• 既知転写産物との類似性

• 比較ゲノム

• “ab initio” 遺伝子発見

非コードRNA

ＲＮＡ配列情報解析の課題

• ゲノム配列からの既知ncRNA発見

• cDNA配列からのncRNA発見

• 比較ゲノム保存領域からのncＲＮＡ発見

• 特定モチーフを持つncRNA発見

配列の比較：2次元DP

通常のアライメント法

二次構造をもつRNAの進化

• 塩基対をつくる塩基ペアは、塩基対を保つよ

うな塩基置換の仕方（共置換）をする。

• →離れた２点での塩基の進化は独立でない。

• 配列の相同性が低くなってくると従来のアライ

メント法はうまくいかなくなってくる。

二次構造を考慮したアラインメント

二次構造を考慮したスコア

ＲＮＡ配列の比較

• 配列の文字列としての類似性

• ＲＮＡの二次構造の類似性

RNAの２次構造予測

• 自由エネルギー最小化（含：準最適構造）

• 配列比較解析

Secondary Structure Prediction of RNA

gcaccggctaactc

gcaccggctaactc

• M(i,j) : maximum # of base pairs in (x

, … x

)

Nussinov アルゴリズム

確率文脈自由文法（SCFG） による

ＲＮＡ二次構造予測

SCFGのCYK アルゴリズム

ＲＮＡ二次構造予測の

計算複雑度

• M(i,j) = max (M(i,k)+M(k+1,j))

Turnerのエネルギーパラメーター

ＲＮＡ

配列比較

の課題

共通２次構造予測

２本のＲＮＡ配列からの

共通二次構造の計算

γ

(i

,j

,i

,j

) : 4 次元のDP行列

(# of non-terminal is constant)

S

メモリ：O(

L

)

計算時間：O(

L

)

長さの６乗の計算時間とは？

• 配列長が２倍になると６４倍の計算時間

確率文脈自由文法（SCFG）による

_(i

_,j

_,i

_,j

_{) : 4 次元のDP行列}