Bioinformatics Algorithms: An Active Learning Approach（バイオインフォマティクス・アルゴリズム：アクティブラーニングによる学び）

引用

Compeau, P., & Pevzner, P. (2018). Bioinformatics Algorithms: An Active Learning Approach (3rd ed.). Active Learning Publishers.

章の要約

本書のウェブサイトには11の章が掲載されている。各章の題は生物学的な問いになっており、それぞれがあるクラスのアルゴリズムと組み合わされている。著者たちは方法を次のように説明する。各章は中心となる生物学的な問いから始まり、それに答えるために必要なアルゴリズムの高度さを着実に積み上げていく。何百もの演習が必要になった時点で本文に組み込まれており、無料の Rosalind プラットフォームでは自動採点のコーディング課題に取り組める。ウェブサイトでは第1〜5章を無料で読むことができ、すべての章に講義動画がある。テキストのインタラクティブ版は別売りである。

第1章：ゲノムのどこでDNA複製が始まるのか？

講義ページでは「アルゴリズムのウォーミングアップ」とされるこの章は、細菌ゲノムの複製起点を探す。レッスンは、起点領域に隠されたメッセージ（頻出する語）から、複製の非対称性、前方と後方の半鎖のあいだのスキュー、近似パターンマッチングを経て、大腸菌のDnaAボックスを見つける最後の試みへと進む。エピローグでは、起点予測の難しさが論じられる。

第2章：どのDNAパターンが分子時計の役割を果たすのか？

この章は、遺伝子の調節領域に共通する短い調節パターンを探すモチーフ探索を通じて、乱択アルゴリズムを導入する。「時計」遺伝子は存在するのかという問いから始まり、モチーフ探索が見かけより難しい理由、モチーフのスコアのつけ方、中央値文字列を見つける問題とのつながりを説明する。続いて、貪欲モチーフ探索、乱択モチーフ探索、ギブスサンプリングへと進む。エピローグは、結核菌がどのように休眠するのかを問う。

第3章：ゲノムをどのように組み立てるのか？

ゲノムアセンブリが、グラフアルゴリズムの舞台となる。章はシークエンシングを「爆発する新聞」にたとえることと、文字列再構成問題から始まる。オーバーラップグラフとド・ブラングラフを比較し、ケーニヒスベルクの七つの橋とオイラーの定理に立ち返ってオイラー閉路のアルゴリズムを組み立てる。そのうえでリードペアに進み、エピローグでは実際のシークエンシングデータが抱える問題を扱う。

第4章：抗生物質の配列をどのように決定するのか？

質量分析による抗生物質ペプチドの配列決定を通じて、総当たりアルゴリズムと分枝限定法が導入される。レッスンでは、抗生物質の発見、細菌がセントラルドグマの外で抗生物質をつくる仕組み（非リボソームペプチド）、総当たりと分枝限定法による環状ペプチドの配列決定、20種類を超えるアミノ酸の場合、スペクトル畳み込みを扱い、最後にシミュレーションではない実際のスペクトルに進む。

第5章：生物学的配列をどのように比較するのか？

この章は本書における動的計画法の入門である。非リボソームコードから始まり、マンハッタン観光客問題と両替問題を通じて配列アラインメントを導入し、有向非巡回グラフにおける最長経路とバックトラックへと一般化する。続いて、スコアリング、局所アラインメント、その他のアラインメントの変種、ギャップペナルティ、省メモリのアラインメント、多重アラインメントを扱う。

第6〜8章：ヒトゲノムに脆弱な領域はあるのか？／どの動物がSARSをもたらしたのか？／酵母はどのようにワインの醸造家になったのか？

これらの章は、生物学的な問いを、組合せアルゴリズム、進化系統樹の再構築、クラスタリングと組み合わせる。第6章は、ゲノム再編成（「人をマウスに変える」）、反転によるソーティング、ブレークポイント定理、腫瘍ゲノムにおける再編成を扱う。第7章は、加法的系統樹、UPGMA、近隣結合法、小節約問題を含め、距離行列から進化系統樹を構築する。第8章は、酵母の遺伝子発現データを用いて、最適化問題としてのクラスタリング、k平均法のためのロイドのアルゴリズム、ソフトk平均法、階層的クラスタリングを導入する。

第9〜11章：病気の原因となる変異をどのように突き止めるのか？／生物学者はなぜいまだにHIVワクチンを開発できていないのか？／ティラノサウルスは大きなニワトリにすぎなかったのか？

最後の章群は、組合せ論的パターンマッチング、隠れマルコフモデル、計算プロテオミクスを扱う。第9章は、トライ、接尾辞木、接尾辞配列、バローズ・ホイーラー変換を用いたリードマッピングを説明する。第10章は「いかさまカジノ」とHIVの分類を通じて隠れマルコフモデルを導入し、デコーディング問題（ビタビ）、プロファイルHMM、バウム・ウェルチ学習を含むパラメータ推定を扱う。第11章は、古生物学を動機となる問いとして、質量スペクトルからのペプチド配列決定と、スペクトルに対するプロテオームの探索を扱う。

主要概念

第1〜3章：複製起点、モチーフ、アセンブリ

• 頻出語とスキュー：過剰に現れるパターンを見つけること、そして鎖間の塩基の偏りを使って複製起点を特定すること。
• 乱択アルゴリズム：網羅的な探索が現実的でない場面で良い解を見つける、乱択モチーフ探索とギブスサンプリング。
• ド・ブラングラフとオイラー路：リードをグラフの辺として表し、ゲノムアセンブリを経路の問題に変えること。

