早稲田大学の教育・研究・文化を発信 WASEDA ONLINE

RSS

読売新聞オンライン

ホーム  > オピニオン  > サイエンス

オピニオン

▼サイエンス

清水 佳奈(しみず・かな)/早稲田大学理工学術院教授  略歴はこちらから

生命の設計図を読み解く鍵はアルゴリズムの発展にあり

清水 佳奈(しみず・かな)/早稲田大学理工学術院教授
2023.6.19

アルゴリズムは問題解決のレシピ

 アルゴリズムという言葉を耳にしたことがあるでしょうか。これは、数学や情報科学の専門用語で、問題を解くための手順を意味します。現代社会では様々な問題解決にコンピューターが用いられますが、コンピューターにもともと備わっているのは基本的な演算(四則演算やデータの参照など)のみであるため、実際に問題を解くには、どの演算をどの順番で実行するか、すなわち、アルゴリズムの内容を実行プログラムという形でコンピューターに示す必要があります。例えるならば、アルゴリズムは料理におけるレシピ、コンピューターはレシピ通りに料理をする人といったところでしょうか。さて、レシピに良し悪しがあるように、アルゴリズムにも良し悪しがあります。レシピの場合、美味しさの他に、手間がかからず、洗い物を増やさないことが重視されると思います。この点、アルゴリズムにおいても同様で、演算回数や使用する記憶領域が少ないものが優れていると評価されます。

膨大なゲノム配列をどうやって分析する?数千台のコンピューターに勝るアルゴリズムの力

 現代の生命科学ではデータ分析が重要な役割を果たします。これは、計測装置の技術革新により、多様な生命現象を安価に計測し、データを大量に取得できるようになったからです。とりわけ、生命の設計図ともいえるゲノム配列は、過去二十年の間に取得コストが約十万分の一にも低下し、日々生み出される膨大なデータが医学や生物学を飛躍的に発展にさせると期待されています。ゲノム配列は、四種類の文字からなる文字列で、ヒトであれば長さは三十億ほどです。これは文庫本にして約三万冊に相当しますが、その分析の根幹をなすのは、文字列同士の比較です。例えば、ガン細胞のゲノム配列には有害な変異(文字の置換、欠損、挿入)が含まれているのですが、実際にどのような変異が含まれているかを調べるには、健康な細胞のゲノム配列と文字の並びを詳細に比較する必要があります。

 さて、文字列の比較にはコンピューターを使いますが、一般的には、比較する文字列が長いほど多くの演算回数と大きな記憶領域を必要とします。ゲノム配列の取得がそれほど容易ではなかった十五年ほど前、当時最先端のアルゴリズムでは、データベースに含まれるゲノム配列全体から、特定の文字の並びを探し出すには、配列の長さに比例する演算回数が必要でした。そのため、前述のように膨大な数のゲノム配列が生み出されるようになった今、当時のアルゴリズムでは何千台ものコンピューターを投入したとしても計算が終わらない問題が生じました。そこで新たに開発されたのが、事前に検索対象となるゲノム配列をうまく加工しておくことで、配列の長さに依存せずに非常に少ない演算回数で文字列の比較を行うアルゴリズムです。これは、簡潔データ構造と呼ばれる方法に基づくアルゴリズムの一つで、現在の研究現場において、あらゆるゲノム配列分析を下支えしているといっても過言ではありません。

加速度的に増えるゲノムデータを余すことなく活用するには

 蓄積の進むゲノムデータをくまなく活用するには、さらに高度なアルゴリズムが必要とされています。ここでは、私たちの研究室で最近開発したアルゴリズムを紹介したいと思います。ゲノム配列を安価に取得できるようになった現在では、同一生物種について、たくさんのゲノム配列が計測されるようになりました。例えば、同じヒトゲノムであっても、数多くの個人のゲノム配列や、同一人物であっても、複数の臓器由来のゲノム配列を計測します。研究の精度を高めるためには、これらのデータをまとめて分析することが理想的ですが、このように膨大なデータをまるごと検索対象としてしまうと、膨大な演算回数や記憶容量が必要となります。そこで、できるだけ多くの情報を残しつつ、データのサイズを極限まで削減し、さらに、分析の際の演算回数を減らせることのできるアルゴリズムが望まれています。この問題に対し、従来は配列で表現されていた情報をグラフとして表現する方法が模索されています。ゲノム配列は同じ生物種(あるいは近縁の生物種)であれば、大部分が似通っており、文字列が異なるのは一部の箇所にとどまります。そこで、以下の図のように似たような配列を直列に並べるのではなく、同一の部分を一つに集約し、異なる部分のみをグラフの分岐で表現し、実際に観測された文字の並びをグラフ上の経路として表現する方法が考案されました。

