全局序列比对算法

‘壹’ 生物信息系统序列比对存入什么数据

生物信息系统序列比对存入什么数据
生物信息学在短短十几年间，已经形成了多个研究方向，以下简要介绍一些主要的研究重点。
序列比对
序列比对（Sequence Alignment）的基本问题是比较两个或两个以上符号序列的相似性或不相似性。从生物学的初衷来看，这一问题包含了以下几个意义：从相互重叠的序列片断中重构DNA的完整序列。在各种试验条件下从探测数据（probe data）中决定物理和基因图存贮，遍历和比较数据库中的DNA序列，比较两个或多个序列的相似性，在数据库中搜索相关序列和子序列，寻找核苷酸（nucleotides）的连续产生模式，找出蛋白质和DNA序列中的信息成分。序列比对考虑了DNA序列的生物学特性，如序列局部发生的插入，删除（前两种简称为indel）和替代，序列的目标函数获得序列之间突变集最小距离加权和或最大相似性和，对齐的方法包括全局对齐，局部对齐，代沟惩罚等。两个序列比对常采用动态规划算法，这种算法在序列长度较小时适用，然而对于海量基因序列（如人的DNA序列高达10^9bp），这一方法就不太适用，甚至采用算法复杂性为线性的也难以奏效。因此，启发式方法的引入势在必然，着名的BLAST和FASTA算法及相应的改进方法均是从此前提出发的。
蛋白质比对
基本问题是比较两个或两个以上蛋白质分子空间结构的相似性或不相似性。蛋白质的结构与功能是密切相关的，一般认为，具有相似功能的蛋白质结构一般相似。蛋白质是由氨基酸组成的长链，长度从50到1000~3000AA（Amino Acids），蛋白质具有多种功能，如酶，物质的存贮和运输，信号传递，抗体等等。氨基酸的序列内在的决定了蛋白质的3维结构。一般认为，蛋白质有四级不同的结构。研究蛋白质结构和预测的理由是：医药上可以理解生物的功能，寻找dockingdrugs的目标，农业上获得更好的农作物的基因工程，工业上有利用酶的合成。直接对蛋白质结构进行比对的原因是由于蛋白质的3维结构比其一级结构在进化中更稳定的保留，同时也包含了较AA序列更多的信息。蛋白质3维结构研究的前提假设是内在的氨基酸序列与3维结构一一对应（不一定全真），物理上可用最小能量来解释。从观察和总结已知结构的蛋白质结构规律出发来预测未知蛋白质的结构。同源建模（homology modeling）和指认（Threading）方法属于这一范畴。同源建模用于寻找具有高度相似性的蛋白质结构（超过30%氨基酸相同），后者则用于比较进化族中不同的蛋白质结构。然而，蛋白结构预测研究现状还远远不能满足实际需要。

‘贰’ 详细介绍双序列比对、blast 以及多序列比对的区别,以及均适用于哪些场 景

