Vol (??? 1959) DNA Analysis of Evolutionary Lineage by Self-organizing map Kentaro Nishimuta, 1 Ikuo Yoshihara, 2 Kunihito Yamamori 2 a

Size: px

Start display at page:

Download "Vol (??? 1959) DNA Analysis of Evolutionary Lineage by Self-organizing map Kentaro Nishimuta, 1 Ikuo Yoshihara, 2 Kunihito Yamamori 2 a"

おきみちさわなか
5 years ago
Views:

1 Vol (??? 1959) DNA Analysis of Evolutionary Lineage by Self-organizing map Kentaro Nishimuta, 1 Ikuo Yoshihara, 2 Kunihito Yamamori 2 and Moritoshi Yasunaga 3 DNA base sequences are considered to involve foot prints of evolution of living creatures. Most analysis methods of the base sequences employ pattern matching rules or knowledge, which require a lot of knowledge and data in advance. This paper proposes an evolutionary lineage method of species by using a novel Self-organizing map (SOM) whose inputs are frequency of appearance of codons. The neighboring relation of the SOM is believed to correspond to similarity between species. 1 Graduate School of Engineering University of Miyazaki 2 University of Miyazaki 3 University of Tsukuba 1. DNA 1) DNA 2) DNA 3) DNA A C G T = ) 1)4)5) 5) 6) 7)8) 1/f 9) 10) 11)12)13)14)15) 16) c 1959 Information Processing Society of Japan

2 自己組織化マップを用いた生物種の系統解析手法の提案して各コドンの出現頻度を計算する多量のデータを扱うことのできる自己組織化マップへ入力し可視化するめに開発された17) 自己組織化マップは高次元空間のデータを 2 次元空間に非線形写像するアルゴリズム自己組織化マップ SOM:Self-Organizing Map は Kohonen によって提案されたニュー 17)

2 自己組織化マップの構造度を反映したマップを作成することにより特徴をより可視化する分類の施されていない自己組織化マップは図 1 のように入力層と競合層の 2 層から構成されている入力層未知のデータを扱うことが可能でありデータの量や構造といった性質に依存しない自は n 次元の入力ベクトルと同じ数のノードがある競合層のノードは出力を視覚的に見

2 2 自己組織化マップを用いた生物種の系統解析手法の提案して各コドンの出現頻度を計算する多量のデータを扱うことのできる自己組織化マップへ入力し可視化するめに開発された17) 自己組織化マップは高次元空間のデータを 2 次元空間に非線形写像するアルゴリズム自己組織化マップ SOM:Self-Organizing Map は Kohonen によって提案されたニュー 17) ラルネットワークの 1 種である入力データ間の関係を教師なし学習しデータの類似であるそのため高次元データの分布を 2 次元平面上に視覚化する有効なモデルである 2.2 自己組織化マップの構造度を反映したマップを作成することにより特徴をより可視化する分類の施されていない自己組織化マップは図 1 のように入力層と競合層の 2 層から構成されている入力層未知のデータを扱うことが可能でありデータの量や構造といった性質に依存しない自は n 次元の入力ベクトルと同じ数のノードがある競合層のノードは出力を視覚的に見己組織化マップによって可視化されたマップに現れる領域の位置はそれぞれの類似度に関係るため通常 2 次元に配列される競合層ではノードがそれぞれの近傍の情報をもとに学習し隣接する領域は遠く離れた領域よりも近い性質を持っていると推測できるつまり未を行う自己組織化マップの学習は競合層の構造に影響を受けることがあるたとえば四知の遺伝子を入力した場合様々な生物種の遺伝子と入力することによって未知の遺伝子方に境界を持つ長方形型の構造の場合境界際の学習の近傍領域が減少してしまうそこでと他の生物種の遺伝子と領域が隣接関係にあれば隣接関係にある生物種の特徴パターンとノードの構造は球体や上下左右がつながったトーラス構造をとるものがあり本研究はトーマッチングができるなど解析を行う前の手がかりになるとも考えられるまた作成されラス構造の競合層を用いるたマップにおける各領域の相対関係を解析するために各領域を構成するノードから特徴また競合層のノードは重みベクトルを持っており入力層のノードと完全結合しているノードを決定し特徴ノード間の距離を算出するさらにこの特徴ノード間の距離を生物種間の距離と考え距離行列法によって系統樹を作成する本研究ではコドンの出現頻度を入力とした自己組織化マップにより可視化しマップ上の領域の隣接関係によって生物種の系統解析を行い作成されたマップの領域の相対関係から系統樹を作成する方法を提案する実際にこの手法を 20 種の生物種のリボソームタンパク質遺伝子を使用し解析を行った自己組織化マップによる可視化では生物種ごとに領域が作られ領域間の隣接関係は生物種間の距離と対応していた系統樹を作成した結果は大まかにみると動物類菌類植物類に分かれ細かく見るとネズミ科に属するハツカネズミとドブネズミが結ばれそれらと同じ哺乳網に属するヒトが結ばれており系統が反映された系統樹が作成できた 2. 自己組織化マップによる進化系統解析手法図 1 自己組織化マップの構造 Fig. 1 Structure of SOM 生物種の塩基配列から標本を切り出し標本ごとに特徴量としてコドンの出現頻度を計算する計算した出現頻度を 64 次元のベクトルとして自己組織化マップに入力する自己組図2 織化マップは入力データの傾向を学習させデータの類似度を反映した領域を形成するそ自己組織化マップの処理の流れ Fig. 2 Algorithm of som のためマップに形成された領域間の距離と生物種間の距離が対応していると考えた 2.3 学習アルゴリズム 2.1 自己組織化マップ本研究で用いる自己組織化マップ (SOM:Self-organizing Map) はニューラルネットワー自己組織化マップの学習アルゴリズムは主に重みベクトルの初期化入力ベクトルのクの 1 種で Kohonen により記憶やその想起連想のメカニズムを計算機上で実現するた入力ユークリッド距離の計算勝者ノード入力ベクトルとのユークリッド距離が最小な情報処理学会論文誌 Vol (??? 1959) c 1959 Information Processing Society of Japan

