春プロ勉強会14.pages

Size: px

Start display at page:

Download "春プロ勉強会14.pages"

わんどあかさか
5 years ago
Views:

1 February 2-25, RNA Spring Project Basic Theories for Bioinformatics Lecture Note I Motomu MATSUI Institute for Advanced Biosciences Keio University, Japan qm at sfc.keio.ac.jp

2 Basic Theories for Bioinformatics Lecture Note I by Motomu MATSUI 203/0/20 ver /02/0 ver /02/08 ver /02/4 ver. π Copyright by Motomu MATSUI

3 LECTURE -Introduction- LECTURE 2 -Clustering- LECTURE 3 -Spectral clustering- LECTURE 4 -Statistics- LECTURE 5 -Phylogenetics-

4 LECTURE 6 -Spectral Phylogenetic Analysis-

5 Nothing in Biology Makes Sense Except in the Light of Evolution - Theodosius Dobzhansky (900-75) a. b. a. b. c. E-value...BLAST a. b. c.

6 google tχ... [ ]. (2007) R,. 2. Rui Xu and Donald C. Wunsch II (2009) CLUSTERING, IEEE. 3. (966),. [ ] 4. (2003) R,. 5. Derek A. Roff (20),. [ ] 6. (988),. 7. and Sudhir Kumar (2006),.

7 8. Ziheng Yang (2006),. 9. (997),. 0. Ian Korf, Mark Yandell and Joseph Bedell (2003) BLAST, O REILLY.. David W. Mount (2004) Bioinformatics, Cold Spring Harbor Laboratory Press. [ ] 2. Jianbo Shi and Jitendra Malik (2000) Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), Chris Ding, Chris H. Q. Ding, Xiaofeng He, Hongyuan Zha, Ming Gu, Horst Simon (200) A Min-max Cut Algorithm for Graph Partitioning and Data Clustering, In Proceedings of the first IEEE International Conference on Data Mining (pp.07-4). Washington, DC, USA: IEEE Computer Society. 4. Motomu Matsui, Masaru Tomita, Akio Kanai (203) Comprehensive Computational Analysis of Bacterial CRP/FNR Superfamily and its Target Motifs Reveals Stepwise Evolution of Transcriptional Networks, Genome Biol. Evol. 5(2), Hirotsugu Akaike (973) Information theory and an extention of the maximum likelihood principle, Proceedings of the 2nd International Symposium on Information Theory, Petrov, B. N., and Caski, F. (eds.), Akadimiai Kiado, Budapest, Newman, MEJ (2006) Modularity and community structure in networks. PNAS 03(23), G Palla, I Derényi, I Farkas, and T Vicsek (2005) Uncovering the overlapping community structure of complex networks in nature and society: Nature 435, Pellegrini M, Marcotte EM, Thompson MJ, Eisenberg D, Yeates TO (999) Assigning protein functions by comparative genome analysis: protein phylogenetic profiles. PNAS 96, Paul Erdös and Alfred Rényi (970) On a new low of large numbers. J. Anal. Math 22, Samuel Karlin and Stephen F. Altschul (990) Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes. PNAS 87, Richard Arratia, Louis Gardon and Michael Waterman (986) An extreme value theory for sequence matching. Anal. Stat., 4,

8 (clustering)(classification) [Classification] ( ) [Clustering] Fig.-Classification Clustering ( ) ( )

