LF mapping
? LF (last-first) mapping: 字符在最后一列与第 一列的出现次数位置保持不变
SA seq
06 $acaacg 0
1 2 a a c g $ a c 1 $0
20 acaacg$ 2
a1
33 acg$aca 3
4 1 c a a c g $ a 4 c4
5 4 c g $ a c a a 5 g6
? 恢复原序列
aacg $acaacg aacg$ac acaacg$ 3acg$aca caacg$a 5cg$acaa 6g$acaac
caacg $acaacg 1aacg$ac acaaCg$ 3acg$aca caacg$a 5cg$acaa 6g$acaac
LF[5]=3, L[3]=a i=3
65 g$acaac 6
LF mapping
? LF[i] = C[L[i]] + ri，C[L[i]]是L[i]在BWT中的起 始位置，ri是L[i]出现的次数
? LF[0] = C[L[0]] + 1 = 6 + 1 -1 = 6 ? LF[1] = C[L[1]] + 1 = 4 + 1 -1= 4 ? LF[2] = C[L[2]] + 1 = 0 + 1 -1= 0 ? LF[3] = C[L[3]] + 1 = 1 + 1 -1= 1 ? LF[4] = C[L[4]] + 2 = 1 + 2 -1= 2 ? LF[5] = C[L[5]] + 2 = 1 + 3 -1= 3 ? LF[6] = C[L[6]] + 2 = 4 + 2 -1= 5 ? LF[] = [6 4 0 1 2 3 5]
短序列片段
? 长度：35 - 120bp
? 碱基测序质量：Phred Quality Score
? ASCII表示 ? P是base-calling错误率
Q ? ?10log10 P
ASCII码表
内容
? 短片段序列 ? 短片段Mapping ? 基因型估计 ? 关联分析
短片段Mapping
? 输入
速，但对于空隙和错配，缺乏敏感度
BW Transform
?X→B
acaacg$
$acaacg aacg$ac acaacg$ acg$aca caacg$a cg$acaa g$acaac
BWT
gc$aaac
Burrows-Wheeler Matrix (BWM)
BW Transform
? 循环转换
? +HWI-EAS209_0006_FC706VJ:5:58:5894:21141#ATCACG/1 efcfffffcfeefffcffffffddf`feed]`]_Ba_^__[YBBBBBBBBBBRTT\]][]ddd d`ddd^dddadd^BBBBBBBBBB%的氨基酸，能否说2PAM矩阵平均改变2%
? 用Blast在GenBank中查询序列 GAATTCCAATAGA ，命中了什么数据库序列
? S和t的长为l的比对，把该比对拆成两部分，一 个从列1到列k，另一个从列k+1到l。计分系统 的什么性质保证对任意的k整个比对的计分是 其部分比对计分的和
LF[3]=1, L[1]=c i=1
acaacg $acaacg 1aacg$ac acaacg$ 3acg$aca 4caacg$a 5cg$acaa 6g$acaac
LF[1]=4, L[4]=a i=4
BW Transform
? BW Transform是可逆的 ? 时间复杂度为O(n) ? 重构时间复杂度为O(n)，空间复杂度为O(n)
? 一个参考基因组 ? 大量(10-1000M)的25~100bp的reads
? 输出
? 成功map到参考基因组上的每一个位点信息 ? 未成功map比例
短片段Mapping
? 问题
? 不唯一位置 ? 不确切位置
? 方法
? 哈希表：迅速，需要完美匹配 ? 阵列扫描：无法处理空隙 ? 动态规划：Indels，最优，但速度慢 ? Burrows-Wheeler Transform (BW Transform): 快
acg $ a c a ac g a a c g $a c a c a a cg $ a c g $ ac a c a a c g$ a 5c g $ a ca a 6g $ a c aa c
X=L[0] i=0
LF[0]=6, L[6]=c i=6
LF[6]=5, L[5]=a i=5
BW Tranform 重构
BLAST
BLAST
BLAST
二代测序数据分析
2019/9/25
测序数据分析流程
? 短片段序列 ? 短片段Mapping ? 基因型估计 ? 关联分析
短序列片段(fastq) Mapping (BWA, Bowtie)
基因型估计 (Bayes) 关联分析
短序列片段
? Fastq格式
? 文本文件 ? 包含短片段序列（reads）和碱基测序质量
0a c a a c g $ 1 caa c g$a 2 aac g $ac 3 acg $ aca 4 cg$ a caa 5 g$a c aac 6 $ac a acg
? 字典方式排序
6 $ ac a acg 2 a ac g $ac 0 a ca a cg$ 3 a cg $ aca 1 c aa c g$a 4 c g$ a caa 5 g $a c aac
? 示例
? HWI-EAS209_0006_FC706VJ:5:58:5894:21141#ATCACG/1 TTAATTGGTAAATAAATCTCCTAATAGCTTAGATNTTACCTTN NNNNNNNNNTAGTTTCTTGAGATTTGTTGGGGGAGACATTTT TGTGATTGCCTTGAT
BW Transform 重构
? 恢复原序列: X = L[ LF(i) ] + X; i = LF(i)
g $acaacg aacg$ac acaacg$ acg$aca caacg$a cg$acaa g$acaac
cg $a c aacg aa c g$ac ac a acg$ ac g $aca ca a cg$a cg $ acaa 6g$ a caac