序列比对
一、记分矩阵
核苷酸替换矩阵
| 类型 | 描述 | 效果 |
|---|---|---|
| 等价矩阵 | 相同核苷酸之间得1分，不同得0分 | 一般用于理论计算，实际使用效果差 |
| 转换-颠换矩阵 | 转换即嘌呤(A/G)之间替换和嘧啶(T/C)之间替换、颠换即嘌呤与嘧啶之间替换 | 一般转换频率高于颠换，因此转换得-1分 ，颠换得-5分 |
| BLAST矩阵 | 相同得5分，不同得-4分 | 实践经验所得，没有理论依据，效果最好 |
蛋白质的替换矩阵
| 类型 | 描述 | 效果 |
|---|---|---|
| 等价矩阵 | 相同得 1 分，不相同得 0 分 | 一般用于理论计算，实际不适用 |
| 遗传密码矩阵（genetic code matrix, GCM） | 计算一个氨基酸突变为另一个氨基酸所需密码子变化的数目 | 常用于进化距离的计算，绘制进化树，但不适合序列比对 |
| 疏水性矩阵（hydrophobic matrix） | 以疏水性为标准，替换后疏水性变化不大则得分高，反之得分低 | 该矩阵物理意义明确，有一定的理化性质依据，适用于偏重蛋白质功能方面的序列比对。 |
| PAM 矩阵 | ||
| BLOSUM 矩阵 |
回答几个问题 1.记分矩阵的一般原理？ 构建记分矩阵，需要找到一个可以估计任何联配的统计数，使生物学关系最显著的联配统计数最大。
2.为什么记分矩阵的打分值会有所差别？尤其是氨基酸矩阵 氨基酸的种类共20种，其中有一些为相对常见的残基（如A、P、S和T），也有一些相对稀有的残基（如W和Y）。为了反映匹配氨基酸间的生物学和化学关系，对于相对常见的残基匹配得分要低于相对稀有的残基匹配得分 ，同时具有相似性质氨基酸的错配得分设置 + 值，毫不相似的错配取 - 值
二、仿射空位罚分
公式： \[ w_{k}=a+bk \] 1.空位设置罚分a和空位扩展罚分b参数的变化会导致哪些影响？
| a | b | 结果 | 适用范围 |
|---|---|---|---|
| 大 | 大 | 极少插入或缺失 | 适用于非常相关的蛋白质之间的联配 |
| 大 | 小 | 少量的大块插入 Gap连续出现 | 适用于整个功能域可能插入的情况（此时打分值主要与a相关，重点在于有几次插入）此设置最佳！ |
| 小 | 大 | 大量的小块插入 Gap分散 | 适用于亲缘关系较远的蛋白质同源性分析此时打分值主要与b相关，重点在于每次插入的长度） |
参考：《生物信息学》樊龙江第二版，P83
2.对于实际情况，如何选择空位罚分（介绍两种例子）
1）有两条相似的待比对序列，是同源序列，因此它们的功能和结构也相似。其中一条序列结构已知，而另一条未知。想通过序列比对，用已知结构序列作为模版，预测另一个序列的结构。（分散，就要用小的空位设置罚分a和大的空位延伸罚分b）
2）有两条待比对序列，且已知它们大部分区域都是非常相似的，但其中一个序列的功能区，在另一个序列中是缺失的。想要通过序列比对，将另一个序列的功能区找出来。（集中，就要用大的空位设置罚分a和小的空位延伸罚分b）
>参考：山东大学《生物信息学MOOC》
三、PAM矩阵、BLOSUM矩阵
PAM矩阵小细节： 1. PAM1和PAM100
PAM1代表100个氨基酸残基中有1个可接受单点突变，但PAM100不代表100个氨基酸残基都发生了替换，因为100次突变中可能有一个氨基酸残基发生了多次突变又突变回了原来的氨基酸残基，即有些突变是可以相互抵消的。
2. PAM矩阵中最不容易突变的氨基酸
一种氨基酸向其他氨基酸突变是存在难易条件的。取决于残基的化学性质和空间位阻。如Trp(W)色氨酸存在吲哚环结构（空间位阻大）以及Cys(C)半胱氨酸存在巯基（形成硫醚环，共价键强度大）
3. PAM250
PAM250并不是有250%的氨基酸发生突变，氨基酸残基差异并不是随着PAM矩阵后面数字增大而线性变化，虽然PAM1的残基差异为1%，PAM23的残基差异为20%；但PAM80的残基差异为50%，PAM250的残基差异为80%
PAM矩阵和BLOSUM矩阵的异同点 相同点 PAM和BLOSUM都是使用了对数概率矩阵来作为最后的打分值 公式为： \[ S^{n}[j,k]=clog_{2}\frac{q_{jk}^{n}}{p_{j}p_{k}} \]
不同点 1. 模型方法：PAM矩阵基于马尔科夫链进行建模，显式地模拟了氨基酸替代过程。而BLOSUM矩阵没有底层的数学模型。 2. 数据来源：PAM矩阵使用全长对齐的相似序列构建，这些序列具有至少85%的相似度，并且被假设在任何位置上仅发生了单个替代。而BLOSUM矩阵使用多个序列的局部保守区域（无间隔的块）构建，这些序列在整个长度上并没有高度保守的特征。（PAM250在检测进化距离较远的序列之间是否具有同源性上准确度受限（PAM250是从初始模型中推算而来并不是直接计算），而BLOSUM62是由真实数据产生的（在面对进化距离较远的序列比对中准确率较好）） 3. 数据处理：PAM矩阵通过使用最大简约树上的分支来校正样本偏差，避免频率偏差。而BLOSUM矩阵则通过聚类方法处理样本偏差并获得不同程度的进化差异。 4. 进化差异参数：在PAM矩阵中，随着进化差异的增加，进化差异参数也增加。而在BLOSUM矩阵中，进化差异参数随着进化差异的增加而减小。（PAM矩阵后面的数字越大，表示序列之间的进化距离越远，而BLOSUM矩阵后面的数字越大，表示序列之间的进化距离越近） 5. 氨基酸性质：PAM矩阵和BLOSUM矩阵对于某些氨基酸之间的相似性和可能引起的替换的处理不同（PAM250认为赖氨酸K与谷氨酸E不太可能发生替换而打分为0；BLOSUM62认为K和E可以发生替换而打分为1） 6. 应用范围：PAM矩阵用于比对和序列相似性评估，而BLOSUM矩阵通常用于蛋白质家族的保守区域分析。
四、最长公共子串与编辑距离
最长公共子串：LCS 是一个在序列集合（通常是两条序列）中找到所有序列中最长的子序列, 通常在全局序列比对结果中去除插入和缺失后的字符串
编辑距离（editing distance）：指的是通过三种编辑操作（插入、缺失和替换）将一条序列转化为另一条序列的最小编辑次数
在只允许插入和缺失而不允许错配的情况下两个字符串的编辑距离可以通过最长公共子序列的长度求的 假定两个字符串 v 和 w，长度分别为 m 和 n。将最长公共子序列记为 \(LC(v,w)\)，而将编辑距离记为 \(DE(v,w)\) \[ DE(v,w)=m+n-2\times LC(v,w) \] 还有一个距离叫汉明距离（hamming distance）：指两个字符串对应位置的不同字符的个数。没有编辑距离的插入缺失和替换的操作，有些时候汉明距离大的序列之间可能具有很高的相似度。
提问：相似性得分和编辑距离的区别与联系？ 区别: 相似性得分是以某种计分规则计算两个序列相似性所得的分值，是为了使得最后打分值最大，在适当的位置插入空位使序列中相同字符对齐，来获得序列之间最大相似度；编辑距离是用来描述两个序列对应位置上差异字符的个数，是为了使得最后编辑次数最少，通过字符替换或插入删除空格将一个序列转变为另一个序列，来获得序列之间最大相似度。 联系: 相似性得分和编辑距离是一对相反的定量描述序列相似性的度量。
五、序列比对算法
Dotlet打点法：大致了解两条序列之间的相似程度，也可以研所某条序列自身可能存在的重复片段
序列之间的打点比较相程度 
序列自身打点探索自身的重复片段 
将两条序列进行横竖比较，比较的次数为两条序列长度之积，即序列m和序列n，比较m×n次 - 连续的对角线和对角线的平行线代表两条序列的相同区域。 - 打点法可以快捷的发现序列中的串联重复序列以及重复次数 - 只需要将一条序列自身横竖比较 - 首先必然会有一条主对角线完全匹配 - 然后通过主对角线一侧且与之平行的片段就是重复区域，长度最小的就是重复序列单元，通过等距平行线的个数可得重复的次数N，（因此，串联重复序列有N+1条，含本身） - 短的重复序列具有高度多态性，且遵循孟德尔共线性遗传规律，所以快速查找某些特定的短的串联重复序列的重复次数可以用于法医学的个体识别或亲子鉴定
六、一致度、相似度和同源性
^3ba492
Identity：两条序列在同一位点上的核苷酸或氨基酸残基完全相同 \[Identity=\frac{相同的碱基或氨基酸}{序列长度}\] Similarity (positive)：两条序列在同一位点上的氨基酸残基的化学性质相似包括相同（计分矩阵中分值>0） \[Similarity=\frac{相同的氨基酸+性质相似的氨基酸}{序列长度}\] Homology可以说A与B的相似性是80%，但不能说A与B有80%同源，因为“同源”是性质，不能量化。
注意！！！ 在进行一致度和相似度的计算时，无论两条序列长度是否相同，都需要先做全局比对，然后根据比对结果及比对长度再计算一致度和相似度
七、BLAST
原理： - 对于待比对或检索的序列，建立词列表或哈希表（word, K-tupple, K-mer） - 确定搜索目标数据库中所有包含与上述词列表中词完全一样的序列（hit） - 对第二步中得到的每一条序列，在匹配区域（hit）向两端以动态规划算法向外延伸，扩展比对区域；得到高得分联配对(HSP)，根据设定的临界比对打分值或E值，列出所有HSP
应用： - 序列比对，例如两序列比对，序列数据库检索 - 推断未知序列功能 - 寻找某个物种同一家族的蛋白质序列 - 寻找物种之间的同源基因/蛋白
基于BLAST算法的工具 
参考：HowTo_BLASTGuide.pdf (nih.gov)
提问 1.为什么在blastx中要对需要查询的核酸序列按照6种开放阅读框翻译？ 答：因为在无法得知翻译起始位点的情况下，核酸翻译的起始位点可能是第1个位点、第2个位点或第3个位点，还有可能在核酸的互补链翻译，这样就有\(2\times 3=6\)种可能的ORF
2.为什么核酸数据库本来就已有注释的信息，在tblastn中还要对核酸数据库进行翻译？ 答：因为核酸数据库中的注释信息并非完全，对于数据库中的核酸序列可能还存在一些未被注释的gene。有些时候，正是这些没有被注释的gene的蛋白质产物与需要查询的蛋白质序列具有相似性
对于蛋白质序列blast，使用的程序有blastp、PSI-BLAST、DELTA-BLAST 对于核酸序列blast，使用的程序有megablast、blastn
1.PSI-BLAST
利用blastp在蛋白质数据库中循环搜索查询蛋白质，所有前一次被psi-blast发现的统计显著蛋白质序列将整合成新记分矩阵（PSSM, Position-Specific Scoring Matrix），通过多次迭代比对，直到不再发现统计显著的新蛋白质。能够寻找到蛋白质家族保守序列，最大限度的找到和查询序列具有同源性的序列（虽然序列相似度很低，但有潜在的同源蛋白质序列）
2.PHI-BLAST
PSI-BLAST属于撒大网搜索，而PHI-BLAST就是精准搜索
PHI-BLAST通过正则表达式的特定模式来进行搜索
例如N{P}[ST]{P}就是查找以N天冬酰胺开头，连接一个不是P脯氨酸的氨基酸，再连接S丝氨酸或T苏氨酸中任意一个，最后再连接一个不是P脯氨酸的氨基酸
正则表达式中 - {}表示除什么以外 -
[]表示其中之一 - x表示任意字符 -
(3,7)表示3到7个某字符
总结：如何选择合适的blast工具 当想要查找亲缘关系较近的序列时，直接使用balstp； 当想要查找亲缘关系较远的序列时，选择PSI-BLAST； 当想要查找符合某一精确模式的序列时，选择PHI-BLAST
3.BLAST数据库选取
核酸数据库， 1. 默认default的是Nucleotide collection(nt)，包含所有来自GeneBank+EMBL+DDBJ+PDB序列，但是排除PAT+EST+STS+WGS+TSA以及phase 0, 1 or 2 HTGS sequences （人类基因组计划(Human Genome Project)早期阶段的未完成和未注释的基因组序列）。是非冗余的，将一致性序列归为一个entry。 2. refseq_rna，包含RefSeq数据库中经过人工审查和校正（NM_, NR_）+ 基因组中预测（XM_,XR）的序列[[3-生物信息学数据库#^969454|NM, NR, XM, XR解释]]
蛋白质数据库 1.
默认default的是Nucleotide
collection(nr)，包含非冗余的GeneBank
CDS翻译的蛋白质序列+RefSeq+PDB+SwissProt+PIR+PRF，不包括PAT，TSA和env_nr（来自环境样本中未知的微生物序列）序列。
2. refseq_protein，包含来自Refseq数据库的蛋白质序列。
^5c3b9e
对于BLAST搜索结果 1. 从Graphic
Summary图形化搜索部分，可以知道balst搜索到了多少个hit（注意，hit不是搜索到的数据库序列，而是高联配得分片段，可能是全长序列也就是全局联配、也可能是某条序列的一部分也就是局部联配）
2.
从Descriptions详细信息列表，可以知道每个高联配得分所在的序列信息，按照E值排序，其中得分值与E值成反比，而一致性与E值无明确的相关性（因为
blast并没有做双序列全局比对，因此一致度是通过搜索到的每条序列与查询序列进行双序列比对得到的）
3.
blast对于亲缘关系较近的序列搜索效果好，但对于亲源关系较远的序列则可能会漏去
blast搜索结果分为三大板块 1. blast任务信息：包括Job Title（任务标题）、RID（blast请求ID）、Program（使用的程序）、Database（查询的数据库）、Query ID（查询ID）、Description（通常是fasta文件的>部分）、Molecule type（分子类型）、Query Length（查询序列长度）、Other report（其他报告，如结果的距离树、多序列比对可视化） 2. 结果筛选：包括Organism物种的筛选（可筛选出包含或排除的物种）、Percent Identity（一致性的百分比）、E value（E值）、Query Coverage（数据库中序列与查询序列的覆盖范围） 3. 结果详细信息：包括Max Score（最大得分）、Total Score(总得分）、Query Cover（覆盖度）、E value（E值）、Per. Ident（一致性百分比）、Acc. Len（该高联配得分对应的数据库中序列的长度）、Accession（序列登录号）
4.其他双序列比对算法
(1) BLAT
BLAT相比于BLAST的优势： - 速度快。BLAT是将庞大的目标数据库索引化，并写入内存可以反复高速调用，时间和空间的数据相关性高，且查询数量越大，BLAT的优势越大 - 可以发现包含内含子的基因位置信息。BLAT不像BLAST将每个同源区域作为单独的比对结果返回，而是将比对结果缝合在一起形成大的联配结果，同时BLAT通过自身算法可以从大联配结果中给出正确的剪切位点，即外显子和内含子的基因位置信息。 ### (2) HMMER 基于隐马尔可夫模型的概型的同源蛋白或核苷酸序列比对和搜索工具。不同于其他的搜索工具，其是以一个HMM概型作为递交序列。例如多序列联配结果可构建HMM概型，单条序列也可通过自身状态和基于标准的氨基酸替换矩阵构建HMM概型
八、双序列比对工具
EMBL全局双序列比对工具PSA
工具介绍：首页包含三个选择，分别是全局比对、局部比对和基因组比对
使用方法（全局比对蛋白质序列）： 1. 输入需要比对的两条序列 2. More
Option设置比对参数，比如可以选择替换矩阵、空位罚分、输出格式 3.
提交Submit 4. 比对结果
|表示上下一致、:表示上下相似、.表示上下不相似
九、比对的统计学显著性
1.典型方法
将两条待比较的序列分别随机打乱，再使用相同的程序与打分函数（或打分矩阵）进行比对，计算这些随机序列的相似性得分。重复这一过程，用\(\mu\)和\(\delta\)分别表示其平均值与标准差。 然后对于原序列比对的得分x，计算\(z=(x-\mu)/\delta\)，z值越小越显著。
2.Karlin-Altschul
Karlin-Altschul的计算公式 \[ E=kmne^{-\lambda S} \] 其中，k为搜索空间，m、n为两条序列的长度，\(\lambda\)为计分系统的特征数，S为设定的联配值 - E值的含义：E值表示不小于比值为S的HSP个数的期望值，反映了在给定数据库大小下,随机得到比对高级别分值至少为S的可能性。 - 序列长度加倍，E值加倍 - E随S变化而显著变化，S增大，E急剧减少 - 搜索不到比值\(\ge S\)的HSP的概率为\(e^{-E}\)，则至少发现一个HSP的概率为\(p=1-e^{-E}\) - 在可能搜索到三个HSP比值\(\ge S\)的情况下，至少发现一个HSP的概率p为0.95（\(E=3,p=1-e^{-3}=0.95\)）
3.经验方法
- 如果两个序列的长度都大于100，在适当地加入空位之后，它们配对的相同率达到25%以上，则两个序列相关；
- 如果配对的相同率小于15%，则不管两个序列的长度如何，它们都不可能相关；
- 如果两个序列的相同率在15%~25%之间，它们可能是相关的。
十、多序列比对
多序列比对联配分为全局联配和局部联配 - 多序列全局联配——启发式算法 - 渐进式全局联配-Clustal, T-Coffee, MUSCLE - 迭代法 - 基于统计模型的方法 - 多序列局部联配——用于分析序列之间的保守性位点，寻找motif - 哈希 - 基于统计的模式识别-最大期望法、吉布斯抽样、HMM ## 1.Clustal系列 第一版Clustal： - 通过计算所有两两序列比对的相似性打分； - 进行UPGMA聚类分析，构建聚类树； - 从最接近的一对序列出发，逐步归并形成比对的聚类，直到所有序列处理完
Clustal W：相比于第一版Clustal的改进 - 序列权重值：下调近似重复或非常相似的序列的权重，反之，上调差异较大的序列 - 根据序列差异的程度，在比对不同阶段使用不同的氨基酸替换矩阵（e.g: PAM100 -> PAM250） - 空位罚分的处理 - 考虑到不同分支分化速率的差异，使用 NJ树，代替UPGMA，结果更稳定
2.T-Coffee
T-coffee与Clustal都属于渐进式比对算法，但T-coffee整合了全局比对Clustal和局部比对Lalign的结果，相比于Clustal有更高的精确度。 T-coffee主要根据序列比对相似性，定义每一对比对上碱基或氨基酸的比对权重，构建初始比对库；合并全局比对与局部比对的权重库；线条越粗，则权重越大，联配的准确度更高，接近多序列联配的最优解。 T-COFFEE有多种变形 - Expresso：给序列加入了结构信息的多序列比对 - M-coffee：把多个比对结果整合成一个 - TM-coffee：专门为穿模蛋白打造的多序列比对 - PSI-coffee：专为远远序列打造的多序列比对 - R-coffee：给RNA序列加入了预测的二级结构信息的多序列比对 - SARA-coffee：给RNA序列加入了三级结构信息的比对
3.MUSCLE
先通过Kmer距离构建距离矩阵，使用UPGMA构建发育树并进行渐进式比对MSA1；将渐进式比对的结果基于Kimura距离再构建一次距离矩阵，并使用UPGMA构建发育树并进行渐进式比对MSA2；通过对第二次发育树进行剪枝计算子树的概型并重新联配得到新的多序列比对结果；基于SP得分高低，来判断是否需要保留或删除，并不断迭代优化直至得到最优联配结果
4.Clustal、T-coffee和MUSCLE三者的区别
- 使用的算法思路不同
- ClustalW使用的是进化距离矩阵进行序列加权的传统算法。
- T-coffee使用的是通过局部和全局比对获得权重评分矩阵的算法。
- MUSCLE使用的是迭代精炼的距离约束树建立算法。
- 比对速度不同
- ClustalW速度较慢。
- T-coffee比ClustalW快,但仍然较慢。
- MUSCLE是目前最快的多序列比对算法之一。
- 比对准确度不同
- ClustalW准确度较低。
- T-coffee通过引入局部比对信息,准确度较高。
- MUSCLE准确度也比较高。
- 处理序列数能力不同
- ClustalW处理几十个序列已经非常慢。
- T-coffee可处理上百个序列。
- MUSCLE可处理上千个序列。
总体来说,MUSCLE兼顾了速度和准确度,是目前最好的选择。T-coffee如果追求准确度则较好。而ClustalW已较少被使用。
5.EM法在MSA中的应用
将多条序列随机排列成一个多序列联配结果——对于联配结果选择一个联配宽度——在这个联配宽度中构建初始PSSM矩阵——利用PSSM对每条序列进行扫描——得到每个位点的匹配概率——由匹配概率得到每个位点的匹配定位概率——由各序列的匹配定位概率生成每个位点碱基数量期望值的新表格——最后期望值最大化——不断重复直到PSSM碱基频率不发生改变 ### MEME MEME就是使用EM进行基序查找的工具，可以对多条核苷酸序列或蛋白质序列进行基序的从头预测 使用方法： - 上传需要分析的序列，且无需提前多序列比对 - 可以设置MEME寻找的motif数量 - 在结果中可以显示按得分高低排名的motif，以及每条序列上motif的所在位置 - 使用FIMO还可以提交基序给其他软件，针对该基序进行相似性搜索
十一、功能域的描述模型
4种功能域描述模型 一致性序列、正则表达式、概型和HMM模型
1. 一致性序列 定义：多序列联配结果中每一列出现最多的碱基或氨基酸构成的序列，它是一条单一序列
2. 正则表达式
定义：把每一列出现的碱基或氨基酸都列出来，形成一个正则表达式
例如一组正则表达式[FY]-[LF]-X-[VL]-X-D-D-[VI]-W，'-'表示氨基酸之间的间隔、'[]'表示位点可能存在的氨基酸类型、单一字母就表示位点只含这一种氨基酸。
可见：只包含位点可能出现的氨基酸种类，但无法得知氨基酸之间的比例
3. 概型 定义：profile是一个类似于PSSM的矩阵，可以包含匹配、错配、插入和缺失等情况。
在PROSITE数据库中，用正则表达式来表示pattern，用概型来表示profile。 - pattern是用来找到短的保守序列即motif区域，通常不超过4到5个残基，由于pattern不会考虑具有相同或相似理化性质的残基，因此找到的序列motif具有高度相似性 - profile则是通常不局限于具有高序列相似性的小区域。相反，profile试图在整个长度上表征蛋白质家族或结构域。 - profile被认为比pattern更敏感、更稳健。因为profile不仅为在基序的给定位置上已经发现的残基提供了区别权重，而且还为尚未发现的残基提供了区别权重。
4. HMM概型 定义：通过构建多序列联配的隐马尔科夫概率模型进行功能域描述。对于 HMM 模型，将一个功能域视为一个从左开始到右结束各个状态（残基匹配或错配、插入和删除）之间的转换。该模型各个“态”之间转换有一个概率，每个“态”所处的具体状态存在一个概率分布，具体状态是未知的。
十二、熵与信息量
熵的计算： \[ H=-\sum P_{i}log_{2}P_{i} \] 信息量的计算： \[ IC=log_{2}(20)-H \] 20指的是20种氨基酸，如果是计算核酸序列多序列比对的信息量，则是\(IC=log_{2}4-H=2-H\)
- PSSM矩阵中熵表示矩阵中每列各个氨基酸或碱基不确定性之和，常用H来表示。
- 信息量表示该矩阵用于序列搜索或保守区段的搜索效果，常用IC来表示。
- PSSM矩阵的熵越大，不确定性越大，PSMM矩阵的信息量就越小，对于序列搜索或保守区段的搜索效果越不好。 ## 序列标识 sequence logo
- 是一种描述功能域等保守性信息量的可视化图形方式
- 每一列的字母高度和它在某一列中出现的频率成正比，但不等同于频率。因此每一列的高度是不一样的，
- 总结：位置越保守，熵越小，信息量越大，logo高度越高
十三、PRINTS 指纹图谱数据库
蛋白质的指纹：一组保守的序列基序，用于刻画蛋白质家族的特定。
这些基序由多序列比对结果获得，且他们在氨基酸序列上并不相邻，但是在三维结构中可能紧密地结合在一起
使用方法： - 输入数据库编号、关键词等查找以及指纹图谱 -
会显示指纹图谱的基本信息；构建指纹图谱所使用的蛋白质序列；指纹图谱中每一个基序的具体信息
- View alignment还能创建指纹图谱所使用的多序列比对 - View
structure可以查看蛋白质的三维结构，并高亮显示基序空间位置 - PRINT
还提供指纹匹配服务，通过 FPScan，输入纯序列（无
>），可以找到匹配的指纹图谱
问题
1. 氨基酸序列打分矩阵 PAM 和 BLOSUM 中序号有什么意义？它们各自的规律是什么？ 1. 序号的意义： - 在 PAM 矩阵中序号表示进化的变异单位，PAM 1 表示每 100 个残基中有 1 个可以接受单点突变，而 PAMn 代表由 PAM 1 矩阵自乘 n 次得到的矩阵。 - 在 BLOSUM 矩阵中序号表示是由多少相似度残基的序列组成的序列模式产生的 BLOSUM 矩阵，如 BLOSUM 80 表示由相似度不小于 80%的序列局部比对产生的，BLOSUM 62 表示由相似度不小于 62%的序列局部比对产生的。 2. 各自的规律： - PAM-n 矩阵中 n 值越小表示变异的可能性越小，残基差异越小，进化距离越小，相似的序列应该使用 n 值较小的 PAM 矩阵，不相似的序列应该使用 n 值较大的 PAM 矩阵，如 PAM 250 适合用于相似度只有 20% 的序列； - BLOSUM-n 矩阵中 n 值越小，表示序列的相似的可能性越小，对于亲缘序列之间的比对使用 n 值较大的，对于远缘序列之间的比对使用 n 值较小的。
2. 动态规划算法的时间和空间复杂度是多少？ 动态规划算法中有4个循环，前2个做初始化，分别消耗时间 \(O(n)\) 和 \(O(m)\)，后2个循环是嵌套的，填写动态规划表s和表b的元素，时间复杂度为 \(O(mn)\)。由于表s和表b是主要的数据结构，算法的空间复杂度也是 \(O(mn)\)。如果两条序列等长，则时间和空间复杂度都是 \(O(n^2)\)