Bioinformatics Algorithms: An Active Learning Approach（生物資訊演算法：主動學習取向）

引用

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

章節概要

本書網站列出了十一章，每章都以一個生物學問題為標題，並與一類演算法相配。作者這樣描述其方法：每章從一個核心生物學問題出發，逐步發展出回答該問題所需的演算法技巧。數百道練習在需要時直接嵌入正文，讀者還可以在免費的 Rosalind 平台上完成自動評分的程式挑戰。網站免費提供第1–5章的閱讀，並為每一章配有授課影片；正文的互動式版本另行販售。

第1章：DNA複製從基因體的何處開始？

授課頁面稱這一章為「演算法暖身」。它尋找細菌基因體的複製起點：各課從起點區域中「隱藏的訊息」（高頻詞）談起，經過複製的不對稱性、前後兩條半股之間的偏斜（skew）和近似模式比對，最後嘗試在大腸桿菌中找到DnaA盒。尾聲討論起點預測中的複雜情況。

第2章：哪些DNA模式扮演分子時鐘的角色？

本章透過模體搜尋——尋找基因調控區共有的短調控模式——來介紹隨機化演算法。它從「是否存在『時鐘』基因」這個問題出發，解釋為什麼模體搜尋比看起來更難、如何為模體評分，以及它與尋找中位字串的關聯；接著依序講解貪婪模體搜尋、隨機化模體搜尋和吉布斯抽樣。尾聲探討結核桿菌如何「冬眠」。

第3章：如何組裝基因體？

基因體組裝是講授圖演算法的場景。本章從把定序比作「爆炸的報紙」以及字串重建問題談起，比較重疊圖和德布魯因圖，然後回到柯尼斯堡七橋問題和歐拉定理，建構尋找歐拉迴路的演算法，最後討論讀段對（read-pairs），並在尾聲中討論真實定序資料帶來的問題。

第4章：如何定出抗生素的序列？

本章透過質譜法測定抗生素胜肽的序列來介紹窮舉演算法和分支定界法。各課內容包括抗生素的發現、細菌如何繞過中心法則合成抗生素（非核糖體胜肽）、用窮舉法和分支定界法測定環狀胜肽序列、胺基酸超過20種的情形，以及譜捲積，最後從模擬譜轉向真實譜。

第5章：如何比較生物序列？

這一章是全書對動態規劃的入門。它從非核糖體密碼談起，透過曼哈頓遊客問題和找零問題引入序列比對，再推廣到有向無環圖中的最長路徑和回溯；接著討論評分、局部比對、其他比對變體、空隙罰分、節省空間的比對以及多重序列比對。

第6–8章：人類基因體中有脆弱區域嗎？；哪種動物把SARS傳給了我們？；酵母是如何成為釀酒師的？

這幾章把生物學問題分別與組合演算法、演化樹重建和分群相結合。第6章討論基因體重排（「把人變成小鼠」）、反轉排序、斷點定理以及腫瘤基因體中的重排。第7章從距離矩陣建構演化樹，包括加成性親緣關係、UPGMA、鄰接法和小簡約問題。第8章利用酵母的基因表現資料，介紹作為最佳化問題的分群、k平均的勞埃德演算法、軟k平均和階層式分群。

第9–11章：如何定位致病突變？；為什麼生物學家至今仍未研發出HIV疫苗？；暴龍只是一隻大雞嗎？

最後幾章涉及組合式模式比對、隱藏式馬可夫模型和計算蛋白質體學。第9章講解利用字典樹、後綴樹、後綴陣列和Burrows–Wheeler轉換進行讀段比對。第10章透過「作弊賭場」和HIV分類引入隱藏式馬可夫模型，內容包括解碼問題（維特比演算法）、輪廓隱藏式馬可夫模型以及參數估計（包括Baum–Welch學習）。第11章以古生物學為引子，討論從質譜測定胜肽序列以及用質譜搜尋蛋白質體。

核心概念

第1–3章：複製起點、模體與組裝

• 高頻詞與偏斜：尋找過度出現的模式，並利用兩股之間核苷酸的不平衡來定位複製起點。
• 隨機化演算法：隨機化模體搜尋和吉布斯抽樣，在窮舉搜尋不可行時找到好的解。
• 德布魯因圖與歐拉路徑：把讀段表示為圖的邊，使基因體組裝變成路徑問題。

第4–5章：抗生素與序列比較

• 分支定界法：對窮舉搜尋進行剪枝，應用於環狀胜肽定序。
• 譜捲積：從質譜推斷可能的胺基酸質量。
• 動態規劃：把比對問題當作格狀有向無環圖中的最長路徑來求解。
• 局部比對、仿射空隙比對與多重序列比對：針對不同生物學問題的比對變體。

第6–8章：重排、親緣關係與分群

• 斷點與反轉：度量和計算基因體之間的重排距離。
• 以距離為基礎的親緣關係推論：加成性親緣關係、UPGMA和鄰接法。
• k平均分群：透過最佳化問題，依表現譜把基因分組。

第9–11章：模式比對、隱藏式馬可夫模型與蛋白質體學

• 後綴樹、後綴陣列與Burrows–Wheeler轉換：用於快速讀段比對的資料結構。
• 隱藏式馬可夫模型：以維特比演算法解碼、以Baum–Welch學習訓練的機率模型。
• 胜肽鑑定：把質譜與胜肽和蛋白質體進行比對。

評析

優點

• 生物學先行，演算法依需要引入。 每章都從一個具體的生物學問題出發，只在問題需要時才發展演算法。各課標題體現了這一點：例如在第3章中，讀者先學習字串重建和兩種圖，然後才接觸歐拉定理。
• 對演算法設計的廣泛概覽。 各章所配的演算法涵蓋暖身用的字串演算法、隨機化演算法、圖演算法、窮舉與分支定界、動態規劃、組合演算法、親緣關係推論方法、分群、字串索引和機率方法。學生會接觸到計算生物學中使用的主要演算法類別。
• 練習融入其中。 練習融入正文，程式挑戰則放在免費的 Rosalind「Bioinformatics Textbook Track」上，那裡列出了涵蓋十一章的124道題，從計算字串中的模式到Baum–Welch學習。
• 免費的輔助材料。 五章可在本書網站上閱讀，每章都配有授課影片。讀者可以在購買前試用這種方法，教師也可以像作者所描述的那樣，用這些材料進行翻轉教室教學。

局限

• 需要程式能力。 本書圍繞演算法實作展開。還不會用任何語言寫程式的學生，在承擔大部分學習任務的程式挑戰上會很吃力。
• 很少涉及資料庫和工具。 各章講的是演算法，而不是生物資訊從業人員日常使用的資料庫、軟體套件和註解流程。講授如何使用生物資訊資源的課程需要另選教科書。
• 章節冗長，敘述迂迴。 以故事為主線、每章包含許多課的方式比較費時。想快速查閱某個演算法的讀者可能會覺得它比傳統教科書慢。

在課程中的定位

在本書單的生物資訊學書目中，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 就足夠了。