序列比对是将两个或多个序列排列在一起，标明其相似之处。使用间隔表示未比对上，比对上的相同或相似的符号排列在同一列上。序列比对是生物信息学以及基因组学与进化的基础之一，其基本思想是：在生物学中普遍存在的序列决定结构、结构决定功能的规律，通过将核酸序列或者蛋白质序列的一级结构看成由基本字符构成的字符串，通过序列比对我们可以找到相似的序列并由此发现生物序列中的功能、结构和进化信息。
全局比对：全局比对是指将参与比对的两条序列里面的所有字符进行比对。全局比对在全局范围内对两条序列进行比对打分，找出最佳比对，主要被用来寻找关系密切的序列。其可以用来鉴别或证明新序列与已知序列家族的同源性，是进行分子进化分析的重要前提。其代表是Needleman-Wunsch算法。
局部比对：与全局比对不同，局部比对不必对两个完整的序列进行比对，而是在每个序列中使用某些局部区域片段进行比对。其产生的需求在于、人们发现有的蛋白序列虽然在序列整体上表现出较大的差异性，但是在某些局部区域能独立的发挥相同的功能，序列相当保守。这时候依靠全局比对明显不能得到这些局部相似序列的。其次，在真核生物的基因中，内含子片段表现出了极大变异性，外显子区域却较为保守，这时候全局比对表现出了其局限性，无法找出这些局部相似性序列。其代表是Smith-Waterman局部比对算法。
双重序列比对：双序列比对是指对两条序列M和N进行比对，找到其相似性关系，这种寻找生物序列相似性关系的过程被称为双序列比对。其算法可以主要分成基于全局比对的Needleman-Wunsch算法和基于局部比对的Smith-Waterman局部比对算法
多重序列比对：多序列比对是双序列比对推广，即把两个以上字符序列对齐，逐列比较其字符的异同，使得每一列字符尽可能一致，以发现其共同的结构特征的方法称为多序列比对。多序列比对算法可以分成渐进法和同步法。其可以发现不同的序列之间的相似部分，从而推断它们在结构和功能上的相似关系，主要用于分子进化关系，预测蛋白质的二级结构和三级结构、估计蛋白质折叠类型的总数，基因组序列分析等。
基因组比对：是多序列比对的一种特例，指对基因组范围内的序列信息进行比对的过程。通过对不同亲缘关系物种的基因组序列进行比较，能够鉴定出编码序列、非编码调控序列及给定物种独有的序列。而基因组范围之内的序列比对，可以了解不同物在核苷酸组成、同线性关系和基因顺序方面的异同，进而得到基因分析预测与定位、生物系统发生进化关系等方面的信息。
BLAST：BLAST[1]（Basic Local Alignment Search Tool）是在在1990年由Altschul等人提出的双序列局部比对算法，是一套在蛋白质数据库或DNA数据库中进行相似性比较的分析工具。BLAST是一种启发式算法，用于在大型数据库中寻找比对序列，是一种在局部比对基础上的近似比对算法，可以在保持较高精度的情况下大大减少程序运行的时间。
算法思想描述：
双重序列比对主要分成以Needleman-Wunsch算法为代表的全局比对和以Smith-Waterman局部比对算法为代表的局部比对，BLAST是局部比对的一种推广。多重比对算法可以主要分成动态规划算法、随机算法、迭代法和渐进比对算法。
（1）双重序列比对：
Needleman-Wunsch算法：该算法是基于动态规划思想的全局比对的基本算法，动态规划的比对算法的比对过程可以用一个以序列S为列，T为行的(m+1)×(n+1)的二维矩阵来表示，用
sigma表示置换矩阵。
在计算完矩阵后，从矩阵的右下角单元到左上单元回溯最佳路径（用箭头表示），根据最佳路径给出两序列的比对结果。其中，斜箭头表示2个残基匹配，水平箭头表示在序列S的相应位置插入一个空位，垂直方向的箭头表示在序列T的相应位置插入一个空位。

Smith-Waterman算法：该算法是一种用来寻找并比较具有局部相似性区域的动态规划算法，这种算法适用于亲缘关系较远、整体上不具有相似性而在一些较小的区域上存在局部相似性的两个序列。该算法的基本思想是：使用迭代方法计算出两个序列的相似分值，存在一个得分矩阵M中，然后根据这个得分矩阵，通过动态规划的方法回溯找到最优的比对序列。与全局比对相比，这种算法的改变是把矩阵单元值为负者一律取为0，这是因为分值为负的比对丧失了比对的生物学意义，因此把得分为负值的子序列丢弃。

