Алгоритмы в биоинформатике, осень 2015: Множественные выравнивания и профили

  • Published on
    15-Apr-2017

  • View
    511

  • Download
    4

Embed Size (px)

Transcript

<ul><li><p> 2 </p><p>1. .1.</p><p>2.</p><p>3.</p><p>1.</p><p>2.</p><p>3.</p><p>4.</p><p>1.</p><p>2.</p><p>3.</p><p> . </p><p> . .</p><p>3-level Manhattan. .</p><p> HMM.</p><p> . .</p><p> . Forward-Backward.</p><p>HMM .</p><p> .</p><p>WPGMA UPGMA.</p><p>Neighbour-Joining.</p><p>6. .1.</p><p>2.</p><p>1.</p><p> .</p><p> .</p><p> .</p><p>Zuker folding algorithm.</p><p>2. .</p><p>7. .3. .</p><p>5. .</p><p>1. . .</p><p>4. - (). .</p><p>4. .</p><p>4. .1.</p><p>2.</p><p>-. -. </p><p> . --. </p><p>3. ???</p><p>2. . ClustalW.</p><p>3. .</p><p>???</p></li><li><p> 2- </p><p> 3- 3- .</p><p>A T _ G C G _A _ C G T _ AA T C A C _ A</p><p> : , </p></li><li><p> 3-</p></li><li><p>3-D </p><p>(i-1,j-1,k-1) (i-1,j,k-1)</p><p>(i-1,j-1,k) (i-1,j,k)</p><p>(i,j,k-1)</p><p>(i,j-1,k-1)</p><p>(i,j-1,k) (i,j,k)</p></li><li><p>si-1,j-1,k-1 + (vi, wj, uk) </p><p>si-1,j-1,k + (vi, wj, _ )</p><p>si-1,j,k-1 + (vi, _, uk) </p><p>si,j-1,k-1 + (_, wj, uk)</p><p>si-1,j,k + (vi, _ , _)</p><p>si,j-1,k + (_, wj, _) </p><p>si,j,k-1 + (_, _, uk)</p><p> si,j,k = max</p><p> (x, y, z) </p></li><li><p> 3- n, 7n3; O(n3)</p><p> k - (2k-1)(nk);O(2knk)</p></li><li><p>x: AC-GCGG-Cy: AC-GC-GAGz: GCCGC-GAG</p><p>:</p><p>x: ACGCGG-C;</p><p>y: ACGC-GAC;</p><p>x: AC-GCGG-C;</p><p>z: GCCGC-GAG;</p><p>y: AC-GCGAG</p><p>z: GCCGCGAG</p></li><li><p> 3 :</p><p>x: ACGCGG-C;</p><p>y: ACGC-GAC;</p><p>x: AC-GCGG-C;</p><p>z: GCCGC-GAG;</p><p>y: AC-GCGAG</p><p>z: GCCGCGAG</p></li><li><p>x GGGCACTGCAT</p><p>y GGTTACGTC--</p><p>z GGGAACTGCAG</p><p>w GGACGTACC--</p><p>v GGACCT-----</p><p>Alignment 1</p><p>Alignment 2</p></li><li><p>GTCTGAGTCAGC</p><p>GTC[TA]G[AC] - G[5X][6X]</p><p>x</p><p>y</p><p>z</p><p>w</p><p>v</p><p>GGGCACTGCAT</p><p>GGTTACGTC--</p><p>GGGAACTGCAG</p><p>GGACGTACC--</p><p>GGACCT-----</p><p>GGACACAGCAT - </p></li><li><p>1. </p><p>bk (i) = Ek (i)/ j Ek(j)</p><p>2. </p><p>bk (i) = (Ek(i) +1) / (j Ek(j)+ N)</p><p>3. </p><p>bk (i) = (Ek(i) +Aqi) / (j Ek(j)+ A)</p><p>4. </p><p>Ek(i) = Aj fkj P(ij)</p><p>5. </p><p>bk (i) = j Pk(ij) P(predk=j | alignment)</p></li><li><p>u1= ACGTACGTACGT</p><p>u2 = TTAATTAATTAA</p><p>u3 = ACTACTACTACT</p><p>u1= AC[GT]TAC[GT]TAC[GT]T</p><p>u2 = TTAATTAATTAA</p><p>k-1</p><p>k</p><p>uk = CCGGCCGGCCGG</p><p>uk = CCGGCCGGCCGG</p><p> k n O(n2k2)</p></li><li><p> ClustalW</p><p> .</p><p>1.) </p><p>2.) -</p><p>3.) -</p></li><li><p> 1: </p><p>identity</p><p>v1 v2 v3 v4</p><p>-</p><p>.17 -</p><p>.87 .28 -</p><p>.59 .33 .62 -</p><p>v1</p><p>v2</p><p>v3</p><p>v4</p><p>(.17 17 % )</p></li><li><p> 2: -</p><p>v1</p><p>v2</p><p>v3</p><p>v4</p><p>v1 v2 v3 v4</p><p>-</p><p>.17 -</p><p>.87 .28 -</p><p>.59 .33 .62 -</p><p>v1</p><p>v3</p><p>v4</p><p>v2</p><p> :v1,3 = (v1, v3)v1,3,4 = ((v1,3),v4)v1,2,3,4 = ((v1,3,4),v2)</p></li><li><p> 3: </p><p> 2 </p><p>.</p><p> - ,</p><p>FOS_RAT</p><p>FOS_MOUSE</p><p>FOS_CHICK</p><p>FOSB_MOUSE</p><p>FOSB_HUMAN</p><p>PEEMSVTS-LDLTGGLPEATTPESEEAFTLPLLNDPEPK-PSLEPVKNISNMELKAEPFD</p><p>PEEMSVAS-LDLTGGLPEASTPESEEAFTLPLLNDPEPK-PSLEPVKSISNVELKAEPFD</p><p>SEELAAATALDLG----APSPAAAEEAFALPLMTEAPPAVPPKEPSG--SGLELKAEPFD</p><p>PGPGPLAEVRDLPG-----STSAKEDGFGWLLPPPPPPP-----------------LPFQ</p><p>PGPGPLAEVRDLPG-----SAPAKEDGFSWLLPPPPPPP-----------------LPFQ</p><p>. . : ** . :.. *:.* * . * **:</p><p> .</p></li><li><p> :</p><p> (SP-Score)</p></li><li><p>AAAAAAAATATC</p></li><li><p>AAAAAAAATATC</p></li><li><p> (SP-Score)</p><p> s(ai, aj)</p><p> : s(a1,,ak) = i,j s (ai, aj)</p></li><li><p>: :</p><p>-( pA logpA + pC logpC + pG logpG + pT logpT)</p><p>A A A</p><p>A C C</p><p> 1 = -[1*log(1) + 0*log0 + 0*log0 +0*log0]=0</p><p> 2 = -[(1/4)*log(1/4) + (3/4)*log(3/4) + 0*log0 + 0*log0]= -[ (1/4)*(-2) + (3/4)*(-.415) ] = +0.811</p><p>A C G</p><p>A C T</p><p> 3 = -[(1/4)*log(1/4)+(1/4)*log(1/4)+(1/4)*log(1/4)+(1/4)*log(1/4)] = 4* -[(1/4)*(-2)] = +2.0</p><p> = 0 + 0.811 + 2.0 = +2.811</p></li></ul>

Recommended

View more >