9 2.2 クラスタリング手法の分類クラスタリング手法には様々なものがありますが大まかには以下のように分類する事ができます (もちろん複数の分類にまたがるような手法もたくさんあります例えば Newman法は大域アプローチでしたが局所アプローチに立った改良もされています ) ① ボトムアップ vs トップダウン似ているもの同士を結合してクラスターを形成する作業を再帰的に繰り返すことで最終的には一つのクラスターまでまとめあげる事ができますこの方法をボトムアップアプローチと言います逆に全体をまず一つのクラスターと考えそれを複数に分割する事でサブクラスターをいくつか得る方法をトップダウンアプローチと言います [ボトムアップ] 階層クラスタリング Markov Cluster Algorithm (MCL) K-クリーク法 [トップダウン] K-meansとその派生スペクトラルクラスタリング混合分布モデル Fig.2-Bottom-up, Top-downアプローチの比較 ② 大域 vs 局所要素の集合全体を対象としてクラスタリングを行うのが大域アプローチです要素数が限られている場合はこれに属する方法のいずれかを行うべきでしょう一方で解析対象が大きすぎる場合は個別の要素に着目してその周辺の要素のまとまり方からクラスターを決定する近似的手法が採られますそれを局所アプローチと言います [大域] 階層クラスタリング K-meansとその派生スペクトラルクラスタリング [局所] 以下の二つを始めネットワーク理論に基く多くの方法は局所アプローチに属します K-クリーク法 MCL Fig.3-Local, Globalアプローチの比較 9

10 vs [] Fuzzy c-means [] K-means * f g Fig.4-Hard, Soft f g (norm) f : e f = e f e f2 e fn g : e g = e g e g2 e gn Fig.5-

11 (L norm) d fg = c e fc e gc (L2 norm) d fg = c (e fc e gc ) 2 Σ dfg=-rfg rfg rfg 2 absolute/squared correlation egc egc d fg = (e f e g ) t (e f e g ) r gf = c (e fc e f )(e gc e g ) c (e fc e f ) 2 c (e gc e g ) 2 Fig.6-

12 cos( )= c e fce gc c e2 fc c e2 gc * X Y sim(x, Y )= X X Y Y (Mutual information; MI) X Y H(X) X H(X,Y) X Y H(X) X=iPi MI(X, Y )=H(X)+H(Y ) H(X, Y ) H(X) = i P i log P i 0/

13 2.2 Tab.- e.g. (K)... overfitting ()( )

14 (UPGMA)( UPGMA ) ( ) ( ) (UPGMA) Fig.7-

15 K-means K-means Fig.8 Kernel K-means K-means Kernel Kernel K-means K-means Kernel x-means KK-means AIC Fussy c-means K-means K Fig.8-K-means.K( ) 2. ( ) ,36.

16 (MCL) K-means Web MCL2000 Fig.9-MCL ( ) MCL Newman Newman 2.5Q K- K-K K- 3.

17 A A... A C x x2... xk C x2 x22... x2k C xk xk2... xkk C, C2,..., Ck K A, A2,..., Ak K xp,q p=qp q TRUE FALSE Predicted True TP FP (α error) PPV Predicted False FN (β error) TN NPV Sensitivity Specificity (Sensitivity) (Specificity)(Accuracy) -Specificity xsensitivity y ROC Sensitivity = Specif icity = TP TP + FN TN TN + FP

18 P ositive predictive value = N egative predictive value = Accuracy = TP TP + FP TN TN + FN TP + TN TP + TN + FP + FN (entropy)(purity) Ei Pi i Ci entropy = E i = purity = K h= P i = max h K i= K i= = N Ci N E i Ci N P i K i= max h C i A h P (A h C i ) log P (A h C i ) C i A h C i

19 Fig.0-/ Newman p q epq ai 2 Q Q = i (e ii a 2 i ) (AIC) (BIC) AIC = 2lnL +2k BIC = 2lnL +2kln(n) Ln k

20 Fig.- (A) G W (B) A,B a b Fig. sim(a, b) sim(p, r) =0.6

21 ABW(A,B) W (A, B) = sim(a, b) a A,b B Fig. W (A, B) = sim(a, b) AW(A) a A,b B = sim(p, s)+ sim(r, t) =0.3 W (A) =W (A, A) d A = W (A)+W (A, B) da G A,B Mcut Ncut Mcut = Ncut = W (A, B) + W (A) W (A, B) + d A W (A, B) W (B) W (A, B) d B Mcut, Ncut McutNcutA B Mcut Ncut

