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

  • Published on
    15-Apr-2017

  • View
    44

  • Download
    4

Embed Size (px)

Transcript

  • , - .

  • (4+1) x(4+1) .

    (20*+1)x(20*+1).

    gap .

    :

    si-1,j-1 + (vi, wj)

    si,j = max s i-1,j + (vi, -)

    s i,j-1 + (-, wj)

  • A

    A

    R

    N

    K

    5

    -

    -

    -

    R

    -2

    7

    -

    -

    N

    -1

    -1

    7

    -

    K

    -1

    3

    0

    6

    , R K ,

    .

    -1 -1 -2 +5 +7 +3 = 11

  • .

    , .

    , ,, (vi , wj), .

  • PAM

    BLOSUM

  • PAM

    Point Accepted Mutation (Dayhoff et al.)

    1 PAM = PAM1 = 1% .

    , 100 PAM ,

  • PAMX

    PAMx = PAM1

    PAM250 = PAM1

    PAM250 :

    Ala

    Arg

    Asn

    Asp

    Cys

    Gln

    ...

    Trp

    Tyr

    Val

    A

    R

    N

    D

    C

    Q

    Ala

    A

    13

    3

    4

    5

    2

    3

    Arg

    R

    6

    17

    4

    4

    1

    5

    Asn

    N

    9

    4

    6

    8

    1

    5

    Asp

    D

    9

    3

    7

    11

    1

    6

    Cys

    C

    5

    2

    2

    1

    52

    1

    Gln

    Q

    8

    5

    5

    7

    1

    10

    Glu

    E

    9

    3

    6

    10

    1

    7

    Gly

    G

    12

    2

    4

    5

    2

    3

    His

    H

    6

    6

    6

    6

    2

    7

    Ile

    I

    8

    3

    3

    3

    2

    2

    Leu

    L

    6

    2

    2

    2

    1

    3

    Lys ...

    K ...

    7 ...

    9

    5

    5

    1

    5

    W

    Y

    V

    0

    1

    7

    2

    1

    4

    0

    2

    4

    0

    1

    4

    0

    3

    4

    0

    1

    4

    0

    1

    4

    0

    1

    4

    1

    3

    5

    0

    2

    4

    1

    2

    15

    0

    1

    10

    x

    250

  • BLOSUM

    Blocks Substitution Matrix

    BLOSUM62 min 62% identity

  • BLOSUM50

  • 2 ( (3+1)(3+1)).

    A R N K

    A 5

    -

    -

    -2

    7

    -

    -1

    -1

    7

    -1

    3

    0

    : RN

    K - - - 6

  • --T-CC-C-AGT-TATGT-CAGGGGACACGA-GCATGCAGA-GAC| || | || | | | ||| || | | | | |||| |

    AATTGCCGCC-GTCGT-T-TTCAG----CA-GTTATGT-CAGAT--C

    tccCAGTTATGTCAGgggacacgagcatgcagagac

    ||||||||||||

    aattgccgccgtcgttttcagCAGTTATGTCAGatc

  • (0,0) (n,m) .

    (i,j) (i, j).

  • free ride

    Yeah, a free ride!

    (0,0)

  • (-)

    si,j

    .

    :0

    si,j = max si-1,j-1 + (vi, wj)s i-1,j + (vi, -)s i,j-1 + (-, wj)

    .

  • 2 .

  • /: .

    /:

    - ,

    -2 ,

    -3 , ..

  • gap

    , k , k :

  • -- 1 indel

    --2 2 indels

    --3 3 indels, etc.

  • .

    O(n3)

  • The 3-leveled Manhattan Grid

  • 3-leveled Manhattan

  • :

    ( ) (-r- s)

    (-s)

  • 3-

    si,j =

    max

    si,j =

    max

    si,j =

    max

    s i-1,j -

    s i-1,j (+)

    s i,j-1 -

    s i,j-1 (+)

    si-1,j-1 + (vi, wj)

    s i,j

    s i,j

    w ()

    w ():

    v ()

    v ():

    :

    :

  • -d -p-ld (p d ) l.

  • w1,1

    w2,1

    w1,2

    wi,j

    wi,j+1

    wi+1,j

    wi+1,j+1wn-1,m

    O(nm)wn,m-1 wn,m

    O(nm)

  • -

    0. , .

    1. Sdown(xij) Sup(xij).

    2. MAX(Sdown(xij) + Sup(xij)) j .. , .

    3. 2 , .

    i

    j

    4.

    T=C*n2+C*n2/2+C*n2/4+=C*n2(1+1/2+1/4+1/8+)=2C*n2

Recommended

View more >