【学习笔记】山东大学生物信息学-05 高通量测序技术介绍 + 06 统计基础与序列算法（原理）

课程地址 ：山东大学生物信息学

文章目录

• 五、高通量测序技术介绍（没有干货）
• 六、统计基础与序列算法（原理）
• • 6.1 贝叶斯公式及其生物学应用
  • 6.2 二元预测的灵敏度和特异度
  • 6.3 基本序列算法

---

五、高通量测序技术介绍（没有干货）

5.1 高通量测序技术在精准医学中的应用

1. Identify new disease genes 疾病基因的筛查
2. Genomics-based diagnostics/screening 遗传病诊断/筛查
3. Precision treatment 精准治疗

5.2 生物信息学面临的挑战

• 数据规模庞大
• 数据类型复杂
• 方法学不成熟
• 技术门槛偏高
• 可重复性不强

● 测序偏差 Sequencing bias/errors

454 测序 ：对于连续重复的 homopolymer，测不准

Illumina ：簇达不到理想的数目 ，导致信号弱，无法准确识别；一个簇内测序反应不同步 ，导致信号冲突，碱基识别错误；高 GC 区往往测序覆盖度低 ，也会导致测序偏差。

PacBio ：长 reads 测序（5k-10k），准确度低。

● 校正偏差 Possible solutions

1. Deep sequencing
2. Statistical evaluation
3. Error correction

● Speed and RAM 计算速度与内存

• 海量数据的计算和挖掘成为主要瓶颈
• CPU-intensive jobs (read mapping, metagenomics)
• RAM-intensive jobs (genome assembly)
• 计算机群（公共计算平台）

5.3 从头测序
de novo sequencing 从头测序 ：得到的序列是片段化、零碎的（几百 bp），重复序列 拼接不好。

5.4 重测序 （没有视频）

5.5 转录组测序 mRNA-seq

5.6 表观基因组学 ChIP-seq

5.7 猛犸象基因组测序计划

5.8 古基因组学面临的挑战 ：DNA damage，基因组存在高度不稳定性

5.9 古基因组学研究中的生物信息技术

• De novo assembly
  Find overlapping reads
  Merge good pairs of reads into longer contigs
  Link contigs to form supercontigs
  Generate consensus sequences

• Comparative assembly
  Using a reference genome （现存大象基因组作为参考基因组） to assemble (or layout) the reads (or contigs) of the target genome.

六、统计基础与序列算法（原理）

6.1 贝叶斯公式及其生物学应用

贝叶斯公式

通常，事件 A 在事件 B 发生的条件下发生的概率，与事件 B 在事件 A 发生的条件下发生的概率是不一样的。然而，这两者是有确定的关系，贝叶斯公式 就是描述这种条件关系概率 的公式。

设 A、B 是两个事件，
在事件 B 发生的条件下，事件 A 发生的概率 是 P(A|B) =P(A∩B)/P(B)；
同样的，在事件 A 发生的条件下，事件 B 发生的概率 是 P(B|A)=P(A∩B)/P(A)。
A、B 的联合概率公式 为 P(A∩B)= P(A|B) P(B)= P(B|4)P(A)
上式两边同除以 P(B)，若 P(B) 是非零的，我们可以得到贝叶斯公式 ：P(A|B)=P(B|A)P(A)/P(B)

贝叶斯公式延展 ：

贝叶斯公式的应用

贝叶斯公式的生物学应用

• 参考视频：贝叶斯公式及其生物学应用-03 P115
  
  
  

6.2 二元预测的灵敏度和特异度

• 灵敏度 Sensitivity = TP/ (TP+FN) 真阳性率 （宁可选错也不漏选）
• 特异度 Specificity = TN/ (TN+FP) 真阴性率 （宁可不选也不选错）

生物学中灵敏度和特异度的应用案例

● 富亮氨酸重复序列的预测

富亮氨酸重复序列 (LRR) 是一个氨基酸片段，广泛存在于病毒、原核生物与真核生物的上万个已知的蛋白质中，往往参与蛋白质与蛋白质或（非蛋白质）的相互作用，在细胞黏连、信号传导、血小板凝聚、细胞外基质聚集、神经系统发育、RNA 加工、病毒入侵及免疫应答等过程中起到了关键性。它往往在一个蛋白质分子中首尾相接的重复几遍甚至几十遍 ，当然，每次重复的序列并非完全相同 。