BLAST: BLAST算法的基本思想是通过产生数量更少的但质量更好的增强点来提高比对的速度。算法的原理主要分为以下五步：（1）过滤：首先过滤掉低复杂度区域，即含有大量重复的序列；（2）Seeding：将Query序列中每k个字组合成一个表，即将一个序列拆分成多个连续的‘seed words’（通常蛋白质k=3，核酸k=11）；（3）比对：列出我们所关心的所有可能的字组，再配合置换矩阵给出高分值的字组并组织成快速搜索树结构或者哈希索引，因此此步骤可以快速搜索出大数据集中的所有匹配序列，找到每个seed words在参考序列中的位置；（4）延伸：当找到seed words的位置后，接下来需要将seed word延伸成长片段，延伸过程中，得分值也在变化，当得分值小于阈值时即停止延伸，最后得到的片段成为高分片段对，HSP（High-scoring segment pair）；（5）显着性分析，最后我们使用如下公式计算E值，E值衡量了在随机情况下，数据库存在的比当前匹配分数更好的比对的数目，因此可以用该值作为指标评价HSP比对序列的可信度。
其中，m是数据库长度，n是query的长度，S是HSP分数，其他两个参数是修正系数。

（2）多重序列比对

动态规划算法：其基本思想是将一个二维的动态规划矩阵扩展到三维或者多维，多序列比对的积分是n个序列中两两进行比对所得积分之和。矩阵的维度反映了参与比对的序列数。这种方法对计算资源要求比较高[6]。
随机算法：主要包括遗传算法和模拟退火算法，遗传算法是一类借鉴生物界进化规律演化来的全局意义上的自适应随机搜索方法。当用遗传算法进行生物序列分析时，每一代包含固定数量的个体，这些个体用他们的适应度来评价。变异则模拟了生物进化过程中的偶然残基突变现象。对产生的新一代群体进行重新评价、选择、交叉、变异，如此循环往复，使群体中最优个体的适应度不断提高，直到达到一个阈值，算法结束。模拟退火的基本思想是用一物质系统的退火过程来模拟优化问题的寻优方法，当物质系统达到最小能量状态时，优化问题的目标函数也相应地达到了全局最优解。这两种方法都是对构造好的目标函数进行最优解搜索，但实际比对效果并不好[6,7]。
迭代法：迭代法的代表是Muscle[8], Muscle是一个新的渐进比对和迭代比对的综合算法，主要由两部分构成，第一部分是迭代渐进比对：第一次渐进比对的目的是快速产生一个多序列比对而不强调准确率，以此为基础再对渐进比对进行改良。经过两次渐进比对，形成一个相对准确的多序列比对；第二部分是迭代比对：该过程类似于Prrp算法[9]，即通过不断的迭代，逐步优化最终比对结果。其主要特点包括：使用kmer counting进行快速的距离测量，使用一个新的图谱比对打分函数进行渐进比对，使用依赖于数的有限分隔进行细化。
渐进比对算法：该算法以Feng和Doolittle提出的最为经典[10]。渐进比对算法的基本思想是迭代地利用两序列动态规划比对算法,先由两个序列的比对开始，逐渐添加新序列，直到所有序列都加入为止。但是不同的添加顺序会产生不同的比对结果。确定合适的比对顺序是渐进比对算法的一个关键问题。通常，整个序列的比对应该从最相似的两个序列开始，由近至远逐步完成。作为全局多序列比对的渐进比对算法有个基本的前提假设:所有要比对的序列是同源的，即由共同的祖先序列经过一系列的突变积累，并经自然选择遗传下来的，分化越晚的序列之间相似程度就越高。因此，在渐进比对过程中，应该对近期的进化事件比远期的进化事件给予更大的关注。由于同源序列是进化相关的，因此可以按着序列的进化顺序，即沿着系统发育树(指导树)的分支，由近至远将序列或已比对序列按双序列比对算法逐步进行比对，重复这一过程直到所有序列都己添加到这个比对中为止[10]。其三个步骤为：（1）利用双序列比对方法对所有的序列进行两两比对，得到相似性分值；（2）利用相似性矩阵（或距离矩阵）产生辅助导向树；（3）根据导向树进行渐进比对。渐进比对算法是最常用、简单又有效的启发式多序列比对方法，它所需时间较短、所占内存较小，其算法很多，主要有CLUSTAL W, T-Coffee和DiAlign等，其中 CLUSTAL W应用最广泛。
应用：
类型+应用
双重序列对比：判断两个序列的同源性和一致性。（1）全局多序列比对可以鉴别或证明新序列与己有序列家族的同源性;帮助预测新蛋白质序列的二级和二级结构，是进行分子进化分析的重要前提。适合序列相似性较高，序列长度近似时的比对；（2）局部比对考虑序列部分区域的相似性。局部多序列比对可以用来刻画蛋白质家族和超家族。适合于未知两个序列相似程度的，可能存在一些片段极其相似而另一些片段相异的序列比对情况。
多重序列比对：多重比对经常用来研究序列间的进化关系，构建进化树；探究序列间的保守性。主要用于分子进化关系，预测蛋白质的二级结构和三级结构、估计蛋白质折叠类型的总数，基因组序列分析等。
基因组比对：通过对不同亲缘关系物种的基因组序列进行比较，能够鉴定出编码序列、非编码调控序列及给定物种独有的序列。而基因组范围之内的序列比对，可以了解不同物在核苷酸组成、同线性关系和基因顺序方面的异同，进而得到基因分析预测与定位、生物系统发生进化关系等方面的信息。
其中，BLAST作为最重要的比对工具，意义特殊，拿出来单独讨论。BLAST可以分成Basic BLAST和 Specialized BLAST, BLAST包括常规的nucleotide blast, Protein blast和Translating blast；Specialize blast可以对特殊生物或特殊研究领域的序列数据库进行检索。