22 Ncut 3.2 Ncut Mcut Ncut W,Dq3.3 W D q OK q ; qa GA -b GB p q r s t u z X W... D = diag(we) q... q =(a, a, a, b, b, b) W (A, B) Ncut = + d A =... =... =... = qt (D W )q q t Dq G (N N ) a -b N W (A, B) d B z = D 2 q X = E D 2 WD 2

23 Ncut Ncut = zt Xz z t z Ncut = zt Xz z t z R X (z) = zt Xz z t z RX(z) X 2... n z,z 2,..., z n = R X (z ) R X (z 2 )... R X (z n )= n

24 . G W 2. X X = E D 2 WD 2 3. X (, ) λ2 (Fielder )z2 (Fielder ) ( ) 4. q q = D 2 z q( a) G A ( -b) GB ( ) (K-means MCL) ( ) ()

25 & & Fig.2- ( ) Fig.2a,b θ a,b a = a a 2 b = b b 2

26 ka = ka ka 2 a ± b = a ± b a 2 ± b 2 a() a a = a 2 + a2 2 a b = a b + a 2 b 2 ( ) (a,b) ( ) a,bθ Fig.3- a b θ c

27 c 2 =(bsin ) 2 +(a b cos ) 2 = b 2 sin 2 + a 2 2ab cos + b 2 cos 2 = b 2 (sin 2 + b 2 cos 2 )+a 2 2ab cos = a 2 + b 2 2ab cos a,b,c a, b a = a a 2 b = b b 2 a = a 2 + a2 2 b = b 2 + b2 2 c = b a = (b a ) 2 +(b 2 a 2 ) 2 cosθ c 2 = a 2 + b 2 2 a b cos cos = a b + a 2 b 2 a 2 + a2 2 b 2 + b2 2 a b cos = a b a b

28 θ a b = a b + a 2 b 2 = a b cos Fig.4- cosθ=0 0 0 ( cos sin )

29 ax + by = X cx + dy = Y x = ad bc (dx by ) y = ad bc (ay cx) (ad - bc 0 ) a c b d x y = X Y ( ) ( ) ( ) 4 x y = ad bc d c b a X Y A = a b c d

30 A x y = X Y A = ad bc d c b a x y = A X Y p = q p = q A A - AA = a b c d = ad bc = 0 0 ad bc d c ad bc ab ab cd cd ad bc b a EA E E = 0 0

31 AE = a b c d = a b c d 0 0 E E ( ) E A EA - A A - A A A E x y x y x y x y = X Y = A X Y = A X Y = A X Y. E N n I( ) ( ) E n = O O N

32 2. A - A X A A - A - A ( A =0 ) 3. A A AX = XA = E A = a b c d A (det(a) ) A = ad bc A - A = A A - A 0 4. A t A d c b a A = a b c d e f g h i A A t t A t = a d g b e h c f i

33 5. ( ) A = a b c A = A x = (2, 0) t Ax = = 2 2 Fig.5-

34 ( (,0) (0,)) (2,0) (2,0) x(2,0)a x (2,2) p q (x-y=0 x+3y=0 ) p = (, ) 2 q = (3, ) 0 x p5 q9 x+3y=0(3,-)a A 3 = = 5 5 x+3y=0 q5 x+3y=0 x-y=0 Ax = x x x+3y=0 x-y=0 λ (5 9) λ x A p q p q λ xp q (A E)x =0 x=0 x 0 X=(A-λE) X -

35 x 0 X - λ λ x x=(x,x2) λ=5 λ= Xx =0 X Xx =0 x =0 A E = =0 =0 (6 )(8 ) 3=0 ( 5)( 9) = x =0 x =0 x +3x 2 =0 =5, 9

36 A Fig.5A λ Ax A Fig.5 3. p,q 2. 3.(,0) (0,) x =0 x =0 x x 2 =0 Ax = x. p,q ( )

