バイオメトリクス授業資料 iwatawiki lec09 s

(1)

060310391 0560565

9 2016/12/5 13:00-14:45

@1 - 4

1

Fig. 4. Convergent evolu0on of feeding morphology and color among East African cichlid ﬁshes. Species from Lake Tanganyika are in the leA column; those from Lake Malawi are to the right. Each of the illustrated ﬁshes from Lake Malawi are more closely related to one another than to any species in Lake Tanganyika.

h/p://www.pnas.org/ Albertson et al. (2003)

1996 ²

• 

3

•  2 ^DNA ^RNA

•  ^DNA ^RNA

4

(2)

A-TGTAAACGCTA

AGTGTAAT-GCTA

ATGTAAACGCTA

AGTGTAATGCTA

ATGTAAACGCTA

AGTGTAATGCTA

…

5

…

-

3 …

①

②

match 1 (mismatch) −1 -2

① 7×1+5×(-1)=2 ② 10×1+1×(-1)+2×(-2)=5

⁵

• – 

Needleman-Wunsch

• – 

Smith-Waterman

6

Needleman-Wunsch algorithm

Needleman and Wunsch (1970) J Mol Biol 48:443

- A T G T C

- 0 -2 -4 -6 -8 -10

A -2

G -4

T -6

A -8

C -10

match = 1 mismatch = -1 gap = -2

7

Needleman-Wunsch algorithm

A T G T C

0 -2 -4 -6 -8 -10

A -2 1 -1 -3 -5 -7

G -4

T -6

A -8

C -10

0 -2

-2 -4

0 -2

-2 -4

0 -2

-2 1

3

(a)

(b)

(c)

(a) (c) gap (b) match mismatch 8

(3)

Needleman-Wunsch algorithm

- A T G T C

- 0 -2 -4 -6 -8 -10

A -2 1 -1 -3 -5 -7

G -4 -1 0 0 -2 -4

T -6 -3 0 -1 1 -1

A -8 -5 -2 -1 -1 0

C -10 -7 -4 -3 -2 0

9

Needleman-Wunsch algorithm

- A T G T C

- 0 -2 -4 -6 -8 -10

A -2 1 -1 -3 -5 -7

G -4 -1 0 0 -2 -4

T -6 -3 0 -1 1 -1

A -8 -5 -2 -1 -1 0

C -10 -7 -4 -1 -2 0

ATGT-C

A-GTAC

₁

2 10

ATGT-C

A-GTAC

4 × 1 + 0 × (-1) + 2 × (-2) = 0

ATGTC

AGTAC

2 × 1 + 3 × (-1) + 0 × (-2) = -1

ATGT-C

AG-TAC

3 × 1 + 1 × (-1) + 2 × (-2) = -2

11

Smith-Waterman algorithm

Smith and Waterman (1981) J Mol Biol 147:195

- A T G T C

- 0 0 0 0 0 0

A 0 ¹ ⁰ ⁰ ⁰ ⁰

G 0 ⁰ ⁰ ¹ ⁰ ⁰

T 0 ⁰ ⁰ ⁰ ² ¹

C 0 ⁰ ⁰ ⁰ ¹ ³

A 0 ⁰ ⁰ ⁰ ⁰ ²

GTC

1.  ⁰

2.  ⁰

3.  0

4.  ⁰ ₁₂

(4)

•  2 3

•  Needleman-Wunsch

m O(n

^m

)

•  Clustal

13

Clustal

Thompson et al. (1994) Nuc Acid Res 22: 4673

2

NJ

root

NJ 1.  Hbb_Human vs. Hbb_Horse 2.  Hba_Human vs. Hba_Horse 3.  (1) vs. (2)

4.  (3) vs. Myg_Phyca :

2

14

Thompson et al. (1994) Nuc Acid Res 22: 4673 ¹⁵

(phylogene_cs)

•  ^DNA

RNA

• 

2005

16

(5)

• 

–  UPGMA

• 

– 

• 

– 

• 

–  MCMC

17

•  ²

• 

A T G A C G A T A

C G G C C A C

A T G T C G A C C

G T

A C

C C

G

A

18

Jukes-Cantor model

