生物信息学算法导论

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 问题
参考文献
索引