37 Fig.6-(3- ). V E G=(V,E)V(note, ) E (edge, )Fig.6 V( ) E (-) 2. Vx,y {x,y} Ex y x~y x y 3. G=(V,E)x E xdeg Fig E {{x, y} ; x, y V,x = y} deg G (x) = {y V ; y x}

38 G=(V,E) G =(V,E ) f: V V x y f(x) f(y) G=(V,E) G =(V,E ) g = g f Fig Fig.7- SNS

39 5. G=(V,E) a xy = if x y 0 if x y A=(axy) G=(V,E) G=(V,E) V={,2,3,4,5,6} E2={{,2},{,3},{,4},{2,3},{3,5},{4,5},{4,6},{5,6}} G A Fig.8-G A = (0) 6 e6 A A e 6 = =

40 A A 2 = = A 3, , 4... A 6. () G2=(V2,E2) V2={,2,3,4,5,6} E2={{,3}, {2,}, {3,2}, {4,}, {4,5}, {4,6}, {5,3}, {5,6}} G E2 {,3} 3 3

41 Fig.9- G2 G2 A2 A 2 = A 2 e 6 = = A t 2e 6 = =

42 A 2 2 = = G up :-) 7. G3=(V3,E3)V3={,2,3,4,5,6} E3={{,2},{,3},{,4},{2,3},{3,5},{4,5},{4,6},{5,6}} Fig.20- G3 SNS

43 G3A A3.0 A 3 = A 3 e 6 = = ,2,3C A = = C

44 3. Ncut... f(x, y) =ax 2 + bx 2 + cxy f(x, y) =ax 2 + bx 2 + cxy =(x, y) = x t Ax a c/2 c/2 a x y (x, y) a c/2 c/2 a x y = ax + c 2 y c 2 x + ay x y = ax 2 + c 2 xy + c xy + ay2 2 = ax 2 + bx 2 + cxy OK A = a c/2 c/2 a f(x,y)( a-a ) ( c )

45 A N N λ, λ2,..., λnz, z2,..., zn ( z = z2 =,..., zn = ) R R = z z 2... z n R AR = O O 2... n O O 2... n n = n O n 2 O... n n O O 2... n = 2 O... O n O t O O 2... n = O 2... n

46 () O O 2... n 3.3 R A R 2 = 2 O 2 2 O... 2 n R = z z 2... z n A R λi zi AR = A z z 2 z n = Az Az 2 Az n Az i = i z i Az Az 2 Az n = z 2 z 2 nz n = z z 2 z n 2 n = R 2 n

47 AR = R 2 n R - R AR = R R 2 n = E = O 2 n O 2 n ( )

48 3. X λ λ2... λn z, z2,..., zn R X (z) = zt Xz z t z = R X (z ) R X (z 2 )... R X (z n )= n z, z2,..., zn z z2 λ λ2 λ λ2 Az = z Az 2 = 2 z 2 (z,z 2 )=( z,z 2 ) =(Az,z 2 ) =(z,a t z 2 ) =(z, Az 2 ) =(z, 2z 2 ) = 2 (z,z 2 ) ( 2 )(z,z 2 )=0 (z,z 2 )=0 λ, λ2,..., λn z = z2 =,..., zn =

49 N Nx c, c2,..., cn RA(x) R A (x) = xt Ax x t x wi x = c z + c 2 z c n z n = (c z + c 2 z c n z n ) t A(c z + c 2 z c n z n ) (c z + c 2 z c n z n ) t (c z + c 2 z c n z n ) = (c z + c 2 z c n z n ) t (Ac z + Ac 2 z Ac n z n ) c 2 + c cn n = (c z + c 2 z c n z n ) t ( z c + z 2 c n z n c n ) c 2 + c cn n = c 2 + c n c 2 n c 2 + c cn n = n i= ic 2 i n i= c2 i w i = c 2 i /(c 2 + c c 2 n) 0 R A (x) = n i= iw i n i= w i = RA(x) wn= wi=0 (i=,...,n-) max R A (x) =R A (z n )= n

