Алгоритмы в биоинформатике, осень 2015: Выравнивание последовательностей II

  • Published on
    15-Apr-2017

  • View
    633

  • Download
    5

Embed Size (px)

Transcript

<ul><li><p>Identity</p><p>AC C TG A G AG</p><p>AC G TG G C AG</p><p>mismatchindel</p><p>Identity = 70%</p></li><li><p> (4+1) x(4+1) .</p><p> (20*+1)x(20*+1).</p><p> gap .</p><p> :</p><p>si-1,j-1 + (vi, wj)</p><p>si,j = max s i-1,j + (vi, -)</p><p>s i,j-1 + (-, wj)</p></li><li><p> .</p><p> , .</p><p> , ,, (vi , wj), .</p></li><li><p>A</p><p>A</p><p>R</p><p>N</p><p>K</p><p>5</p><p>-</p><p>-</p><p>-</p><p>R</p><p>-2</p><p>7</p><p>-</p><p>-</p><p>N</p><p>-1</p><p>-1</p><p>7</p><p>-</p><p>K</p><p>-1</p><p>3</p><p>0</p><p>6</p><p> , R K , </p><p> .</p><p>-1 -1 -2 +5 +7 +3 = 11</p></li><li><p> , - .</p></li><li><p> PAM</p><p> BLOSUM</p></li><li><p>PAM</p><p> Point Accepted Mutation (Dayhoff et al.)</p><p> 1 PAM = PAM1 = 1% .</p><p> , 100 PAM , </p></li><li><p>PAMX</p><p> PAMx = PAM1</p><p> PAM250 = PAM1</p><p> PAM250 :</p><p>Ala</p><p>Arg</p><p>Asn</p><p>Asp</p><p>Cys</p><p>Gln</p><p>...</p><p>Trp</p><p>Tyr</p><p>Val</p><p>A</p><p>R</p><p>N</p><p>D</p><p>C</p><p>Q</p><p>Ala</p><p>A</p><p>13</p><p>3</p><p>4</p><p>5</p><p>2</p><p>3</p><p>Arg</p><p>R</p><p>6</p><p>17</p><p>4</p><p>4</p><p>1</p><p>5</p><p>Asn</p><p>N</p><p>9</p><p>4</p><p>6</p><p>8</p><p>1</p><p>5</p><p>Asp</p><p>D</p><p>9</p><p>3</p><p>7</p><p>11</p><p>1</p><p>6</p><p>Cys</p><p>C</p><p>5</p><p>2</p><p>2</p><p>1</p><p>52</p><p>1</p><p>Gln</p><p>Q</p><p>8</p><p>5</p><p>5</p><p>7</p><p>1</p><p>10</p><p>Glu</p><p>E</p><p>9</p><p>3</p><p>6</p><p>10</p><p>1</p><p>7</p><p>Gly</p><p>G</p><p>12</p><p>2</p><p>4</p><p>5</p><p>2</p><p>3</p><p>His</p><p>H</p><p>6</p><p>6</p><p>6</p><p>6</p><p>2</p><p>7</p><p>Ile</p><p>I</p><p>8</p><p>3</p><p>3</p><p>3</p><p>2</p><p>2</p><p>Leu</p><p>L</p><p>6</p><p>2</p><p>2</p><p>2</p><p>1</p><p>3</p><p>Lys ...</p><p>K ...</p><p>7 ...</p><p>9</p><p>5</p><p>5</p><p>1</p><p>5</p><p>W</p><p>Y</p><p>V</p><p>0</p><p>1</p><p>7</p><p>2</p><p>1</p><p>4</p><p>0</p><p>2</p><p>4</p><p>0</p><p>1</p><p>4</p><p>0</p><p>3</p><p>4</p><p>0</p><p>1</p><p>4</p><p>0</p><p>1</p><p>4</p><p>0</p><p>1</p><p>4</p><p>1</p><p>3</p><p>5</p><p>0</p><p>2</p><p>4</p><p>1</p><p>2</p><p>15</p><p>0</p><p>1</p><p>10</p><p>x</p><p>250</p></li><li><p>BLOSUM</p><p> Blocks Substitution Matrix</p><p> BLOSUM62 min 62% identity</p></li><li><p> BLOSUM50</p></li><li><p> (+)4 </p><p> 2 ( (3+1)(3+1)).</p><p>A R N K</p><p>A 5</p><p>-</p><p>-</p><p>-2</p><p>7</p><p>-</p><p>-1</p><p>-1</p><p>7</p><p>-1</p><p>3</p><p>0</p><p>: RN</p><p>K - - - 6</p></li><li><p>--T-CC-C-AGT-TATGT-CAGGGGACACGA-GCATGCAGA-GAC| || | || | | | ||| || | | | | |||| |</p><p>AATTGCCGCC-GTCGT-T-TTCAG----CA-GTTATGT-CAGAT--C</p><p>tccCAGTTATGTCAGgggacacgagcatgcagagac</p><p>||||||||||||</p><p>aattgccgccgtcgttttcagCAGTTATGTCAGatc</p></li><li><p> (0,0) (n,m) .</p><p> (i,j) (i, j).</p></li><li><p> free ride</p><p>Yeah, a free ride!</p><p>(0,0)</p></li><li><p> Smith - Waterman</p><p> si,j .</p><p>:0</p><p>si,j = max si-1,j-1 + (vi, wj)s i-1,j + (vi, -)s i,j-1 + (-, wj)</p><p>.</p></li><li><p> (+)4 </p><p> 2 .</p></li><li><p> /: .</p><p> /:</p><p> - ,</p><p> -2 ,</p><p> -3 , ..</p></li><li><p> gap</p><p> , k , k :</p></li><li><p> -- 1 indel</p><p> --2 2 indels</p><p> --3 3 indels, etc.</p></li><li><p> .</p><p> O(n3)</p></li><li><p>The 3-leveled Manhattan Grid</p></li><li><p>3-leveled Manhattan</p></li><li><p> :</p><p> ( ) (-r- s)</p><p> (-s)</p></li><li><p> 3- </p><p>si,j =</p><p>max</p><p>si,j =</p><p>max</p><p>si,j =</p><p>max</p><p>s i-1,j - </p><p>s i-1,j (+)</p><p>s i,j-1 - </p><p>s i,j-1 (+)</p><p>si-1,j-1 + (vi, wj)</p><p>s i,j</p><p>s i,j</p><p> w ()</p><p> w (): </p><p> v ()</p><p> v (): </p><p> : </p><p> : </p></li><li><p> 4 </p><p> -d -p-ld (p d ) l.</p></li><li><p>w1,1</p><p>w2,1</p><p>w1,2</p><p>wi,j</p><p>wi,j+1</p><p>wi+1,j</p><p>wi+1,j+1wn-1,m</p><p> O(nm)wn,m-1 wn,m</p><p> O(nm)</p></li><li><p> -(Miller-Myers)</p><p>0. , .</p><p>1. Sdown(xij) Sup(xij).</p><p>2. MAX(Sdown(xij) + Sup(xij)) j .. , .</p><p>3. 2 , .</p><p>i</p><p>j</p><p>4. </p><p>T=C*n2+C*n2/2+C*n2/4+=C*n2(1+1/2+1/4+1/8+)=2C*n2</p></li></ul>

Recommended

View more >