3 3 5 2 n x (n) = (x (n) 1, x(n) 2,..., x(n) ) w = (w 1, w 2,..., w k ) i = (0, 1,.., I 1) j = (0, 1,..., J 1) Step 1. Step 2. Step 3. E E = N (x (n) k w k ) 2 (1) Step 4. Step 5. k=0 w (new) = w (old) k + α(t)(x (n) w (old) ) (2) t(= 0, 1,..., T ) α(t) β(t) α(t) β(t) α(t) = α init (1 t/t ) (3) β(t) = max{ϵ, β init t} (4) α init (0 < α(t) < 1) β init 2.4 (Batch Learning-Self Organizing Map : BL-SOM) w w (new) = w (old) + α(t) 1 N x (k) w (old) (5) x (k) S S i, j β(t) x (k) N S t(= 1, 2,.., T ) α(t) (0 < α(t) < 1) β(t) α(t) β(t) α(t) = max{0.01, α init (1 t/t )} (6) β(t) = max{0, β init t} (7) α init β init 2.5 3

4 Fig. 3 Shifting of cut-out position Fig. 4 Shifting of codon 3. DNA NJ 3.1 Step1. Step2. 1 Step3. Step2 Step4. Step2 Step5. 1 Step2. Step Step1. Step2. Step distance ab = 63 wan 2 + wbn 2 (8) n=0 a b distance ab = (x a x b ) 2 + (y a y b ) 2 (9) a b

5 rrna RNA rrna RPG(Ribosomal Protein Gene database) 18) SOM SOM : SOM : 0.5 SOM : 12 SOM : Table 1 Species for experiments 4.2 Hs Rn Mm Fr Ci Dm Ag Am Ce Mg Fg Dd Yl Sp Sc Cn Um Ro At Cr 5 Fig. 5 Ideal tree ,

6 Fig. 8 8 Evolutionary tree by distance of ordinate and abscissa 6 Fig. 6 Result of SOM 5. 20 2 0 7 Fig.

6 6 Fig. 8 8 Evolutionary tree by distance of ordinate and abscissa 6 Fig. 6 Result of SOM Fig. 7 Evolutionary tree by distance of weight 9 Fig. 9 Evolutionary tree by mix distance 5.1 SOM SOM : SOM : 0.5 SOM : 20 SOM :

7 ClustalW ClustalW ClustalW ClustalW 12 6 ClustalW Fig. 10 Result of SOM ClustalW ClustalW ClustalW ClustalW Fig. 11 Result of evolutionary tree SOM

8 8 12 ClustalW Fig. 12 Evolutionary tree by ClustalW Fig Evolutionary tree by proposed method 1) ) ) ) Gbas, C. and Jambeck, P.: ) ) I.Yoshihara, H.Takashima, K.Yamamori and K.Sugawara: Similarity Comparisons of Seeds Using Image Compression Technology, Memoirs of the Faculty of Engineering University of Miyazaki, Vol.35, pp (2006). 7) Y.Sakaguchi, I.Yoshihara, K.Yamamori and N.Kenmochi: Criterion of Evolution Analyzing DNA Sequences based on Statistical Mechanics, Memoirs of the Faculty of Engineering University of Miyazaki, Vol.35, pp (2006). 8) Abe, T., Kanaya, S., Kinouchi, M., Y.Ichiba, T.K. and Ikemura, T.: Informatics for unveiling hidden genome signatures, Genome Resarch, No.13 (2003). 9) Y.Koyama, K.Nishimuta, K.Yamamori, I.Yoshihara and M.Yasunaga: Quest fo genetic information hidden behind disorder in DNA sequences, Proc of 15th Int Symp Artificial Life and Robotics, pp (2010). 10) K.Yamamori, Y.Fujita, M.Aikawa and I.Yoshihara: Identification of Exon-intron Boundaries by Integration of Base-oriented Genetic Programming and Statistical Heuristics, Proc of 12th Int Symp Artificial Life and Robotics, pp (2007). 11) I.Yoshihara, Y.Yano, K.Yamamori and M.Aikawa: Analysis of Organism s Evolutionary Relationships using Information Entropy, Memoirs of the Faculty of Engineering, Vol.38, pp (2009). 12) S.Miyazaki, H.Sugawara and M.Ohya: The efficiency of entropy evolution rate for construction of phylogenetic trees, Genes Genet Syst, No.71 (1996). 13) HIV-1(V3 loop) No.1420 (2005). 14) HIV No.IT97-52 (1997). 15) HIV No.IT98-38 (1998). 16) A HA (2007). 17) T ) ribosomal proteingenes database:.

258 5) GPS 1 GPS 6) GPS DP 7) 8) 10) GPS GPS 2 3 4 5 2. 2.1 3 1) GPS Global Positioning System

258 5) GPS 1 GPS 6) GPS DP 7) 8) 10) GPS GPS 2 3 4 5 2. 2.1 3 1) GPS Global Positioning System Vol. 52 No. 1 257 268 (Jan. 2011) 1 2, 1 1 measurement. In this paper, a dynamic road map making system is proposed. The proposition system uses probe-cars which has an in-vehicle camera and a GPS receiver.