3 序列比对和数据库搜索
数据挖掘论坛
比较是科学研究中最常见的方法，通过将研究对象相互比较来寻找对象可能具备的特性。在生物信息学研究中，比对是最常用和最经典的研究手段。
最常见的比对是蛋白质序列之间或核酸序列之间的两两比对，通过比较两个序列之间的相似区域和保守性位点，寻找二者可能的分子进化关系。进一步的比对是将多个蛋白质或核酸同时进行比较，寻找这些有进化关系的序列之间共同的保守区域、位点和profile，从而探索导致它们产生共同功能的序列模式。此外，还可以把蛋白质序列与核酸序列相比来探索核酸序列可能的表达框架；把蛋白质序列与具有三维结构信息的蛋白质相比，从而获得蛋白质折叠类型的信息。
比对还是数据库搜索算法的基础，将查询序列与整个数据库]的所有序列进行比对，从数据库中获得与其最相似序列的已有的数据，能最快速的获得有关查询序列的大量有价值的参考信息，对于进一步分析其结构和功能都会有很大的帮助。近年来随着生物信息学数据大量积累和生物学知识的整理，通过比对方法可以有效地分析和预测一些新发现基因的功能。 数据挖掘交友
3.1 序列两两比对 数据挖掘工具
序列比对的理论基础是进化学说，如果两个序列之间具有足够的相似性，就推测二者可能有共同的进化祖先，经过序列内残基的替换、残基或序列片段的缺失、以及序列重组等遗传变异过程分别演化而来。序列相似和序列同源是不同的拍睿蛄兄涞南嗨瞥潭仁强梢粤炕牟问蛄惺欠裢葱枰薪率档难橹ぁＴ诓谢谢榷灾校梢悦飨钥吹叫蛄兄心承┌被岵谢绕渌恢蒙系牟谢Ｊ兀庑┬畔⒔沂玖苏庑┍Ｊ匚坏闵系牟谢缘鞍字实慕峁购凸δ苁侵凉刂匾模缢强赡苁敲傅幕钚晕坏悴谢纬啥蚣陌腚装彼岵谢肱涮褰岷喜课坏牟谢虢鹗衾胱咏岷系牟谢纬商囟ń峁筸otif的残基等等。但并不是所有保守的残基都一定是结构功能重要的，可能它们只是由于历史的原因被保留下来，而不是由于进化压力而保留下来。因此，如果两个序列有显著的保守性，要确定二者具有共同的进化历史，进而认为二者有近似的结构和功能还需要更多实验和信息的支持。通过大量实验和序列比对的分析，一般认为蛋白质的结构和功能比序列具有更大的保守性，因此粗略的说，如果序列之间的相似性超过30%，它们就很可能是同源的。 数据挖掘实验室
早期的序列比对是全局的序列比较，但由于蛋白质具有的模块性质，可能由于外显子的交换而产生新蛋白质，因此局部比对会更加合理。通常用打分矩阵描述序列两两比对，两条序列分别作为矩阵的两维，矩阵点是两维上对应两个残基的相似性分数，分数越高则说明两个残基越相似。因此，序列比对问题变成在矩阵里寻找最佳比对路径，目前最有效的方法是Needleman-Wunsch动态规划算法，在此基础上又改良产生了Smith-Waterman算法和SIM算法。在FASTA程序包中可以找到用动态规划算法进行序列比对的工具LALIGN，它能给出多个不相互交叉的最佳比对结果。 数据挖掘实验室
在进行序列两两比对时，有两方面问题直接影响相似性分值：取代矩阵和空位罚分。粗糙的比对方法仅仅用相同/不同来描述两个残基的关系，显然这种方法无法描述残基取代对结构和功能的不同影响效果，缬氨酸对异亮氨酸的取代与谷氨酸对异亮氨酸的取代应该给予不同的打分。因此如果用一个取代矩阵来描述氨基酸残基两两取代的分值会大大提高比对的敏感性和生物学意义。虽然针对不同的研究目标和对象应该构建适宜的取代矩阵，但国际上常用的取代矩阵有PAM和BLOSUM等，它们来源于不同的构建方法和不同的参数选择，包括PAM250、BLOSUM62、BLOSUM90、BLOSUM30等。对于不同的对象可以采用不同的取代矩阵以获得更多信息，例如对同源性较高的序列可以采用BLOSUM90矩阵，而对同源性较低的序列可采用BLOSUM30矩阵。
数据挖掘论坛
空位罚分是为了补偿插入和缺失对序列相似性的影响，由于没有什么合适的理论模型能很好地描述空位问题，因此空位罚分缺乏理论依据而更多的带有主观特色。一般的处理方法是用两个罚分值，一个对插入的第一个空位罚分，如10－15；另一个对空位的延伸罚分，如1－2。对于具体的比对问题，采用不同的罚分方法会取得不同的效果。
数据挖掘工具
对于比对计算产生的分值，到底多大才能说明两个序列是同源的，对此有统计学方法加以说明，主要的思想是把具有相同长度的随机序列进行比对，把分值与最初的比对分值相比，看看比对结果是否具有显著性。相关的参数E代表随机比对分值不低于实际比对分值的概率。对于严格的比对，必须E值低于一定阈值才能说明比对的结果具有足够的统计学显著性，这样就排除了由于偶然的因素产生高比对得分的可能。
数据挖掘论坛
Genbank、SWISS-PROT等序列数据库提供的序列搜索服务都是以序列两两比对为基础的。不同之处在于为了提高搜索的速度和效率，通常的序列搜索算法都进行了一定程度的优化，如最常见的FASTA工具和BLAST工具。FASTA是第一个被广泛应用的序列比对和搜索工具包，包含若干个独立的程序。FASTA为了提供序列搜索的速度，会先建立序列片段的“字典”，查询序列先会在字典里搜索可能的匹配序列，字典中的序列长度由ktup参数控制，缺省的ktup=2。FASTA的结果报告中会给出每个搜索到的序列与查询序列的最佳比对结果，以及这个比对的统计学显著性评估E值。FASTA工具包可以在大多提供下载服务的生物信息学站点上找到。
数据挖掘研究院
BLAST是现在应用最广泛的序列相似性搜索工具，相比FASTA有更多改进，速度更快，并建立在严格的统计学基础之上。NCBI提供了基于Web的BLAST服务，用户可以把序列填入网页上的表单里，选择相应的参数后提交到数据服务器上进行搜索，从电子邮件中获得序列搜索的结果。BLAST包含五个程序和若干个相应的数据库，分别针对不同的查询序列和要搜索的数据库类型。其中翻译的核酸库指搜索比对时会把核酸数据按密码子按所有可能的阅读框架转换成蛋白质序列。 数据挖掘交友
表1. BLAST程序：
数据挖掘研究院
表2. BLAST的蛋白质数据库：
数据挖掘研究院
数据挖掘实验室
表3. BLAST的核酸数据库：
BLAST对序列格式的要求是常见的FASTA格式。FASTA格式第一行是描述行，第一个字符必须是“>”字符；随后的行是序列本身，一般每行序列不要超过80个字符，回车符不会影响程序对序列连续性的看法。序列由标准的IUB/IUPAC氨基酸和核酸代码代表；小写字符会全部转换成大写；单个“-”号代表不明长度的空位；在氨基酸序列里允许出现“U”和“*”号；任何数字都应该被去掉或换成字母(如，不明核酸用“N”，不明氨基酸用“X”)。此外，对于核酸序列，除了A、C、G、T、U分别代表各种核酸之外，R代表G或A(嘌呤)；Y代表T或C(嘧啶)；K代表G或T(带酮基)；M代表A或C(带氨基)；S代表G或C(强)；W代表A或T(弱)；B代表G、T或C；D代表G、A或T；H代表A、C或T；V代表G、C或A；N代表A、G、C、T中任意一种。对于氨基酸序列，除了20种常见氨基酸的标准单字符标识之外，B代表Asp或Asn；U代表硒代半胱氨酸；Z代表Glu或Gln；X代表任意氨基酸；“*”代表翻译结束标志。
数据挖掘论坛
BLAST的当前版本是2.0，它的新发展是位点特异性反复BLAST(PSI-BLAST)。PSI-BLAST的特色是每次用profile搜索数据库后再利用搜索的结果重新构建profile，然后用新的profile再次搜索数据库，如此反复直至没有新的结果产生为止。PSI-BLAST先用带空位的BLAST搜索数据库，将获得的序列通过多序列比对来构建第一个profile。PSI-BLAST自然地拓展了BLAST方法，能寻找蛋白质序列中的隐含模式，有研究表明这种方法可以有效的找到很多序列差异较大而结构功能相似的相关蛋白，甚至可以与一些结构比对方法，如threading相媲美。PSI-BLAST服务可以在NCBI的BLAST主页上找到，还可以从NCBI的FTP服务器上下载PSI-BLAST的独立程序。 数据挖掘研究院
NCBI的BLUST网址是：http://www.ncbi.nlm.nih.gov/BLAST/。
下载BLUST的网址是：ftp://ncbi.nlm.nih.gov/blast/。 数据挖掘论坛
下载FASTA的网址是：ftp://ftp.virginia.edu/pub/fasta/。 数据挖掘研究院
数据挖掘交友
3.2 多序列比对
数据挖掘实验室
顾名思义，多序列比对就是把两条以上可能有系统进化关系的序列进行比对的方法。目前对多序列比对的研究还在不断前进中，现有的大多数算法都基于渐进的比对的思想，在序列两两比对的基础上逐步优化多序列比对的结果。进行多序列比对后可以对比对结果进行进一步处理，例如构建序列模式的profile，将序列聚类构建分子进化树等等。
目前使用最广泛的多序列比对程序是CLUSTALW(它的PC版本是CLUSTALX)。CLUSTALW是一种渐进的比对方法，先将多个序列两两比对构建距离矩阵，反应序列之间两两关系；然后根据距离矩阵计算产生系统进化指导树，对关系密切的序列进行加权；然后从最紧密的两条序列开始，逐步引入临近的序列并不断重新构建比对，直到所有序列都被加入为止。 数据挖掘工具
CLUSTALW的程序可以自由使用，在NCBI的FTP服务器上可以找到下载的软件包。CLUSTALW程序用选项单逐步指导用户进行操作，用户可根据需要选择打分矩阵、设置空位罚分等。EBI的主页还提供了基于Web的CLUSTALW服务，用户可以把序列和各种要求通过表单提交到服务器上，服务器把计算的结果用Email返回用户。 数据挖掘论坛
CLUSTALW对输入序列的格式比较灵活，可以是前面介绍过的FASTA格式，还可以是PIR、SWISS-PROT、GDE、Clustal、GCG/MSF、RSF等格式。输出格式也可以选择，有ALN、GCG、PHYLIP和GDE等，用户可以根据自己的需要选择合适的输出格式。
数据挖掘工具
用CLUSTALW得到的多序列比对结果中，所有序列排列在一起，并以特定的符号代表各个位点上残基的保守性，“*”号表示保守性极高的残基位点；“.”号代表保守性略低的残基位点。 数据挖掘实验室
EBI的CLUSTALW网址是：http://www.ebi.ac.uk/clustalw/。 数据挖掘研究院
下载CLUSTALW的网址是：ftp://ftp.ebi.ac.uk/pub/software/。 数据挖掘工具