‘叁’ 序列比对的算法有哪些在应用上各有何特点

首先你要明白——Clustalx的多序列比对算法是基于双序列比对的，它先将所有序列两两比对，然后根据两两比对结果构建指导树，再根据指导树依次添加相似度最高的

‘肆’ 什么是多序列全局比对的累进算法（三个步骤）

第一，所有的序列之间逐一比对（双重比对）；第二，生成一个系统树图，将序列按相似性大致分组；第三，使用系统树图作为引导，产生出最终的多序列比对结果。

‘伍’ 如何通过生物信息学获得一个基因家族的所有序列

如何通过生物信息学获得一个基因家族的所有序列
序列比对其意义是从核酸、氨基酸的层次来比较两个或两个以上符号序列的相似性或不相似性，进而推测其结构功能及进化上的联系。研究序列相似性的目的是通过相似的序列得到相似的结构或功能，也可以通过序列的相似性判别序列之间的同源性，推测序列之间的进化关系。序列比对是生物信息学的基础，非常重要。
序列比对中最基础的是双序列比对，双序列比较又分为全局序列比较和局部序列比较，这两种比较均可用动态程序设计方法有效解决。在实际应用中，某些在生物学上有重要意义的相似性不是仅仅分析单条序列，只能通过将多个序列对比排列起来才能识别。比如当面对许多不同生物但蛋白质功能相似时，我们可能想知道序列的哪些部分是相似的，哪些部分是不同的，进而分析蛋白质的结构和功能。为获得这些信息，我们需要对这些序列进行多序列比对。多重序列比对算法有动态规划算法、星形比对算法、树形比对算法、遗传算法、模拟退火算法、隐马尔可夫模型等，这些算法都可以通过计算机得以解决。

‘陆’ 什么时候需要利用生物信息学获取核酸序列信息

