基础与数学
生物信息学的很多问题都可以抽象成对序列、图、矩阵和概率模型的计算。
但在进入算法之前，先要明确几个基本对象：
- 序列是什么；
- 读段和参考基因组是什么；
- coverage、错误模型和坐标系统怎样影响后续分析；
- 注释和特征区间如何把序列映射到生物学对象；
- 为什么图模型、动态规划和概率模型会反复出现。
这一部分在全站中的位置
Section titled “这一部分在全站中的位置”这一节是整站的对象层与方法入口。后面的索引、比对、组装、变异检测、转录组分析几乎都依赖这里的术语和直觉。
为什么这一节重要
Section titled “为什么这一节重要”如果这层基础不稳，读者很容易在后面的页面里只记住工具名和术语，而无法理解：
- 输入输出到底对应什么对象；
- 某个方法为什么适合这个问题；
- 错误和不确定性从哪里进入流程。
推荐阅读顺序
Section titled “推荐阅读顺序”- 生物信息学中的基础对象
- 序列、字符串与坐标系统
- 测序 reads、coverage 与错误模型
- 参考基因组、坐标系统与注释
- 概率、图与动态规划预备
- 算法与复杂度
- 图算法基础
- 字符串模式匹配
- 分治算法基础
- 近似算法
- 穷举搜索与分支定界
- 基因组重排
- 动态规划基础
- 随机化算法
起点
生物信息学中的基础对象
先建立 DNA、RNA、蛋白质、基因组、reads 和注释等基本对象的整体认识。
进入子主题 基础
序列、字符串与坐标系统
把生物对象和字符串表示、坐标系、区间概念连接起来。
进入子主题 核心
测序 reads、coverage 与错误模型
理解原始观测如何影响后续比对、组装、变异检测与定量。
进入子主题 关键
参考基因组、坐标系统与注释
建立参考版本、注释层级与坐标系统的基本直觉。
进入子主题 衔接
概率、图与动态规划预备
为后续比对、组装和概率模型页建立共通数学语言。
进入子主题 总纲
算法与复杂度
从穷举、DP、图算法、索引到随机化方法，建立整站的算法主线。
进入子主题 算法
图算法基础
BFS、DFS、最短路径与连通性，在组装、系统发育树和序列比对中的应用。
进入子主题 算法
字符串模式匹配
KMP、Boyer-Moore、Rabin-Karp，在序列比对、motif 搜索和数据库检索中的应用。
进入子主题 算法
分治算法基础
归并排序、快速排序、最近点对，在序列排序、树构建和距离计算中的应用。
进入子主题 算法
近似算法
处理 NP-hard 问题的实用策略，在系统发育树、Motif 发现和序列比对中的应用。
进入子主题 算法
穷举搜索与分支定界
理解组合优化问题的基线方法，以及如何通过剪枝加速搜索。
进入子主题 应用
基因组重排
理解物种进化中的基因组结构变化，包括同源区块、反转距离和贪心算法。
进入子主题 算法
动态规划基础
从曼哈顿游客问题到序列比对，理解DP的核心思想、递推关系和表格填充方法。
进入子主题 算法
随机化算法
通过引入随机性在巨大搜索空间中更聪明地探索，包括快速排序、Gibbs Sampling 和随机投影。
进入子主题 算法
编辑距离与序列比对
理解字符串相似性的度量，包括编辑距离、全球/局部比对和得分矩阵。
进入子主题 应用
基因预测
从基因组序列中识别基因的方法，包括统计和相似性搜索方法。
进入子主题