生物信息學演算法導論

1. 生物信息學演算法導論的內容提要

全書強調的是演算法中思想的運用，而不是對表面上並不相關的各類問題進行簡單的堆砌。體現了以下特色：闡述生物學中的相關問題，涉及對問題的模型化處理並提供一種或多種解決方案；簡要介紹生物信息學領域領軍人物；饒有趣味的小插圖使得概念更加具體和形象，方法更容易被領會，激勵學生學習的興趣並鼓勵他們加入到生物信息學研究工作中來。
書中的大量論述表明：較少的幾種設計思想就能解決大量的生物學難題。

2. 判別分析方法、聚類分析方法、HMM方法簡介

三個學分的通選課,A類
曾經作為力學系的限選課開出.
歡迎大二以上有數理基礎的同學選修.

《生物信息學演算法導論》課程介紹
課程英文名：Introction to Computational Biology
課程號：00331440
開課單位：力學系、理論生物學中心
開課教師：朱懷球
上課時間：每周四晚
上課地點：理教201
選課地點、時間：三教103，9月5日星期五上午8:00～12:00

一、課程設置目的及主要內容
隨著人類基因組計劃的不斷推進，運用理論模型和數值計算研究生命科學，已經成為一門 最吸引人的新興學科，是當今生命科學和自然科學的核心領域和最具活力的前沿領域之一 。生物信息學/計算生物學以現代分子生物學數據作為主要研究對象，發展理論模型和計算方法，揭示以基因組信息結構為主的生物復性，以及生長、發育、遺傳、進化等生命 現象的根本規律。本課程主要為具有數理背景的大學二年級以上本科生（含大二）和相關領域的研究生開設，偏重理論建模和演算法的學習。首先介紹當代生命科學的發展和現狀， 然後介紹計算生物學中幾種主要的研究方法，包括統計學方法、Markov過程模型、資訊理論方法、機器學習方法等，並結合當今生物信息學領域的最新進展，討論上述各種方法實際研究中的應用（包括基因序列信息分析、基因預測、分子進化及系統發育樹和蛋白質調控網路等重要問題）。 本課程注重學科交叉、融合，以介紹思想、方法為主，深入淺出，避免繁瑣、抽象的數學形式，啟發學生綜合運用數學、物理、工程科學和計算機知識的能力，拓寬知識面，了解學科前沿和最新進展，培養跨越生命科學、計算科學、數理科學等不同領域的「大科學」素質和意識，為今後選擇新興交叉學科領域進行深造奠定基礎。

二、課程大綱

第1章 緒論 （1學時）
從人類基因組計劃說起
計算生物學——後基因組時代的呼喚
計算生物學主要研究內容和方法
以生命科學為核心的「大科學」

第2章 生物學基礎 （5學時）
What is life？——從薛定鍔的思考到「雙螺旋」的發現
生命的演化和分類
生命的分子組成
遺傳的分子基礎
基因組與基因結構

第3章 生物信息資料庫和計算生物學主要問題 （3學時）
生物信息資料庫簡介
計算生物學主要問題之一：序列比對
計算生物學主要問題之二：核酸和蛋白質結構與功能預測
計算生物學主要問題之三：基因組序列分析
計算生物學主要問題之四：功能基因組相關信息分析

第4章 計算生物學的統計學方法 （10學時）
統計方法的基本概念
回歸分析方法及其應用
判別分析方法及其應用
聚類分析方法及其應用

第5章 計算生物學的Markov過程模型 （6學時）
Markov過程的基本概念
隱Markov模型（HMM）的基本原理
HMM模型的計算生物學應用

第6章 生物學的資訊理論基礎 （6學時）
信源與信息熵
離散信道與平均互信息
編碼理論簡介
生物遺傳信息的傳遞

第7章 遺傳演算法和人工神經網路方法簡介 （8學時）
遺傳演算法的基本原理和方法
遺傳演算法與人工生命模型
人工神經網路的基本概念
人工神經網路的模式識別演算法

第8章 生物信息學/計算生物學的若乾重要問題 （6學時）
基因預測演算法和軟體
分子進化與系統發育
基因調控網路

三、本課程考試方式

在老師指導下，結合所講內容進行學科調研，要求同學在期中、期末分別完成兩次調研論 文，論文題目不限。

3. 生物信息學演算法導論的目錄

