Title
重み優先探索と機械学習アルゴリズムによるDNAアセン
ブルの精度向上
Author(s)
大城, 絢子; 岡崎, 威生; 名嘉村, 盛和; 安富祖, 仁
Citation
沖縄大学マルチメディア教育研究センター紀要 = The
Bulletin of Multimedia Education and Research Center,
University of Okinawa(12): 7-15
Issue Date
2012-08-31
URL
http://hdl.handle.net/20.500.12001/10261
m~fJ:)t~~ e:t~;f!t~$~7
Jv:f
lJ
:XL~~
d:
G
.
DNA
7t/7JvO)*~~~l:
Accuracy improvement for DNA assembly with weight first
search and machine learning algorithm
::ktfiX
*Tij-=f+
t
/!Rdlli~&X;j::+z
/
1:;~11·f&f
D
+2
/3'C'i't.ll
{
-
+
1Ayako
OHSHIRQ
+
t /
Takeo
OKAZAKI
+z
/
Morikazu NAKAMURA
+z
/
Hitoshi AFUSO
+t
+
I
]:)1t:f.:j(*~flltfJI:!I~~Jf~f-'1-Graduate School
of
Engineering
of Science, University of
the Ryukyus
+2J:At:f1*~I~M'~·Iw¥~I~~4
Department
of
Inf
ormat
i
on
Engineering, University
of
the Ryukyus
iV.>~*~
:Jzt!t1i: :/-7
/-lj-0) ~~H::J:
'J,
~JJ.Jf:Z'J
@2:§
!J
*
~m<
G
:M!::J
!J9!1
fJI:!
~1'T'5
::.
c
'l.\DNA
@2:§!J
0) ~J*9!1fJI:! i61PJ~~r~ tc~: -::Jt::.o
~0)-trc ~ 7.7 t /
-:iJv0)3B1:i61lJ!l~11f t~tJ:o,
IE~itJ:@c:J!J*lli-EliJ<~~~~H~tJ:9
c
~)-5
F"9~i611:
G
t::.o
::<t:W~Tf-;t, @2:JUFa90)m1j[*t~~ § tAa15-~1'T v), 511~G
tda15-@2:§
IJi6
> G
~~-::Jtda15-@2:§
!J
~ Jf:Z'J
~~'2-, *a-ElO)Il~;:o~T~HfiR ~~9:~tt::.=Fr~~1~~
G,
7 t /
:iJvO)'i·i~~~~ffilli LJ::.~ ::<t:~-cf-;t~O)fll!f~ cPX:.*t~ ".:Jv)T¥~1599oAbstract
With development
of second generation technology,
it has become
possib
l
e
to
speedily get
massive
short-read seQuences.
On the
ot
h
er
hand,
s
h
ort
-r
ead seQuences occur
misassembly
and
this
problem
.
makes DNA
assemb
l
y
difficult.
We proposed assembly procedures that included
discriminant
m
e
thod
and
lower limit for
weight
first
search
algorithm. We had a
eva
lu
ation of assemb
l
y performance.
In this manuscript,
we
report
on conclusion about summary and conclusion
.
-1．研究背景 生命'情報工学の分野において、複数の遺伝子配列データを比較し相同性を発見する事で、遺伝子の構造や機 能を推定する研究が盛んに行われている。そのためには、正しい配列データの獲得が前提となる。 図1:生命情報工学における配列解析 配列データはDNAシークエンシングを行うことで獲得される。DNAシークエンシングとは、塩基配列 の 読 み 取 り を 行 う こ と で あ り 、 遺 伝 情 報 を 解 析 す る た め の 基 本 手 段 と な っ て い る 。 D N A シ ー ク エ ン シ ン グ を行うために、シークエンサーが用いられている。シークエンサーが出力した断片配列を結合し、配列デー タを生成する。断片配列を結合する過程をDNAアセンブルとよぶ。従来型に比べ、次世代シークエンサー では読み取り長を短くし並列処理を行うことで高速処理が可能になった。その一方で、出力される断片配列 が非常に短いため、アセンブルが非常に困難になるという問題が生じた。正しく配列結合を行うということ は正しい全配列データの復元を行う上で最も大切な条件である。
2．一般的なDNAアセンブルにおける問題点とその改善のための目的
シークエンサーが一度に読み取れる長さには限界があるため、DNA全配列をシークエンサーに読み取ら せるのは不可能である。そこで一般的には、DNA細胞を、PCR[1]と呼ばれる複製法により複製しシーク エ ン サ ー の 読 み 取 り が 可 能 な 長 さ に な る ま で 細 断 片 化 す る 。 細 断 片 化 さ れ た 配 列 は シ ー ク エ ン サ ー に よ っ て 読 み 取 ら れ 、 断 片 配 列 と し て 獲 得 さ れ る 。 元 配 列 を 複 製 し て 細 断 片 化 さ れ た 断 片 配 列 同 士 に は 重 複 部 分 が 存 在する。アセンブルでは断片配列同士を、重複情報をもとに有向グラフにより表現し配列同士を結合する。 0シークエンサから獲得した断片配列を用意する。 1断片配列をそれぞれノードとする。ノード間に十分な重複部分があればエッジを与え、隣接有向グラフを 作成する。 − 8 −2グラフ内で経路探索を行い経路を決定する。 3決定した経路に従い結合配列を生成し出力とする。 ＜入力＞シークエンサーから得られた 断片配列 配 列 そ れ ぞ れ を ノ ー
画 面 圃 師 画 面
A ¥ ¥ ド と 見 な雷J回向配叩
ノード間(断片間)に ＠噸f随p部分があれば凶
リンクされたノード同士は ■接していると見なし、”グラフを生錘する．圏
棲
グ
"
陰
塁
隣接行列としても表現される．P
恥A 脇 A ◆ R8 跡 棚 a’ , む 0 勘 瞳 4 ⑱ 8 苧 8 割 p ＃ 3 8 ， 厩 ＊ 9 ｡ シークエンスを生成する心
<出カジ 図2:DNAアセンブルの流れ 次世代シークエンサーの読み取り可能な長さが短いことより、ステップ2の経路を決定し配列結合を行う といった段階において、図3のように結合ミスによるミスアセンブルの発生が顕著になった。そこで本稿で は、結合精度を向上するアセンブル法について提案し評価をおこなった。回国日GTC
‘圃同嗣圃’ACCQT同一一∼ご
Ilal侯I侯InlTA C C G T C A C C G T C A C G A − T C A A↓一= 一
jACCGTCAa￨
どちらが正しいかわからない 図3:Short-read結合の困難さ − 9 −3．重み優先経路探索を用いたアセンブル法
断片配列同士の結合部分長は、結合信頼性の高さに影響している。隣接グラフ内で信頼性の高い経路探索
を行うために、図4のように重み、つまり断片配列同士の重複部分長の値が大きくなるように探索を行う。
ｌｌｌＩＩＩ凶
一 一 一 . − − − − 1 1 − ． − 1 − 一 一 一 一 一 一 図4:エッジに重みを与えた重み優先探索 【重み優先探索によるアセンブル法】 0シークエンサから獲得した断片配列を用意する。 1断片配列をノードとし、ノード間に重複部分があればエッジを与える。エッジを1本経由することを1ステップとし、全てのノード間の距離を格納した距離行列とノード自身の次に訪問が可能なノードを格納し
た経路行列、訪問済みノードを記憶する行列を用意する。 2探索を開始する。ステップをlずつ増やし、重みが大きくなるよう経路を選択し全てのノードに関しての 距離行列、経路行列、訪問済み行列を更新する。3訪問可能になったノードを経由する方が重みが大きくなる場合は経路行列に新たにノードを追加し、距離
行列には、新たな経路による重みを格納する。その際には訪問情報を格納した行列も更新する。 4ステップ数を増やして2の手続きを繰り返し、ステップ数がノード数の半分に達したら探索を終了する。 5経由したノードと結合部分長、配列長の情報を保存し、経路にしたがって結合配列を生成し出力とする。 重み優先探索によるアセンブル法に従い出力された結合配列の精度を評価するために、結合配列が元の配列に含まれている（正結合配列）か否（誤結合配列）かを確認した。精度確認用断片配列データには酵
母菌配列データの一部（長さ2380base)を50-70baseに断片化したものを利用した。酵母菌の塩基配列
データは生物の中でも配列長が短く、配列解析の研究で最も利用されているデータである。配列データは
RIKEN[2]のデータベースサイトから獲得した。出力された結合配列726本のうち正結合配列が311本、誤結合配列が415本であり、重複部分長が最大
であることが必ずしも配列結合が正確であるとは限らないことを確認した。誤結合を防ぐには、結合の際に
結合部分長の下限値を設けることが有効だと考えられる。さらに結合配列に対して正誤判別が可能なルール
を、正結合配列（正例)、誤結合配列（負例）の特徴を学習することで獲得し、重み優先探索アルゴリズムか ら生成される結合配列に適用する。判別ルールが「正結合」と判別した結合配列のみ出力とすることで、正 結合配列のみ獲得することができる。 本研究では学習データを以下のように生成し、判別ルールを獲得した。 1 0 -一 A C C G ” 4 p 凸 郎 D a B L ■ ■ CGAC TCACGA ACCGTG “ 2 ●曽申凸凸令qe4も 凸■ ● も り 弓 G b a CGAC 町 q P O ■ ■ 啓 一 T r ■ ■ ■ ■ ■ ■ ■ ■ ■ ｳ ■ 画 3 T℃':ga 2 己 0 晶 C ■ 卓 & ■ I U ■ ｡ ■ ■ 4 ｡ 申 ■ ● 4 ■ G 守 口 ｡ ■ 生 ■ ■ ■ ■ ■ ､ ■ 早 ■ ● ■ ＆ ■ ■ ■ ■ ｳ ㈲ 固 守 q b や ﾏ ● 邑 心 ■ 坤 旬 ○ 寺 ■ ■ 弓 や ◆ 険 白 ● ● 『 ｡ 白 け 僧 寺 令 守学 習 デ ー タ の 生 成 方 法 1.ターゲット配列に生物種が類似した既知の配列を用意する。 2 次 世 代 シ ー ク エ ン サ ー に な ら い 、 複 製 し て 配 列 を 断 片 化 す る 。 3断片配列から重み優先探索によるアセンブル法による結合配列を生成し､正例(元の配列に含まれている)、 負例（元の配列に含まれていない）に分類する。 4 各 結 合 配 列 の 持 つ 、 配 列 長 や 重 複 長 と そ れ ら の 合 成 関 数 を パ ラ メ ー タ と し て 設 け る 。 5.正例、負例とパラメータ値の情報を含んだ学習データを機械学習させ、判別ルールを獲得する。 学習能力の高い判別ルールを獲得するために、結合配列の「重複部分長｣、「結合配列長｣、「重複部分長× 結合配列長｣、「重複部分長／結合配列長｣、「log(重複部分長)｣、「log結合配列長)」をパラメータとして学 習させ判別ルールを獲得した。 また高性能の判別ルールを獲得するために、本研究では複数のSupportVectorMachine[3]について学 習 能 力 の 比 較 を 行 い 、 最 も 学 習 能 力 の 高 い （ 正 例 、 負 例 を 正 し く 学 習 し 識 別 で き る ） 機 械 学 習 ア ル ゴ リ ズ ム を提案手法に適用した。比較候補としてPolynomialkernelSVM、GaussiankernelSVM，Linearkernel SVM、HyperbolictangentSVMを列挙した。 判別ルールがどれほど正例と負例を正しく識別できたかを、表lのように整理する。 有 効 無効 正しい結合
C/C:正しい結合に対して有効と判定した配列数
C/W:正しい結合に対して無効と判定した配列数
誤った結合W/C:誤った結合に対して有効と判定した配列数
W/W:誤った結合に対して無効と判定した配列数
判別ルールによって出力される本数 表1:識別結果フォーム c/c、w/wは正しく判定された結果になるので、これらをデータの総数で割った数を学習の精度とした。 {C/C}+{W/W}学
習
網
膜
"
{
c
/
c
}
-
i
-
{
c
/
w
]
+
n
v
/
c
}
-
i
-
m
/
w
]
学習能力の比較結果 重 み 優 先 探 索 に よ る ア セ ン ブ ル 法 に 従 い 、 既 知 で あ る サ ン プ ル 配 列 を 用 い て 、 学 習 デ ー タ に 対 し て 各 SVMalgorithmの学習精度比較評価をおこなった。比較の際には、正例61本、負例58本を検証用データ に用いた。 表2より、PolynomialkernelSVMやHyperbolictangentSVMに比べてGaussiankernelSVMや PolynomialkernelSVMは正例を多く残し、負例を多く取り除くことができている。 1 1-PolynomialkernelSVM 有効 無効 学習精度 正しい結・合 59 2 98.3％ 誤った結合 0 58 LinearkernelSVM 有効 無効 学習精度 正 し い 結 合 54 7 92.4％ 誤った結合 2 56 GaussiankernelSVM 正し↓ ÷ へ ロ ロ 誤った結合 有効 58 0 lp 無効 学習精度 3 97.4％ 58 1 HyperbolictangentSVM 有効 無効 学習精度 正 し い 結 合 51 10 91.6％ 誤った結合 0 58
表2:各SVMalgorithmについての学習精度比較
次にこれらのSVMがどれほどの識別能力を持つのかを、学習データとは異なる配列から生成したオープ ンデータを利用して検証した。データには、DNAデータベースから獲得した別の酵母菌（長さ2325base， 複製回数7回、断片配列本数600本）を用いた。各機械学習アルゴリズムの識別精度を以下に示す。 " PolviioinialkernelSVM 有効 無効 学習糖度 正しい結合 344 2 99.5％ 誤った結合 1 345 LinearkernelSVM 有効 無効 学習精度 正しい結合 344 2 98.4％ 誤った結合 9 337 GaussiankernelSVM 有効 無 効 学習糖度 正しい結合 345 1 ”､7％ 誤った結合 1 345 HyperbolictangentSVM 有効 無効 学習精度 正 し い 結 合 328 18 96.9％ 誤った結合 3 343 表3:各SVMalgorithmについての判別精度比較 学習用のデータとオープンデータどちらについても、GaussiankernelSVMがほぼ正確に正例と負例を 判別できていることから、本研究の機械学習アルゴリズムとして採択した。 以上より、判別ルールと結合下限値適用による重み優先探索法を提案した。 【判別ルールと結合下限値適用による重み優先探索法】 0シークエンサから獲得した断片配列を用意する。 1断片配列をノードに格納し、設定した下限値以上の重複を持つノード同士の重み情報のみ格納した隣接グ ラフを生成する。 2重み付き隣接グラフに対し重み優先探索を行い、決定した経路に従い結合配列を生成する。 3ターゲットである断片配列の種が類似した既知配列に対し重み優先探索を行い、学習データを生成する。 4学習データに機械学習を適用し判別ルールを獲得する。 5ターゲットの断片配列に対し重み優先探索を行い生成した結合配列から判別ルールにより選別された複数 の結合配列を出力結果とする。 − 1 2 −出力
｜出力I
図5:判別ルールと結合下限値通用による重み優先探索法アセンブルの流れ4．提案アセンブル法に対する検証実験
本 研 究 で は 配 列 間 の 重 複 長 に 着 目 し 結 合 を 行 い 、 獲 得 し た 結 合 配 列 か ら 誤 っ た 結 合 配 列 を 取 り 除 き 、 結 合 の際に下限値を設けたアセンブル手法を提案した。提案手法においての機械学習の効果、下限値設定の影響 について、断片配列データを用いて評価した。 出力配列中の正しい結合の割合も確認する必要があるので次式により与えた。 {C/C} 学習による出力中の判別精度＝ [C/C}+{WC] データ量、つまり断片配列数の変化による出力結果の違いをみるために本実験では、断片配列数を300, 900本と本数を変えて実験を行い、出力結果の違いを考察した。結合下限値は3，5，7，11と変化させて 検証した。 本実験では酵母菌（長さ2400base)の塩基配列データを用いた。配列データは機械学習アルゴリズムの学 習能力の比較を行う際に用いた酵母菌データを獲得したRIKENのデータベースサイトから獲得することが 可能である。 本稿では断片配列本数を300，900本で入力した際の結果について表4−6に掲載する。重み優先探索法と 提案した判別ルールと結合下限値適用による重み優先探索法の、出力された正結合配列について比較した。 ここで、出力された全ての結合配列が元の配列をどの程度正しく復元しているかを評価する「被覆率」も 検討指標に加えた。出力を制約することによる被覆率の変化も観察した。 断片配列数3卯本 断片配列数900本 結 果 被覆率 結果 被覆率 正結合 311（428％） 正結合 1109(4“％） 誤結合 415(57.2％） 98.9％ 誤結合 1182(52%) 99.5％ 合 計 726 合計 229(） 表4:重み優先探索法による判別精度 − 1 3 −下限値 結 果 有効 無効 計 判別精度 出力中の判別精度 被 覆 率 正 結 合 310 1 311 0 誤 結 合 4 411 415 ”.3％ 98．7％ 98.9％ 出力 314 正 結 合 306 3 309 3 誤結合 6 55 ti1 97.5％ 98％ 98.9％ 出力 312 正 結 合 309 7 316 5 誤 結 合 4 11 15 96.6％ 98.7％ 98今99％ 出力 313 正結合 309 9 318 7 誤結合 0 2 2 97.1% 1Ⅸ)％ 92.7％ 出力 309 正結合 310 8 318 11 誤結合 0 0 0 97.4％ 100％ ”､7％ 出力 310
表5:判別ルールと結合下限値適用による重み優先探索法による判別精度(断片配列数300本）
下 限 値 結果 有効 無効 計 判別精度 出力中の判別精度 被覆率 正結合 1105 4 1109 0 誤 結 合 5 1177 1182 99.6％ 99.5％ 99.5％ 出力 1110 2291 正 結 合 1100 3 1103 3 誤結合 6 51 57 99.2％ 99"4％ ”.4％ 出力 1106 1160 正結合 1111 6 1117 5 誤結合 7 6 13 98.8％ 99.3％ 99.4％ 出力 1118 113(） 正結合 1140 6 1146 7 誤結合 1 0 1 99.3％ ” ％ ”､4％ 出力 1141 1147 正結合 1138 6 1144 11 誤 結 合 0 ）〔 0 99％ 1 0 0 ％ ′ 99.4％ 出力 1138 1144表6:判別ルールと結合下限値適用による重み優先探索法による判別精度(断片配列数900本）
1 4-結果より以下のことがわかった。 ･断片配列数が少ない時(300本）下限値を過度に上げると、被覆率は下がるが、正しい結合配列が獲得さ れやすくなる。よって、機械学習アルゴリズムと最適な結合下限値を組み合わせることで、精度の高い 配列が得られる。 ･断片配列数が多い時(900本)、配列数が十分にあるので、結合下限値を過度に上げても被覆率は下がら ない。よって配列本数が十分に多い時は、機械学習を行わなくても下限値を高く設定することで結合精 度の高い配列が得られる。 5 ． ま と め 正確なDNA配列を実現させるため、本研究では、配列間の重複長に着目し結合を行い、獲得した結合配 列から誤った結合配列を取り除き、結合の際に下限値を設けた手法を提案した。以下に本研究の成果を述べ る。 ・判別ルールと結合下限値適用による重み優先探索法出力結果を比較することで、機械学習の効果が確認 できた。 ・断片配列本数が十分でない場合、学習の効果は出るが、結合下限値を高く設けると、被覆率が下がって しまう。よって断片配列数が少ないときは、下限値を高く設定せずに機械学習を実行する方が被覆率を 下げずにすむということがわかった。一方で断片配列数が十分である場合、結合下限値を高めに設定し ても被覆率は下がらない。よって断片配列数が多いときは下限値を高めに設定することで機械学習をす る必要が無くなるということがわかった。 以上から、実際にヒトゲノムなどの大量の配列データのアセンブルを考慮すると、元配列が長く十分な断片 配列が獲得するのが困難であることから、次世代シークエンサーから獲得された断片配列を用いて全配列復
