来自：中国大学mooc-山东大学 生物信息学 课程
1.什么是序列？
序列就是字符串。
s就是一个序列。（原来序列是这么简单的，听着太高大上了）
蛋白质序列：由20个不同的字母（氨基酸）排列组合而成。
核酸序列：由4个不同的字母（碱基，ATCGU）排列组合而成，包括DNA序列和RNA序列。
FASTA格式：第一行＞表示注释；第二行及以后：每行60个字母或80，不一定。
图1.数据格式
2.序列相似性
图2.相似比较
图中显示了序列的相似性比较，对于序列长度是非常非常长的，肉眼根本无法识别，所以就需要技术来进行识别。
那么有序列一致度identity与相似度similarity两个概念：
图3.一致度和相似度定义
图4.例子
那么这两个序列的一致度就是50%，很好计算。
但是相似度是怎么计算的呢？哪个残基和哪个残基算作相似？
答：残基两两相似关系被 替换积分矩阵 所定义。
图5.蛋白质替换积分矩阵长这个样子
3.替换记分矩阵
描述了残基两两相似性的量化关系。
图6.DNA
3.1 3种常见的DNA替分矩阵：
①等价矩阵：相同为1，不同为0.
②转换-颠换矩阵：核算碱基按照环结构被划分为两类，嘌呤（腺嘌呤A，鸟嘌呤G）有两个环；嘧啶（胞嘧啶C、胸腺嘧啶T）有一个环。如果DNA替换保持环数不变则是转换，比如嘌呤与嘌呤之间的转换；如果环数发生变化那么就是颠换，比如嘌呤和嘧啶之间的替换。
③BLAST矩阵：就是根据经验得到，没有为什么。
三种如下图：
3.2 3中常见的蛋白质序列的替换计分矩阵：
等价矩阵：与DNA替换等价。
PAM矩阵：基于进化原理。如果两种氨基酸替换频率高，那么就代表自然界易接受这种替换，替换得分就相应高。
PAM矩阵中，后边的数越小，表示亲缘关系越近；越大表示亲缘关系越远。PAM-1是基于相似度>85%的序列计算产生的。更多的PAM-259是PAM-1多次自乘得到的。
BLOSUM矩阵：它是根据真实数据得到的，BLOSUM-80是由一致度>=80%得到的。后边的数越大，表示亲缘关系越近；越小，表示亲缘关系越远。
这个图很好的说明了。氨基酸差异合BLOSUM矩阵是互补的。但是PAM矩阵中由于连乘是有差异的，在PAM后面的数字和氨基酸差异度。
那么是选PAM还是BLOSUM呢？
如果不确定的话，一般选：BLOSUM-62是没问题的。
对于亲缘关系较远的比对，由于PAM-250是计算得到的，准确度有限制，BLOSUM-45更有优势；对于亲缘关系较近的比较，两者差别不大。
3.3其他2个替换计分矩阵
1.遗传密码矩阵：通过计算一个氨基酸转换成另一个氨基酸所需的 密码子变化数目 得到。如果变化一个碱基就能使一个氨基酸的密码子转换为另一个氨基酸的密码子，那么代价就是1，以此类推。得到的最终矩阵一般都是1和2。
2.疏水矩阵：根据氨基酸替换前后疏水性的变化得到计分矩阵。
如果一次替换导致蛋白质疏水特性不发生较大改变，则替换得分高，否则分低。
矩阵物理意义明确，有一定理化性质依据，适用于偏蛋白质功能方面的序列比对。
4.计算相同长度的序列相似度
还是对那个例子来说：
那么它的一致度为：2/4=50%.
那么相似度如何计算？根据查表得到(得分>=0就是相似的)，L和I之间是相似的，K和L是不相似的，那么=(2+1)/4=75%.
但是两个序列长度不同的怎么替换呢？（觉得这个问题还挺有趣的，应该就是通过dp计算最大子串长度吧。）
——到目前为止觉得这些东西还都比较简单。
5.序列比较法
5.1 打点比较
从图中可以发现，打点打出了一条主对角线。那么连续的对角线及与对角线平行的代表序列中相同的区域。
还可以对一条序列自己打点，那么肯定是一个对称矩阵，在纵向或者横向与主对角线平行的短平行线对应的序列片段就是重复的部分。
比如对：
这个序列得到：
那么重复出现了3次，包括主对角线在内的重复的个数就是重复总个数。
通过这种方法就可以发现串联重复序列，如下图：
*这里讲解时提到了，孟德尔共显性遗传规律，所以去百度百科了解了一下：
（我居然是这个词条第一个点赞的人也）
共显性遗传是指一对等位基因之间，没有显性和隐性的区别，在杂合子个体中两种基因的作用都能表现出来。比如ABO型血。
6.序列比较法
这个图解非常不错，理解了这个算法，向左上表示当前字符与字符对比；向左表示序列P当前字符与空格对比；向上表示序列序列q与空格对比。
最后在最后一个部分回溯即可。
关于回溯最有比对序列，图里给出了不错的解释，理解了之后记住这三个箭头的含义即可。
这里给出了全局比对和局部比对，理解了为什么要有局部比对。
对于长度不同的序列来说，如果都使用全局比对，比如途中的两个比对，很明显比对结果和想要的并不是一个，而应该是第一个效果好，所以出现了局部比对。
对于局部比对算法，只比全局比对多了个最大值限定为0，在接下来的例子中能够反映出这个0，需要注意的是，一开始矩阵的第0行和第0列都会被初始化为0，这是和全局比对算法不同的。
这个基本过程是和全局比对相似的，只不过在追溯最优比对序列时，不是从右下角追溯到左上角，而是选择矩阵中的最大值开始追溯，追溯到没有箭头为止。
那么又回到了这个问题，就是如何计算长度不同的序列的相似度？
从图中可以很清晰的了解，长度不同时使用的是全局比对，而不是局部比对。
总的来说就是图中最后一句，不论长度是否相同都要做序列全局比对。
7. 在线序列对比工具
7.1全局比对工具
选择蛋白质比对，输入以下数据：
得到比对结果：
那么在计算一致度时就计算|的个数，相似度是计算.的个数，依次这样计算。下面会介绍使用参数：
第一个就是替换积分矩阵了，GAP OPEN是出现第一个空位的罚分，GAP EXTEND是延后罚分。
第一次比对设置为10 0.5，第二次比对设置为1 5.
设置这两个参数后得到的比对结果是大不相同的。如下：
第一次比对结果中，有较长的空位出现，因为空位延申罚分低；第二次结果中，除了开头部分，空位都是分散出现，因为连续空位代价高。
有一个例题：
↑有一句话特别明显：“用其中已知结构的序列做模板，来预测另一个序列的结构”。那么就是采用分散空位了。
另一个例子是知道比对的序列绝大多数是相似的，但是其中的一个功能区在另一条序列中是缺失的，想通过序列比对将功能区找到，怎么设置gap open和gap extent呢？
7.2局部比对工具
默认参数局部比对结果，可以看出序列一中头部不同的部分红色标注在局部比对中被去掉；在序列2中最后的被去掉。
这些对不上的在全局比对中是对空位的。
下面是对新一组数据进行全局与局部比对的结果：
局部比对时将空位open和gap延申都设置为较大：10 5，使尽可能相似的部分出现。
在全局比对中可以看出只有前一段中比对结果较好，后边均较差。
8.BLAST搜索
BLAST是Basic Local Alignment Search Tool的缩写。
它的基本原理是片段对的概念。片段对就是两个给定序列中的子序列，长度相等，并且无空位完全匹配。
首先找出探测序列和目标序列间所有匹配程度超过一定阈值的序列片段对，然后根据相似性进行延伸，得到相似性片段，最后给出高分值片段对（HPS，high-scoring pairs）。
前两种是比较常用的，后三种是对于新发现的序列吧，看它们对应的蛋白质。下图是更好的一个介绍的过程。
例题：要在核酸数据库查询一段与某DNA序列编码蛋白质最相似的序列，应选择：肯定是最后一个了tBLASTx。
NCBI上的BLAST比对算法:
线条颜色和位置分别表示匹配度和匹配位置，另有一个来源表:
其中Ident为一致度，BLAST为了速度牺牲掉了一定的准确度，但是对于亲缘关系近的序列并没有太大的影响，但是对于远亲就不又好了可能丢失。
解决办法是PSI-BLAST：Postion-Specific Iterated BLAST。
位置特异权重矩阵，搜索一遍数据库后，统计一个多序列比对中，每一个位置上不同残基出现的百分比，
PSSM：比如给出的四条序列，现在找到了这4条是相似的，那么得到的矩阵如下，在下一次比对中，和B是朋友的也会被计算进来，比如C也会被计算进来。
PHI-BLAST（Pattern-Hit Initiated）精准搜索：能找到与输入序列相似的符合某种特定模式(Pattern)的序列。
比如举个例子：
就是用个正则表达式找出这一类呗。那么这个序列有什么生物学含义呢？
->
在正则表达式中：{}表示除...以外，[..]在..之中，x代表任意字母，(x,y)表示x-y个()之前的字符。【这个正则表达式我看见时居然没有主动去思考，真是错误。】
那么这里里边的含义就是再接3-7个任意字母。
最后的Smart BLAST，操作最简洁，最终返回与待测序列最相近的三个序列，
给出最相近的物种并根据其可得到进化关系的推断。
还有其他的BLAST算法，以及他们的适用情况。
9.多序列比对
两条以上的序列进行的全局比对。
要求如上↑
10.从头测序
对一个从未见过的生物的基因组的测序。（这里说的是测出来序之后如何存储吧！毕竟是一个大数据问题，如何存储才能更节省空间更高效？）
第一个重叠图，不太明白是什么意思，图也没有看懂。
第二个图是DB图，这个是将一个reads分称kmer个，每个之间都有k-1个overlap，在使用哈希表，键值表示出现次数，那么这样就可以降低数据存储量，只要找到欧拉路就是一个可能的reads。两个点之间存在边即kmer之间存在k-1个overlap。
这个DB的缺点是不能反映出原始结构吧。
但是也有一个很大的问题，就是基因组中一般都有很高的dulpication，人体基因组中有50%左右的重复区域或者说是高度相似。那么这样DB中就会有很多出度入度，不便存储，这是二代测序中存在的问题。