50 RA(x) A A λn λn-... λ maxmin = max R A (x) = max R A (x) max f(x) = min f(x) min R A (x) =R A (z )= = R X (z ) R X (z 2 )... R X (z n )= n

51 3. Ncut Jn = qt (D W )q q t q Jn Ncut Ncut = Jn Jn 3. Jn = zt Xz z t z Ncut = JnNcut Jn W W = d d 2 d n d 2 d 22 d 2n d n d n2 d nn N Ndij i j e = N e D D = diag(we) diag N N N D

52 d i = j d ij di d O D = d 2 O dn q a -bn a b a = b = d B d A d d A d B d d X = i X d i i Aa i B-bJn Ncut d = d A + d B Ncut = W (A, B) d A + W (A, B) d B Jn q t Wq = a 2 W (A)+b 2 W (B) 2abW (A, B) aw (A) bw (B)+(a b)w (A, B) =0 W (A, B) = qt (D W )q (a + b) 2

53 q t Wq = a 2 W (A)+b 2 W (B) 2abW (A, B) Wq i N j= d ij q i q a -b N j= d ij q i = a N d ij j A b N d ij j B = ad (i) A bd (i) B da (i) i A q t Wq = N i= (ad (i) A bd (i) B )q i = a N i= (ad (i) A bd (i) B ) b N i= (ad (i) A bd (i) B ) = a 2 d A abw (A, B) baw (A, B)+b 2 d B = a 2 d A + b 2 d B 2abW (A, B) aw (A) bw (B)+(a b)w (A, B) =0

54 aw (A) bw (B)+(a b)w (A, B) = a(w (A)+W (A, B)) b(w (B)+W (A, B)) = a d i b d i i A i B = ad A bd B a = b = d B d A d d A d B d ad A bd B = d A d B d A d d B d A d B d = d2 A d B d A d d 2 B d A d B d =0 W (A, B) = qt (D W )q (a + b) 2 xi x i = q i a b 2 2 a + b x i = if q i = a if q i = b

55 (x i x j ) 2 = 0 if x i = x j 4 if x i = x j W(A,B) W (A, B) = 2 ij (x i x j ) 2 4 d ij xi(xi - xj) 2 (x i x j ) 2 = q i a b 2 = 4(q i q j ) 2 (a + b) 2 2 a + b q j a b 2 2 a + b 2 W (A, B) = 2 ij (q i q j ) 2 (a + b) 2 d ij = 2 ij q 2 i 2q i q j + q 2 j (a + b) 2 d ij = q 2 i d ij 2 q i q j d ij + q 2 j d ij 2(a + b) 2 i j i j j i = q 2 i d i q i q j d ij (a + b) 2 i i j Dq i diqi Wq j Σjdijqj W (A, B) = (a + b) 2 (qt Dq q t Wq) = qt (D W )q (a + b) 2

56 Ncut Jn aw (A) bw (B)+(a b)w (A, B) =0 a(w (A)+W (A, B)) = b(w (B)+W (A, B)) ad A = bd B W (A, B) = qt (D W )q (a + b) 2 (a + b) 2 W (A, B) =q t Dq q t Wq q t Wq = a 2 W (A)+b 2 W (B) 2abW (A, B) (a + b) 2 W (A, B) =q t Dq a 2 W (A) b 2 W (B)+2abW (A, B) (a 2 +2ab + b 2 )2W (A, B)+a 2 W (A)+b 2 W (B) 2abW (A, B) =q t Dq a 2 (W (A)+W (A, B)) + b 2 (W (B)+W (A, B)) = q t Dq a 2 d A + b 2 d B = q t Dq ad A = bd B a(a + b)d A = q t Dq