什么时候需要利用生物信息学获取核酸序列信息
1.序列比对
序列比对其意义是从核酸、氨基酸的层次来比较两个或两个以上符号序列的相似性或不相似性，进而推测其结构功能及进化上的联系。研究序列相似性的目的是通过相似的序列得到相似的结构或功能，也可以通过序列的相似性判别序列之间的同源性，推测序列之间的进化关系。序列比对是生物信息学的基础，非常重要。
序列比对中最基础的是双序列比对，双序列比较又分为全局序列比较和局部序列比较，这两种比较均可用动态程序设计方法有效解决。在实际应用中，某些在生物学上有重要意义的相似性不是仅仅分析单条序列，只能通过将多个序列对比排列起来才能识别。比如当面对许多不同生物但蛋白质功能相似时，我们可能想知道序列的哪些部分是相似的，哪些部分是不同的，进而分析蛋白质的结构和功能。为获得这些信息，我们需要对这些序列进行多序列比对。多重序列比对算法有动态规划算法、星形比对算法、树形比对算法、遗传算法、模拟退火算法、隐马尔可夫模型等，这些算法都可以通过计算机得以解决。
2.数据库搜索
随着人类基因组计划的实施，实验数据急剧增加，数据的标准化和检验成为信息处理的第一步工作，并在此基础上建立数据库，存储和管理基因组信息。这就需要借助计算机存储大量的生物学实验数据，通过对这些数据按一定功能分类整理，形成了数以百计的生物信息数据库，并要求有高效的程序对这些数据库进行查询，以此来满足生物学工作者的需要。数据库包括一级数据库和二级数据库，一级数据库直接来源于实验获得的原始数据，只经过简单的归类整理和注释；二级数据库是对基本数据进行分析、提炼加工后提取的有用信息。
分子生物学的三大核心数据库是GenBank核酸序列数据库，SWISS-PROT蛋白质序列数据库和PDB生物大分子结构数据库，这三大数据库为全世界分子生物学和医学研究人员了解生物分子信息的组织和结构，破译基因组信息提供了必要的支撑。但是用传统的手工分析方法来处理数据显然已经无法跟上新时代的步伐，对于大量的实验结果必须利用计算机进行自动分析，以此来寻找数据之间存在的密切关系，并且用来解决实际中的问题。
3.基因组序列分析
基因组学研究的首要目标是获得人的整套遗传密码，要得到人的全部遗传密码就要把人的基因组打碎，测完每个小的序列后再把它们重新拼接起来。所以目前生物信息学的大量工作是针对基因组DNA序列的，建立快速而又准确的DNA序列分析方法对研究基因的结构和功能有非常重要的意义。对于基因组序列，人们比较关心的是从序列中找到基因及其表达调控信息，比如对于未知基因，我们就可以通过把它与已知的基因序列进行比较，从而了解该基因相关的生理功能或者提供疾病发病机理的信息，从而为研发新药或对疾病的治疗提供一定的依据，使我们更全面地了解基因的结构，认识基因的功能。因此，如何让计算机有效地管理和运行海量的数据也是一个重要问题。
4.蛋白质结构预测
蛋白质是组成生物体的基本物质，几乎一切生命活动都要通过蛋白质的结构与功能体现出来，因此分析处理蛋白质数据也是相当重要的，蛋白质的生物功能由蛋白质的结构所决定，因此根据蛋白质序列预测蛋白质结构是很重要的问题，这就需要分析大量的数据，从中找出蛋白质序列和结构之间存在的关系与规律。
蛋白质结构预测分为二级结构预测和空间结构预测，在二级结构预测方面主要有以下几种不同的方法：①基于统计信息；②基于物理化学性质；③基于序列模式；④基于多层神经网络；⑤基于图论；⑥基于多元统计；⑦基于机器学习的专家规则；⑧最邻近算法。目前大多数二级结构预测的算法都是由序列比对算法BLAST、FASTA、CLUSTALW产生的经过比对的序列进行二级结构预测。虽然二级结构的预测方法其准确率已经可以达到80%以上，但二级结构预测的准确性还有待提高。
在实际进行蛋白质二级结构预测时，往往会把结构实验结果、序列比对结果、蛋白质结构预测结果，还有各种预测方法结合起来，比较常用的是同时使用多个软件进行预测，把各个软件预测结果分析后得出比较接近实际的蛋白质二级结构。将序列比对与二级结构预测相结合也是一种常见的综合分析方法。
蛋白质二级结构指蛋白质多肽链本身的折叠和盘绕的方式。二级结构主要有α-螺旋、β-折叠、β-转角等几种形式，它们是构成蛋白质高级结构的基本要素，常见的二级结构有α-螺旋和β-折叠。三级结构是在二级结构的基础上进一步盘绕，折叠形成的。研究蛋白质空间结构的目标是为了了解蛋白质与三维结构的关系，预测蛋白质的二级结构预测只是预测蛋白质三维形状的第一步，蛋白质折叠问题是非常复杂的，这就导致了蛋白质的空间结构预测的复杂性。蛋白质三维结构预测方法有：同源模型化方法、线索化方法和从头预测的方法但是无论用哪一种方法，结果都是预测，采用不同的算法，可能产生不同的结果，因此还需要研究新的理论计算方法来预测蛋白质的三维结构。
图4.1 蛋白质结构
目前，已知蛋白质序列数据库中的数据量远远超过结构数据库中的数据量，并且这种差距会随着DNA序列分析技术和基因识别方法的进步越来越大，人们希望产生蛋白质结构的进度能够跟上产生蛋白质序列的速度，这就需要对蛋白质结构预测发展新的理论分析方法，目前还没有一个算法能够很好地预测出一个蛋白的三维结构形状，蛋白质的结构预测被认为是当代计算机科学要解决的最重要的问题之一，因此蛋白质结构预测的算法在分子生物学中显得尤为重要。
5.结束语
现如今计算机的发展已渗透到各个领域，生物学中的大量实验数据的处理和理论分析也需要有相应的计算机程序来完成，因此随着现代科技的发展，生物技术与计算机信息技术的融合已成为大势所趋。生物学研究过程中产生的海量数据需要强有力的数据处理分析工具，这样计算机科学技术就成为了生物科学家的必然选择，虽然人们已经利用计算机技术解决了很多生物学上的难题，但是如何利用计算机更好地处理生物学中的数据仍是一个长期而又复杂的课题。