waseda_230619_img_1_2.jpg

図1 同一生物種のゲノム配列をグラフ構造に集約

 従来手法では、経路情報をできるだけ小さくするため、すべての情報を記録せず、主要な部分のみを記録していました。このようにすることで、必要となる記憶容量は小さく抑えられたのですが、一部の経路を正確に復元できない問題がありました。そこで、私たちはグラフ上で復元が難しくなっている構造を明らかにし、そのような構造においても正確に経路を記録できる新たなアルゴリズムを考案しました。以下の図に従来手法と新たなアルゴリズムの比較結果を示します。比較には、ヒトの代表的なゲノム配列から生成した人工データを用いました。図に示す通り、従来手法では多くの箇所においてデータの復元に失敗していたところ、私たちのアルゴリズムではほぼ復元ができています。また、従来手法よりも、復元の際の計算が早く(演算回数が少なく)、従来手法と同程度の記憶領域を達成しています。復元に失敗が起きないように、すべての経路を記録した場合の方法と比較すると数倍も記憶領域を削減できています。

waseda_0619_img2.jpg

図2 提案手法の性能(注1)

ゲノム配列の保護に必要とされる新たなアルゴリズム

 ところで、ヒトゲノム配列に関しては、データが増大したことにより顕在化した問題がもう一つあります。安価に入手可能になった個人のゲノム配列はその人物の設計図そのものです。そのため、流出すればプライバシの侵害につながる可能性があります。そうしたことから、データを流出させずに分析する方法が必要になったのです。実は、データを隠したまま特定の演算を行う秘密計算と呼ばれる方法が暗号理論の分野で研究されているのですが、全ゲノム配列の分析を行える効率的なアルゴリズムはまだ開発されていません。私たちの研究室では、前述の簡潔データ構造に基づくアルゴリズムを秘密計算のアルゴリズムとうまく組み合わせる研究も推進しており、これまでに、文字列の部分一致やゲノム情報分析で用いられる機械学習を従来手法より高速に実現するアルゴリズムを開発しています。(注2)

おわりに

 様々な条件下で計測された膨大なゲノム配列から科学的な知見を得るには、高度な分析が必要です。一方で、計算資源は有限ですから、より優れたアルゴリズムの開発が常に望まれ続けている状況です。料理の世界では様々な文化で育まれたレシピが互いに影響を与え合い、より優れたレシピが生み出されていますが、アルゴリズムの世界でも各分野で培われた技術の融合により、革新的な手法が生み出されることを期待したいです。私たちの研究室でも、配列解析アルゴリズムを軸足に多様な技術を取り入れ、ゲノム配列解析にまつわる様々な問題解決に挑んでいきたいと思います。


(注1)「Nozomi Hasegawa, Kana Shimizu,"Efficient Colored de Bruijn Graph for Indexing Reads." Journal of computational biology, 2023」より

(注2)「Kana Shimizu, Koji Nuida, Gunnar Ratsch, "Efficient privacy-preserving string search and an application in genomics", Bioinformatics, 2016」など

清水 佳奈(しみず・かな)/早稲田大学理工学術院教授

2006年早稲田大学より博士 (工学) 取得。同年、産業技術総合研究所入所。メモリアルスローンケタリング癌センター客員研究員、早稲田大学准教授を経て現職。情報処理学会理事、日本バイオインフォマティクス学会理事等を歴任。

ゲノム配列をはじめとする生命情報の分析に必要なアルゴリズムの設計と実装に興味を持っている。最近は、多数のゲノム配列を効果的に表現する参照ゲノムグラフの構築法や、個人情報を守りながらゲノム情報等を安全に分析する方法の開発に興味を持っている。

研究室ウェブサイト:https://www.cbio.cs.waseda.ac.jp/