1 緒論
2 演算法與復雜性
2.1 演算法是什麼？
2.2 生物學演算法與計算機演算法
2.3 找錢問題
2.4 正確的與錯誤的演算法
2.5 遞歸演算法
2.6 迭代演算法與遞歸演算法的比較
2.7 快速演算法與慢速演算法的比較
2.8 大O記號
2.9 演算法設計技術
2.10 易處理與不易處理問題的比較
2.11 附註
人物天地：Richard Karp
2.12 問題
3 分子生物學簡介
3.1 生命是由什麼組成的？
3.2 什麼是遺傳物質？
3.3 基因是干什麼的？
3.4 哪些分子編碼基因？
3.5 DNA的結構是怎樣的？
3.6 在DNA和蛋白質間傳遞信息的物質是什麼？
3.7 蛋白質是由什麼組成的？
3.8 我們該如何去分析DNA？
3.9 一個物種的個體差異是怎樣產生的？
3.10 不同物種間有怎樣的差異？
3.11 為什麼要搞生物信息學？
人物天地：Russell F.Doolittle
4 窮舉搜索
4.1 限制酶切作圖
4.2 不實用的限制酶切作圖演算法
4.3 一個實用的限制酶切作圖演算法
4.4 DNA序列上的調控基序
4.5 序列剖面
4.6 基序發現問題
4.7 檢索樹
4.8 發現基序
4.9 發現一個中間字元串
4.10 附註
人物天地：Gary Stormo
4.11 問題
5 貪婪演算法
5.1 基因組重排
5.2 反序排序法
5.3 近似演算法
5.4 斷點：貪婪的另一面
5.5 貪婪方法與基序發現
5.6 附註
人物天地：David Sankoff
5.7 問題
6 動態規劃演算法
6.1 DNA序列比較的力量
6.2 找錢問題重述
6.3 曼哈頓遊客問題
6.4 編輯距離與聯配
6.5 最長共同子序列
6.6 全局序列聯配
6.7 得分聯配
6.8 局部序列聯配
6.9 缺口罰分聯配
6.10 多重聯配
6.11 基因預測
6.12 基因預測的統計方法
6.13 基於相似性的基因預測方法
6.14 剪接聯配
6.15 附註
人物天地：Michael Waterman
6.1 6 問題
7 分而治之演算法
7.1 排序問題的分治法
7.2 空間效率高的序列聯配
7.3 模序聯配和四個俄羅斯人的加速法
7.4 在亞二次時間內構建聯配
7.5 附註
人物天地：Webb Miller
7.6 問題
8 圖演算法
8.1 圖
8.2 圖與遺傳學
8.3 DNA測序
8.4 最短超字元串問題
8.5 作為可選擇測序技術的DNA陣列
8.6 雜交測序
8.7 SBH與Hamilton路問題
8.8 SBH與歐拉路問題
8.9 DNA測序中的片段裝配
8.10 蛋白質測序和鑒定
8.11 肽測序問題
8.12 譜圖
8.13 基於資料庫搜索的蛋白質鑒定
8.14 譜的卷積
8.15 譜聯配
8.16 附註
8.17 問題
9 組合模式匹配
9.1 重復序列發現
9.2 哈希表
9.3 精確模式匹配
9.4 關鍵詞樹
9.5 後綴樹
9.6 啟發式相似性搜索演算法
9.7 近似模式匹配
9.8 BLAST：依靠資料庫的序列比較
9.9 附註
人物天地：Gene Myers
9.10 問題
10 聚類和樹
10.1 基因表達分析
10.2 系統聚類
10.3 k-均值聚類
10.4 聚類和有瑕團
10.5 進化樹
10.6 基於距離的樹重構
10.7 由可加矩陣重構樹
10.8 進化樹與系統聚類
10.9 基於字元的樹重構
10.10 小簡約問題
10.11 大簡約問題
10.12 附註
人物天地：Ron Shamir
10.13 問題
11 隱馬氏模型
11.1 CG島和「公平賭場」
11.2 公平賭場和隱馬氏模型
11.3 解碼演算法
11.4 隱馬氏模型參數估計
11.5 剖面隱馬氏模型聯配
11.6 附註
人物天地：David Haussler
11.7 問題
12 隨機化演算法
12.1 排序問題回顧
12.2 吉布斯抽樣
12.3 隨機投影
12.4 附註
12.5 問題
參考文獻
索引