‘柒’ 序列比对的算法过程

实际操作中利用计算机程序实现序列比对的基本算法。序列比对不仅需要考虑子序列之间的匹配，而且需要对整个序列进行比较。也就是说，必须考虑两个序列中所有残基的匹配。这就意味着，不可能使所有残基都能严格匹配。在这种情况下，序列比对中确定空位的过程变得十分复杂。
在进行序列两两比对时，有两方面问题直接影响相似性分值：取代矩阵和空位罚分。 空位罚分是为了补偿插入和缺失对序列相似性的影响，由于没有什么合适的理论模型能很好地描述空位 问题，因此空位罚分缺乏理论依据而更多的带有主观特色。一般的处理方法是用两个罚分值，一个对插入的第一个空位罚分，如10－15；另一个对空位的延伸罚分，如1－2。对于具体的比对问题，采用不同的罚分方法会取得不同的效果。
对于比对计算产生的分值，到底多大才能说明两个序列是同源的，对此有统计学方法加以说明，主要的思想是把具有相同长度的随机序列进行比对，把分值与最初的比对分值相比，看看比对结果是否具有显着性。相关的参数E代表随机比对分值不低于实际比对分值的概率。对于严格的比对，必须E值低于一定阈值才能说明比对的结果具有足够的统计学显着性，这样就排除了由于偶然的因素产生高比对得分的可能。

‘捌’ 序列比对的分类

把两个以上字符序列对齐，逐列比较其字符的异同，使得每一列字符尽可能一致，以发现其共同的结构特征的方法称为多序列比对 。多序列比对问题其实是双序列比对问题的推广。
多序列比对的目标是使得参与比对的序列中有尽可能多的列具有相同的字符，即，使得相同残基的位点位于同一列，这样以便于发现不同的序列之间的相似部分，从而推断它们在结构和功能上的相似关系，主要用于分子进化关系，预测蛋白质的二级结构和三级结构、估计蛋白质折叠类型的总数，基因组序列分析等。
由于多序列比对能够揭示双序列比对所不能发现的序列微弱相似性、序列模式和功能位点，因而对蛋白质和核酸序列的结构、功能和进化研究更加有用。 1981年，由F. Smith 和 M.Waterman首次提出局部比对算法，动态规划方法通过较少的改动便可以用来识别匹配的子序列， 并且忽略匹配区域之前或之后的失配和空位;局部比对时，表中小于零的位置用零代替。主要用来考察两序列的某些特殊片段。