第4〜5章：抗生物質と配列比較

• 分枝限定法：総当たり探索の枝刈り。環状ペプチドの配列決定に応用される。
• スペクトル畳み込み：質量スペクトルから、ありそうなアミノ酸の質量を推定すること。
• 動的計画法：アラインメントを、格子状の有向非巡回グラフにおける最長経路として解くこと。
• 局所、アフィンギャップ、多重アラインメント：異なる生物学的な問いに応じたアラインメントの変種。

第6〜8章：再編成、系統、クラスタリング

• ブレークポイントと反転：ゲノム間の再編成距離を測り、計算すること。
• 距離に基づく系統推定：加法的系統樹、UPGMA、近隣結合法。
• k平均クラスタリング：最適化問題を通じて、発現プロファイルによって遺伝子をグループ分けすること。

第9〜11章：パターンマッチング、HMM、プロテオミクス

• 接尾辞木、接尾辞配列、バローズ・ホイーラー変換：高速なリードマッピングのためのデータ構造。
• 隠れマルコフモデル：ビタビアルゴリズムでデコードされ、バウム・ウェルチ学習で訓練される確率モデル。
• ペプチドの同定：質量スペクトルをペプチドやプロテオームと照合すること。

批判的分析

長所

• まず生物学、アルゴリズムは必要に応じて。 各章は具体的な生物学的な問いから始まり、その問いが求めるときにだけアルゴリズムを展開する。レッスンの題がそれを示している。たとえば第3章では、読者は文字列再構成と2種類のグラフに取り組んでから、オイラーの定理にたどり着く。
• アルゴリズム設計の幅広い概観。 章ごとの組み合わせは、ウォーミングアップの文字列アルゴリズム、乱択、グラフ、総当たりと分枝限定法、動的計画法、組合せ論、系統推定、クラスタリング、文字列索引、確率的手法に及ぶ。学生は計算生物学で使われる主要なアルゴリズムの系統に出会う。
• 練習が組み込まれている。 演習は本文に統合されており、コーディング課題は無料の Rosalind「Bioinformatics Textbook Track」にある。そこには、文字列中のパターンの数え上げからバウム・ウェルチ学習まで、11章にわたって124の問題が掲載されている。
• 無料の補助教材。 5つの章が本書のウェブサイトで読め、すべての章に講義動画が付いている。読者は購入前にこのアプローチを試せるし、教員は著者たちが述べているように、反転授業にこれらの教材を使える。

短所

• プログラミングが必要。 本書はアルゴリズムの実装を中心に組み立てられている。まだどの言語でもプログラムを書けない学生は、学習の多くを担うコーディング課題で苦労するだろう。
• データベースやツールの扱いは少ない。 各章が扱うのはアルゴリズムであり、実務のバイオインフォマティシャンが日々使うデータベース、ソフトウェアパッケージ、アノテーションのワークフローではない。バイオインフォマティクスの資源の使い方を学ぶ授業には、別のテキストが必要である。
• 章が長く、話が回り道をする。 物語を軸にし、1章に多くのレッスンを含む方式は時間がかかる。あるアルゴリズムを手早く調べたい読者には、従来の教科書より遅く感じられるかもしれない。

コースにおける位置づけ

このリストのバイオインフォマティクスの本のなかで、Compeau と Pevzner はアルゴリズム中心で、プログラミングに基づく入門書である。Arthur Lesk の Introduction to Bioinformatics は、この分野を、データと計算で答えられるゲノム、タンパク質、進化についての問いとして示し、ソフトウェアを書くことよりも結果の解釈を重視する。そのため良い補完となる。Lesk は手法が何に使われるかを説明し、Compeau と Pevzner は手法が内部でどう動くかを示す。Baxevanis、Bader、Wishart の Bioinformatics は、実際に使われるデータベース、アルゴリズム、解析手法についての編著の教科書で、本書が扱わないツールの側面をカバーする。Zvelebil と Baum の Understanding Bioinformatics は、タンパク質構造やシステムの話題も含む、より幅広い学際的な解説である。

Uri Alon の An Introduction to Systems Biology は、配列解析から生物学的回路の定量的モデルとその設計原理へと移る。別の主題であり、本書のようなアルゴリズムの授業のあとに学ぶのが最もよい。

本書の使い方

本書は、プログラミングのできる生物学の学生と、生物学の問題への入門を求めるコンピュータサイエンスの学生に向いている。何らかの言語での基本的なプログラミングと、学校レベルの数学が必要である。第2章と第10章には確率の知識が役立つ。

• 無料で始める： ウェブサイトで第1〜5章を読み、スタイルを確かめる。第1章（文字列アルゴリズム）、第3章（グラフ）、第5章（動的計画法）は、多くの授業の中核である。
• 中心となる道筋： 第1、3、5、7、9章で、パターン探索、アセンブリ、アラインメント、系統推定、リードマッピングという必須の道具がそろう。
• 関心に応じて： 確率的手法なら第2章と第10章、質量分析とプロテオミクスなら第4章と第11章、ゲノム再編成なら第6章、発現データとクラスタリングなら第8章。
• 問題を解く： 各章の Rosalind Textbook Track の問題は、読み終えてからではなく、読みながら解く。レッスンがわかりにくいときは講義動画を見る。

修了証や本文内の自動採点演習を望む学生は、有料のインタラクティブ版や関連するオンライン講座を利用できる。独学なら、印刷版と Rosalind で十分である。