57 Ncut = W (A, B) d A + = W (A, B) = W (A, B) Ncut=JnJn D W (A, B) d B + d A d B d A + = W (A, B) a + b ad A = qt (D W )q a(a + b)d A = qt (D W )q q t Dq = J n J n = qt (D W )q q t Dq = qt D(E D W )q q t D 2 D 2 q = qt D 2 (E D 2 WD 2 )D 2 q q t D 2 D 2 q a b d A = D 2 q t (E D 2 WD 2 ) D 2 q D 2 q t D 2 q z = D 2 q X = E D 2 WD 2

58 zx X λ0 Ncut B Jn = zt Xz z t z Fig.2- W(A,B) = 0λ=0 Fielder Fielder Ncut 3. () Mcut Ncut Mcut Mcut

59 a. () ( ) ( )...tuχ ANOVA ( ) ()... b. ( ) ( ) (LOESS ) ( SVM ) ( K-means )

60 . [ ] : : {,2,3,4,5,6} : 5,6,3,,3,5,6,,2,3,5,,6,4,2,4... ( ) [ ] : :. {A,B,...,N } : ( ) Crand R = Blum- Blum-shub s 2 s 2 μσ 2 x E(ˆµ) =µ ˆµ ˆ2 E(ˆ2) = 2 x

61 s 2 x,x2,...,xn x E(s 2 )=E n n i= = n E n = n = n = n = n n i= n i= n i= n i= i= = 2 2 x (x i x) 2 (x i x) 2 E(x) =E E(x) =µ E(ŝ 2 )= 2 n n i= = n E n = n nµ = µ E (x i x µ + µ) 2 E ((x i µ) (x µ)) 2 E (x i µ) 2 2(x µ) n E (x i µ) 2 E (x µ) 2 n i= n i= x i x i E [x i µ]+ n n i= E (x µ) 2

62 s 2 u 2 = n s2 u 2 σ 2 u 2 n- 3. Fit μσ 2 f(x) = 2 e (x µ) ( )

63 ( ) X,X2,...,Xn µ = E(X i ) 2 = V (X i ) i =, 2,,n 4 = E(X i µ) 4 Pr lim n X + X X n n = µ = lim n X = µ ( ): X,X2,...,Xn µ = E(X i ) 2 = V (X i ) i =, 2,,n Y Y = n(x µ) lim n n(x µ) = 2 e x 2 2 dx

64 t Fχ 2 tfχ 2 Fig.22- F F: F : FF : t 2. ANOVA... t: t : tt :. Student t Welch t... χ 2 χ 2 : χ 2 : χ 2 ( ) χ 2 :

65 vs tt = U (=Wilcoxon) t t t ( ) ( ) α t F F

66 t Ft Welch t Welch t [ ] Z 2tWelch t FANOVA [] 2Wilcoxon( )= U ( ) ( )= ( ) χ 2 = [ ] t 0.05 () tulsd OK HSD (R) k α α/k α/k α=α/k, α2=α/(k-),..., αk=α iαi

67 BLAST E E BLAST E 0,000 (= ) 9,999 9,999 E 9,999P E E P E=0.05 E=0-0 E=0-00 E E-0 E-00 E-0E E? E-0 E E E e -0 E-0 E E e 0 = eeeeeeeeee E 0 = E D ahoo E

68 BLAST E S Fig.23-BLAST(Korf I et al., BLAST ) E. ( ) 970 pn Rn p nnp 2 np 2 3 np 3...i np i l np l = R n log p (n)

69 np l = 2. p l = n log p p l = log p n l = log p n m n M M = log p (mn) Arratia Waterman E(M) = log (mn) + log (q)+ log (e) p p p 2 log p Var(M(m, n)) (e) γ= () q=-p ( Attatia (986) ) E(M) E(M) log e (Kmn) λ=loge(/p) K M S E(S) = log e(kmn)