q

_t

^q

_t+1

q

: [ ]/[ ]

A T G C

A T G C 1 − λ

λ/3^λ/3 λ/3

h/p://www.veritastk.co.jp/kamon/pdf/kamon27/popu27.pdf

q_{t +1}≅ (1 −λ)²q_t+ 2(1 −λ)(λ/ 3)(1 − q_t)

≅ (1 − 2λ)q_t+²^λ 3 ^{(1 − q}^t⁾ q_{t +1}− q_t=²^λ

3 ⁻ 8_λ

3^q^t

dq/dt

dq dt⁼

2_λ 3 ⁻

8_λ 3^q

q =1 −³

4

₍

1 − exp(−8λt 3)

₎

d

dxy + P(x)y = Q(x)

⇒ y = exp(− Pdx_∫ )₍_∫Qexp(_∫Pdx) + C₎

2λt = −³ 4^{ln 1−}

4 3^{(1− q)}

$

% & ^'

( ) d =−³ 4^{ln 1}⁻

4 3^p

#

$ % ^& ' (

d=2λt (

p = 1−q ¹⁹

C

t = 0 q=1

Kimura’s 2-parameters model

A T

G C

Jukes-Cantor model

A T

G C

Kimura’s 2-parameters model

→ α

β

P, Q

h/p://www.veritastk.co.jp/kamon/pdf/kamon27/popu27.pdf P=¹

4₍1 − 2exp(−4(α + β)t) + exp(−8βt)₎ Q=¹

2(1 − exp(−8βt))

d≡ 2λt = 2αt + 4βt

= −¹

2ln(1− 2P − Q) −¹ 4^{ln(1− 2Q)}

20

p = P + Q

(6)

UPGMA

(Unweighted Pair Group Method with Arithme_c mean)

• 

•  ^{A B} ^AB

→

• 

21

Neighbor Joining method

Saitou and Nei (1987) Mol Biol Evol 4: 406

• 

2005

Saitou and Nei (1987) 22

Saitou and Nei (1987)

internal branch

S_O= L_iX= ¹ N₋₁

^∑

_{i< j}^D^ij

i=1 N

∑

^OUT _N-1 ^OTU ^{OTU N-1} _N-1

D_ij: OTU i j

L_ab: ab

LXY= ¹

2(N− 2) ^(D^1k^{+ D}^2k⁾− (N − 2)(L_1X+ L_2X)− 2 LiY i_{= 3}

N

∑

k_{= 3} N

$

∑

% &

' ( ) Fig.2a

XY Fig.2b

1 OTU1, 2 OTU

2 3 XY

S₁₂= L_XY+ (L_1X+ L_2X) + L_iY

i= 3 N

∑

= ¹

2(N− 2) ^(D^1k^{+ D}^2k^{) +} 1

2^(L^1X^{+ L}^2X^{) +} N− 3 N− 2_{i= 3}^L^iY

N

∑

k = 3 N

∑

⁼_2(N¹_{− 2)} ^(D1k^{+ D}2k^{) +}

1 2^D¹²⁺

1 N− 23≤i< j^D^ij

∑

k = 3 N

∑

2OTU ²³

1.  2OTU

2.  ^2OTU ¹ ^OTU

OTU1 2 OTU(1-2)

OTU :

D

_{(1− 2) j}

= (D

_{1 j}

+ D

_{2 j}

) /2

3.  1,2 OTU ³

4. L

1X

= (D

12

+ D

1Z

− D

2Z

^{) /2}

L

2X

= (D

12

+ D

2Z

− D

1Z

^{) /2}

D_1Z ₌ D_1i

i= 3

∑

N ^/(N^{− 2)}

D2Z ⁼ _{i= 3}^D2i

∑

N ^/(N^{− 2)} 24

(7)

A

C

B ^D

(unrooted tree)

A

A B C D

(rooted tree)

?

25

• 

26

A A C C C

T → A

1

2

1

2 T → A

T → A

most parsimonious tree ²⁷

1 2 3 4 5

Out A C T A C

A T C T A T

B T A T G C

C T C G G C

1 2 3 4 5

Out 0 0 0 0 0

A 1 0 0 0 1

B 1 1 0 1 0

C 1 0 1 1 0

Out A B C

h/p://www.gwu.edu/~clade/faculty/lipscomb/Cladis_cs.pdf

1

5 (0,1,1,0)

28

(8)

• 

29

S_a ^S^b

S_d S_c S₀

S₁ t₁

t₂ t_a ^t^b

t_d

L= _π_{S 0}P_{S 0S1}(t1)PS1Sa(ta)PS1Sb(tb)PS 0S 2(t2)PS 2Sc(tc)PS 2Sd(td)

S 2

∑

S1

∑

S 0

∑

1

S₀, S₁, S₂ {A, T, C, G}

4³

S_a, S_b, S_c {A, T, C, G} 1

S₂

π_X X 1/4

PXY(t) t X Y

n

L = πS0j^PS0jS1j^(t¹^)PS1jSaj^(ta^)PS1jSbj^(tb^)PS0jS2j^(t²^)PS2jScj^(tc^)PS2jSdj^(td⁾ S2j

∑

S1j

∑

S0j

∑

j n

∏

³⁰

h/p://www.stat.wisc.edu/~larget/phylogeny/Holmes-Sta_s_calScience-2003.pdf 49% CONS-CPZ,O4,N2,B34

monophyle_c group

31

0123456789 AATAATCACA GGCAATTATG GGTGGCCTCG AACGATCACG A

B C D

3229168977 ATTAACCAAA ACCGGTTGAA GTTGGCCGTT GCCGACCGAA

1

9831664065 ACAACCAACT GTAGTTAGTT GCGGCCGGCC GCGACCAACT

2

:

32

(9)

h/p://www.stat.wisc.edu/~larget/phylogeny/Holmes-Sta_s_calScience-2003.pdf

Phylip

33

9

1.  ACTG CTAG Needleman & Wunsch

match = 1, mismatch = -1, gap = -2

2.  Jukes-Cantor ⁴

d

3.  ^A, B

1 2 3 4

AATAATCA GGTAATCT GGTAGTCT AGCAATCA

1 2 3 4

A

1 2 3 4

B

34

PDF MS Word

e

[email protected]

2016 12 12

35

バイオメトリクス授業資料 iwatawiki lec09 s

060310391 0560565

9

2016/12/5 13:00-14:45

@1 - 4

•

•

•

•

•

•

•

•

•

• 2 DNA RNA

• DNA RNA

A-TGTAAACGCTA

AGTGTAAT-GCTA

ATGTAAACGCTA

AGTGTAATGCTA

ATGTAAACGCTA

AGTGTAATGCTA

•

–

Needleman-Wunsch

•

–

Smith-Waterman

Needleman-Wunsch algorithm

Needleman-Wunsch algorithm

Needleman-Wunsch algorithm

Needleman-Wunsch algorithm

ATGT-C

A-GTAC

ATGT-C

A-GTAC

ATGTC

AGTAC

ATGT-C

AG-TAC

Smith-Waterman algorithm

GTC

GTC

• 2 3

• Needleman-Wunsch

m O(n

)

• Clustal

Clustal

(phylogene_cs)

• DNA

RNA

•

• 2

•

Jukes-Cantor model

q

q

q

(

)

Kimura’s 2-parameters model

Jukes-Cantor model

Kimura’s 2-parameters model

UPGMA

(Unweighted Pair Group Method with Arithme_c mean)

Neighbor Joining method

Saitou and Nei (1987) Mol Biol Evol 4: 406

∑

∑

∑

∑

∑

∑

∑

∑

∑

1. 2OTU

2. 2OTU 1 OTU

OTU1 2 OTU(1-2)

• 

• 

• 

• 

• 

• 

• 

• 

• 

•  2 ^DNA ^RNA

•  ^DNA ^RNA

• 

– 

• 

– 

•  2 3

•  Needleman-Wunsch

•  Clustal

•  ^DNA

• 

•  ²

• 

^q

₍

₎

^∑

1.  2OTU

2.  ^2OTU ¹ ^OTU

3.  1,2 OTU ³

4. 

^{) /2}

^{) /2}

B ^D

• 

• 