離散数学第 14回系統樹復元の離散数学

Size: px

Start display at page:

Download "離散数学第 14回系統樹復元の離散数学"

なごみうすい
5 years ago
Views:

目次離散数学第 14 回系統樹復元の離散数学岡本吉央 okmotoy@ueccjp 1 2 形質に基づく系統樹復元 3 Binry

電気通信大学最終更新 2013 年 7 月 29 日 17:54 1 / 44 2 / 44 生物の多様性形態と形質

treehouse id=2482 http://enwikipediorg/wiki/file:fungi of SsktchewnJPG

http://evolutionberkeleyedu/evolibrry/news/061001 trpjw

genotype nd phenotype 5 / 44 6 / 44 系統樹ダーウィンの著書から系統樹他分野での利用法カンタベリー物語

1 目次離散数学第 14 回系統樹復元の離散数学岡本吉央 1 2 形質に基づく系統樹復元 3 Binry Directed Perfect Phylogeny 問題 4 不完全 Binry Directed Perfect Phylogeny 問題電気通信大学最終更新 2013 年 7 月 29 日 17:54 1 / 44 2 / 44 生物の多様性形態と形質 id= of SsktchewnJPG 3 / 44 4 / 44 遺伝子型と表現型系統樹 trpjw stories/evolved enzymes/imges/fly genotype nd phenotype 5 / 44 6 / 44 系統樹ダーウィンの著書から系統樹他分野での利用法カンタベリー物語 (Geoﬀrey Chucer 14 世紀) の写本の系統樹 C Drwin (1859) On the Origin of Species by Mens of Nturl Selection 7 / 44 8 / 44

2 1 1 distnce-bsed pproch 2 chrcter-bsed pproch C Drwin (1859) On the Origin of Species by Mens of Nturl Selection ( ) (14) / 44 ( ) (14) / 44 (1) (2) ( ) (14) / 44 ( ) (14) / 44 Perfect phylogeny M 1 # toes Webbed feet Ostrich 2 N Emu 3 N Pelicn 4 Y Duck 4 Y Owl 4 N Pelicn (4, Y) Duck (4, Y) Owl (4, N) Emu (3, N) Ostrich (2, N) 0 1 () ( ) (14) / 44 ( ) (14) / 44 s c c 3 c 4 c 6 c 8 X T = (X, ) 1 X 2 x, y, z X y, z x y, z ( ) (14) / 44 ( ) (14) / 44

3 T = (X, ) T X T X T = (X, ) Y X Y ( ) (14) / 44 ( ) (14) / 44 T = (X, ) x X x X y X y x y z x z X T = (X, ) T x X 2 b c d e f ( ) (14) / 44 ( ) (14) / 44 () 1 s c 2 c 3 c 4 c 6 c ( ) (14) / 44 ( ) (14) / 44 1 A j = c j (A j = {s i M i,j = 1}) c 3 c 4 c 6 c 8 A 3 =A 4 A 5 A7 A 2 A6 =A 8 s 1,, s n,, c m M {0, 1} n m () M,, A m 2 A i A j A 3 =A 4 A 5 A7 A 2 A6 =A 8 A 2 = A 3 = A 4 = A 5 = A 6 A 7 = A 8 A 2 A 3 A 2 A 4 A 2 A 5 = A 2 A 6 = A 2 A 7 = A 2 A 8 = ( ) (14) / 44 ( ) (14) / 44

4 (1) (2) s 1,, s n,, c m M {0, 1} n m () M,, A m 2 A i A j ( ) T c i c j T 1 c i c j 2 c i c j 3 c i c j 4 c i c j ( ) (14) / 44 s 1,, s n,, c m M {0, 1} n m () M,, A m 2 A i A j ( ) T 1 c i c j A i A j 2 c i c j A i A j 3 c i c j A i = A j (A i A j ) 4 c i c j A i A j = ( ) (14) / 44 (3) s 1,, s n,, c m M {0, 1} n m () M,, A m 2 A i A j ( ),, A m m m = 1 (3) s 1,, s n,, c m M {0, 1} n m () M,, A m 2 A i A j ( ) k < m,, A m A i c i () ( ) (14) / 44 ( ) (14) / 44 () 2 A j = c j c 3 c 4 c 6 c 8 A 3 =A 4 A j = c j c 3 s s s s s 1 s 2 s 3 s 4 A2, A 2 A 3 A 2, A 2, A 2 = A 5 A7 A 2 A6 =A 8 ( ) (14) / 44 ( ) (14) / 44 ( ) (Estbrook, Johnson, McMorris 76) Binry Directed Perfect Phylogeny O(m 2 n) m n O(mn) (Gusfield 91) O 4 ( ) (14) / 44 ( ) (14) / 44

5 (M {0, 1,?} n m ) 1 c 3 c 4 c 6 c 8 s ? 0 s ? s 4 0? ( ) (14) / 44 ( ) (14) / 44 1 (M {0, 1,?} n m ) 1 M {0, 1,?} n m M {0, 1} n m M i,j = 0 M i,j = 0 M i,j = 1 M i,j = 1 M,, A m c 3 s s s 3? 1 1 s 4 0? 1 {s 1, s 2 } {s 1, s 2, s 3 } {s 2, s 3 } A 2 {s 2, s 3, s 4 } A 3 = {s 3, s 4 } A 3 = {s 1, s 2 } A 2 A 3 A 2 = {s 2, s 3, s 4 }, A 2 A 2, A 2, A 2 = ( ) (14) / 44 ( ) (14) / 44 2 (1) c 3 c 4 s 1 1? s 2?? s 3? 0 1?? {s 1 } {s 1, s 2, s 3 } A 2 {s 1, s 2 } A 3 = {s 3 } {s 2 } A 4 {s 2, s 3 } {s 1 } A 5 {s 1, s 3 } = {s 1, s 2, s 3 } A 2, A 3, A 4, A 5 A 2 = A 2 A 3, A 4, A 5? 0 A 3, A 4, A 5 s 1,, s n,, c m M {0, 1,?} n m c k A k = M A k = M,, A m i, j A k ( ) (14) / 44 ( ) (14) / 44 (2) 3 s 1,, s n,, c m M {0, 1,?} n m c k A k = {s 1,, s n } M A k = {s 1,, s n } M,, A m i, j A k {s 1,, s n } ( ) (14) / 44 c 3 c 4 s 1 1 0? 0 s 2 1 1?? s 3? 1 0? s 4 0? 1? s 5? s 6? 0? 1 A 2 A3 A 4 s 1 s 2 s 3 s 4 s 5 s 6 = {s 1, s 2, s 3 } A 3 = {s 4, s 5, s 6 } ( ) (14) / 44

6 s 1,, s n,, c m M {0, 1,?} n m M? 0 {S 1, S 2 } {C 1, C 2 } S 1 C 2 S 2 C 1 M M s i S 1 c j C 2 M i,j = 0 s i S 2 c j C 1 M i,j = 0 ( ) (14) / ? 0,, A m 4 ( ) (14) / 44 ( ) (Benhm, Knnn, Pterson, Wrnow 95) Binry Directed Perfect Phylogeny O(mn 2 ) m n O(mn + k log 2 (m + n)) (Pe er, Pupko, Shmir, Shrn, 04) k? ( ) (14) / 44

離散数学 第 14回 系統樹復元の離散数学

離散数学第 14回系統樹復元の離散数学