70 3. P xs x(x>>e(s))x S x n P n = e x x n n S x S x S x S-E(S) c x=c+e(s) P 0 = e x P 0 = e x P (S E(S) c) = e pc P (S x) = e p(x E(S)) = e px ln(kmn) = e p ( x ln(kmn)) = e p ( ln(kmn)e = e Kmne x P x ) =ln p e = p P = e

71 lim x e e x e x x>2 P (S x) Kmne x P S S = S ln Kmn P (S x) e x Bit score = S ln(2) S 2 E 4. E E S f(s) = e S S x P (S x) = x f(s) = = e x x e S ds S x (Kmn)

72 E(x) =Kmne S x Kmn E PE P (x) = e E(x) x P(x) E(x) P (x) E(x) 5. P P. 2. α 3. - α ( P )

73 Yev Y ev = e x e x P(S<x) Yev - x P (S <x)=e e x P(S x) P(S<x) x u Su=E(S) P P (S x) = e e x X = (x u) P (S X) = e e (x u) = e e (x log e (Kmn) ) = e e x+log e (Kmn) = e Kmne x Fig.24-: (μ=0,σ 2 =) : (μ=0,η=)

74 (...) BAP(A B) P (A B) = P (A B) P (B) B ( ) A B ( ) B A P(A) P(A B) B *cap A B cup A B A B D n (H,H2,...,Hn) HiL(Hi) Hi L(Hi) Hi D D L(H i )=P (D H i ) P (A B) =P (A B)P (B) A B P (B A) =P (B A)P (A)

75 P (B A) =P (A B) P (A B)P (B) =P (B A)P (A) P (A B) = P (B A)P (A) P (B) P(D Hi ) P(Hi) HiP(D) D P(Hi D) D HiHi P(D) Hi Hi P(D) P (H i D) = P (D H i)p (H i ) P (D) P (D) =P ((D H ) (D H 2 ) (D H n )) = = n i= n i= P (D H i ) P (D H i )P (H i ) P (H i D) = P (D H i )P (H i ) n i= P (D H i)p (H i )

76 : P(D Hi) : P(Hi D) (Hi) : P (H i D) = P (D H i)p (H i ) P (D) P(Hi)/P(D)

77 () DNA DNA a. ( ) b. DNA ( ) c. DNA ( n DNA4 n ) in/del ( ) : DNA BLAST, FASTA, SSearch( ) NP (Clustal, Muscle, Mafft, T-coffee... )

78 NJ ( ) internal outgroup : : - 3 () : : () ( )

79 : : : 6S/8S rrna : : : e.g. 6S rrna Hox : e.g. : :

80 (α) (a t c g)(β) (A) Jukes-Cantor (B) 2 Jukes-Cantor (C) - Jukes-Cantor ( ) 2 (D) Fig.25- (α)(β)

81 Tab.2-α βgi (Nei et al., 2006 ) Tab.3-BLOSUM62. A R N D C Q E G H I L K M F P S T W Y V B Z A R N D C Q E G H I L K M F P S T W Y V B Z a,b,c

82 a. UPGMA (Unweighted pair group method using arithmetic averages) [] 2 [] ( ) [ ] LUCA UPGMA NJ (Neighbor joining method) ( ) - [] L L L 2 [] [ ] ( )

83 b. + [] k0 k [] [ ] ( ) () c.( ) () ( ) ( ) [] MCMC [] [ ] ( )

84 ( ) Fig.26- (Pellegrini M et al., 999 ) Step (Genomes): 4 Genome P-7 Step2 (Phylogenetic Profile): Step3 (Profile Clusters): Step4 (Conclusion):

85 . ( ) 2. BLAST 3. 3 ( ) NCBI BLAST BLAST BLAST 2 6-frame BLAST TBLASTN 3 ( ) (Mutual information) BLAST 0/( ) BLAST 0/

88 Memorandum

x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y)

x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 1 1977 x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y) ( x 2 y + xy 2 x 2 2xy y 2) = 15 (x y) (x + y) (xy