LRR 具有一个特征性序列模板LxxLxLxxNxL。

从目前己知的所有 Toll 样受体蛋白质序列 (>2500) 中半手动的精确划分出 5 万多个单个的 LRRs 。把这 5 万多个 LRRs 作为标准数据组，从中构建出一个预测模型 ，来详细描述一个 LRR 的序列特征并可预测一个蛋白质序列中是否含有 LRR ，有的话每个 LRR 的起始位置在哪里。

通过位点特异性加权矩阵 (Position-Specific Weight Matrix)，构建预测模型： 将 5 万多个 LRRs 序列纵向罗列出来，得出所有序列上各种氨基酸在 LRR 各位点上出现的频率，与 LRR 的特征性序列模板 LxxLxLxxNxL 一致。

预测一条序列是否含有 LRR 序列 ：
Score = 每个点出现该氨基酸的频率之和。因此得分越高，是 LRR 的可能性就越大。
Cutoff Score 根据二元预测的灵敏度和特异度得到 。
在一定的范围内一个个试 Cutoff Score，在不同的 Cutoff Score 下，计算模型的灵敏度和特异度（例如取灵敏度和特异度曲线的交点为 Cutoff Score）。

6.3 基本序列算法

• 序列算法 ：为研究生物序列 而开发出的计算复杂度尽可能低的算法。比如，如何从序列中快速准确的找到重复序列。
• 生物序列 ：包括核酸序列、蛋白质序列或其他由生物问题转化而来的数字串或字符串。

后缀树

• 后缀 就是包含最后一个字符的子序列。最后一个字符后面还要加上一个 $ ， 表示结尾。

• 后缀 $ 是序列 S 最短的一个后缀 。

• 一个序列的所有后缀数 等于包括 $ 在内的序列的长度。
  

• 后缀树 ：用一个序列 所包含的所有后缀 构成的树。

● 画后缀树 ：

• 1、先画 1 号序列，从根到叶画一条枝，枝上标记序列；

• 2、画 2 号序列，看有没有以 2 号序列的首字母 D 开头的枝，没有就另起一枝。

• 3、画 3 号序列，有以 SD 开头的序列，之后分枝把后面的序列写完。
  

• 4、以此类推，画出序列的所有后缀。
  

后缀树的功能

字符串 S=SDSDFSDFG

功能 1: 查找字符串 s 是否在字符串 S 中 （即 判断 s 是否是 S 的子序列）。
方法：从树根开始，与 s 的字符逐一比对。（只需要比对 s 的长度 次即可以得出结果。）
s1=DFSD （在！)
s2=SDFD （在不在？)

功能 2: 查找字符串 s 在字符串 S 中的重复次数
方法：从树根开始，按照功能 1 的方法找到 s，然后看 s 之后有几片树叶 ，则重复几次。

功能 3: 找字符串 S 中的最长重复子序列
方法：找到从树根到所有内节点 （非叶片）的子字符串，从中找到最长的 。

$ 的作用：如果某一个后缀 是另一个后缀的前缀 ，那么需要用 $ 标识出一个独立的叶片。

最高分-子序列

● 最短原则 ：在几个子序列同时拥有最高分 时，如果某一个完全包含在另一之内，则只返回被包含的 那一个。例如，下图序列有 2 个最高分子序列。

• 生物学应用：
  (1) 预测蛋白质序列跨膜区域（疏水片段） 。根据氨基酸的亲疏水性不同，将字符串序列转化为实数序列，疏水氨基酸 [0,5]， 亲水氨基酸 [-5,0]。
  
  （2）预测 DNA 序列中富含 GC 的区域 。如寻找 CpG 岛。
  

• Naive 算法：按照其算法原理，计算一次 f(i,j) 需要计算 n3步。
  ◆ 通常一个算法的计算复杂度至少要达到 n 2以下，才有可能被实际应用。否者，随着 n 的增大，计算量会超出目前的计算能力以及可接受的计算时间。因此，最高分子序列问题，不能用 Naive 算法。
  

• 更高效的算法：
  动态算法 的总运算步骤为: O(n2)
  分而治之法 的总运算步骤为:O(nlogn)
  聪明算法 的总运算步骤为: O(n)

---