BLAST的基本算法原理的基本算法原理BLAST BLAST 是由美国国立生物技术信息是由美国国立生物技术信息中心（中心（NCBI）开发的一个基于）开发的一个基于序列相序列相似性似性的数据库搜索程序。的数据库搜索程序。 BLAST是是“局部相似性基本查询工具局部相似性基本查询工具”(Basic Local Alignment Search Tool)的的 缩写。缩写。BLAST基本原理基本原理Step 1n n1) 1) 滤去低复杂度区域（滤去低复杂度区域（滤去低复杂度区域（滤去低复杂度区域（Low Complexity Low Complexity Region,LCRRegion,LCR) ) （Low Complexity Region, LCR) Low Complexity Region, LCR) 一般指重复的能缩小不同序列间一般指重复的能缩小不同序列间一般指重复的能缩小不同序列间一般指重复的能缩小不同序列间差异的序列片段。主要包括一些基因序列的固定结构，差异的序列片段。主要包括一些基因序列的固定结构，差异的序列片段。主要包括一些基因序列的固定结构，差异的序列片段。主要包括一些基因序列的固定结构， 如：如：如：如： Poly A Poly A 尾；尾；尾；尾； AluAlu序列；序列；序列；序列； 有多个重复序列的短序列片段；有多个重复序列的短序列片段；有多个重复序列的短序列片段；有多个重复序列的短序列片段； 某个字母的大量重复。某个字母的大量重复。某个字母的大量重复。某个字母的大量重复。2）将检索序列分解为种子序列）将检索序列分解为种子序列 BLAST将待搜索的序列根据规定字长按照顺序分成一系列的序列单词（word)。 例：待搜索序列“acgttcgt” 字长设定为 3:Acg cgt gtt ttc tcg cgt (六个word)BLAST基本原理基本原理Step 2n n1）找到待搜索序列单词的字母匹配组合，以计）找到待搜索序列单词的字母匹配组合，以计分规则打分，选择阈值，淘汰低于阈值的字符串分规则打分，选择阈值，淘汰低于阈值的字符串 举例举例: Word “ Word “gttgtt” ” 以以gttgtt 作为检索字符串，在数据库中搜索。作为检索字符串，在数据库中搜索。 那么数据库中的待搜那么数据库中的待搜索的索的word word 有多少个？有多少个？ 组合单词有组合单词有3 3个字母，每个位置有个字母，每个位置有4 4个碱基，则个碱基，则4 43 3 =64 =64 计分规则：匹配计分规则：匹配=1=1分分 错配错配=3 =3 分分 ： BLAST基本原理基本原理Step 2“gtt” aaaaaa=-9 =-9 aataat=-5 =-5 aacaac=-9 =-9 aagaag=-9=-9ataata=-5 =-5 attatt=-1 =-1 atcatc=-5 =-5 atgatg=-5=-5 acaaca=-9 act=-5 acc=-9 =-9 act=-5 acc=-9 acgacg=-9=-9agaaga=-9 =-9 agtagt=-5 =-5 agcagc=-9 =-9 aggagg=-9=-9taataa=-9 =-9 tactac=-9 tag=-9 tat=-5 =-9 tag=-9 tat=-5 ttatta=-5 =-5 tttttt=-1 =-1 ttcttc=-5 =-5 ttgttg=-5=-5 tcatca=-9 =-9 tcttct=-5 =-5 tcctcc=-9 =-9 tcgtcg=-9=-9tgatga=-9 =-9 tgttgt=-5 =-5 tgctgc=-9 =-9 tggtgg=-9=-9 caacaa=-9 cat=-5 =-9 cat=-5 caccac=-9 =-9 cagcag=-9=-9ctacta=-5 =-5 cttctt=-1 =-1 ctcctc=-5 =-5 ctgctg=-5=-5 ccacca=-9 =-9 cctcct=-5 =-5 cccccc=-9 =-9 ccgccg=-9=-9cgacga=-9 =-9 cgtcgt=-5 =-5 cgccgc=-9 =-9 cggcgg=-9=-9 gaagaa=-5 gat=-1 =-5 gat=-1 gacgac=-5 gag=-5=-5 gag=-5gtagta=-1 =-1 gttgtt=3 =3 gtcgtc=-1 =-1 gtggtg=-1=-1 gcagca=-5 =-5 gctgct=-1 =-1 gccgcc=-5 =-5 gcggcg=-5=-5ggagga=-5 =-5 ggtggt=-1 =-1 ggcggc=-5 =-5 gggggg=-5=-5设定阈值设定阈值n n设定阈值为-2，对所有的Word进行筛选 aaaaaa=-9 =-9 aataat=-5 =-5 aacaac=-9 =-9 aagaag=-9=-9ataata=-5 =-5 attatt=-1=-1 atcatc=-5 =-5 atgatg=-5=-5 acaaca=-9 act=-5 acc=-9 =-9 act=-5 acc=-9 acgacg=-=-9 9agaaga=-9 =-9 agtagt=-5 =-5 agcagc=-9 =-9 aggagg=-=-9 9taataa=-9 =-9 tactac=-9 tag=-9 tat=-5 =-9 tag=-9 tat=-5 ttatta=-5 =-5 tttttt=-1=-1 ttcttc=-5 =-5 ttgttg=-5=-5 tcatca=-9 =-9 tcttct=-5 =-5 tcctcc=-9 =-9 tcgtcg=-9=-9tgatga=-9 =-9 tgttgt=-5 =-5 tgctgc=-9 =-9 tggtgg=-9=-9 caacaa=-9 cat=-5 =-9 cat=-5 caccac=-9 =-9 cagcag=-9=-9ctacta=-5 =-5 cttctt=-1=-1 ctcctc=-5 =-5 ctgctg=-5=-5 ccacca=-9 =-9 cctcct=-5 =-5 cccccc=-9 =-9 ccgccg=-9=-9cgacga=-9 =-9 cgtcgt=-5 =-5 cgccgc=-9 =-9 cggcgg=-9=-9 gaagaa=-5 =-5 gat=-1gat=-1 gacgac=-5 gag=-5=-5 gag=-5gtagta=-=-1 1 gttgtt=3=3 gtcgtc=-1 =-1 gtggtg=-1=-1 gcagca=-5 =-5 gctgct=-1=-1 gccgcc=-5 =-5 gcggcg=-5=-5 ggagga=-5 =-5 ggtggt=-1=-1 ggcggc=-5 =-5 gggggg=-5=-5 n n以筛选出的每个序列组合（word)对数据库中的每个序列进行扫描，以期找到种子序列匹配的部分。 例： 以以attatt 为种子序列，在数据库中搜索。为种子序列，在数据库中搜索。为种子序列，在数据库中搜索。为种子序列，在数据库中搜索。 找到若干条找到若干条找到若干条找到若干条包含种子序列的目标序列。包含种子序列的目标序列。包含种子序列的目标序列。包含种子序列的目标序列。 如：序列如：序列如：序列如：序列A : A : tctc attatt cgacga 序列序列序列序列B: B: tgtg attatt caacaa 序列序列序列序列C: ac C: ac attatt cctcctBLAST基本原理基本原理Step 3n n获得HSP片段 将待检索序列，与目标序列进行匹配。种子向左向右延伸将待检索序列，与目标序列进行匹配。种子向左向右延伸至计分不再增加，于是就获得了一个至计分不再增加，于是就获得了一个HSPHSP片段。片段。 例：例： 待搜索序列：待搜索序列： ac ac gttgtt cgtcgt 序列序列序列序列A :A : tctc attatt cgacga 两序列序列进行匹配两序列序列进行匹配: : 待搜索序列：待搜索序列： a ac c gttgtt cgcgt t 序列序列序列序列A :A : t tc c attatt cgcga a HSPHSP片段片段1 1： cattcgcattcg BLAST基本原理基本原理Step 4 待搜索序列：待搜索序列： ac ac gttgtt cgtcgt 序列序列序列序列B :B : tgtg attatt caacaa 两序列序列进行匹配两序列序列进行匹配: : 待搜索序列：待搜索序列： ac ac gttgtt c cgtgt 序列序列序列序列B :B : tgtg attatt c caaaa HSPHSP片段片段2 2： attcattc 待搜索序列：待搜索序列： ac ac gttgtt cgtcgt 序列序列序列序列C :C : acac attatt cctcct 两序列序列进行匹配两序列序列进行匹配: : 待搜索序列：待搜索序列： ac ac gttgtt c cgtgt 序列序列C:C: acac attatt c cctct HSPHSP片段片段3 3： acattcacattc BLAST基本原理基本原理Step 4HSP片段片段1： cattcgHSP片段片段2： attcHSP片段片段3： acattcn n筛选HSP片段设定一个阈值删去某些低分的结果。例：设定阈值为例：设定阈值为例：设定阈值为例：设定阈值为+1+1，匹配，匹配，匹配，匹配 +1 +1 错配错配错配错配 -3 -3 目标序列目标序列目标序列目标序列 ： ac ac gttgtt cgtcgtHSPHSP片段片段片段片段1 1： c c attatt cg cg （1-3+1+1+1+1=2)1-3+1+1+1+1=2)HSPHSP片段片段片段片段2 2： attatt c (-3+1+1+1=0) c (-3+1+1+1=0)HSPHSP片段片段片段片段3 3： ac ac attatt c (1+1-3+1+1+1=2) c (1+1-3+1+1+1=2) 则删除则删除则删除则删除HSP2,HSP2,保留保留保留保留HSP1HSP1和和和和HSP3 HSP3 BLAST基本原理基本原理Step 5n n统计各HSP片段的分值（Score)和E值 n n分值(Score): 是衡量查询序列同命中序列间相似性的测度。分值越高，命中序列与查询序列越相似。n nE值: 又称期望值。是随机产生一个比所得分值高的对位排列的概率，即分值可靠性的测度。 E值越小, 所命中序列越可靠。BLAST基本原理基本原理Step 6E值计算公式值计算公式E = K m n e -Sn nK， 一个与目标序列相关的经验常数 n n ，与计分（分值）系统相关的经验常数n nm，查询序列大小n nn，所查询数据库大小n nS，分值主要的主要的BLAST程序程序n n基因组BLASTn n基本BLASTn n特殊类型数据库的搜索基本基本BLAST程序程序程序名查询序列数据库搜索方法Blastn核酸核酸用核酸序列搜索核酸数据库Blastp蛋白质蛋白质用蛋白质序列搜索蛋白质数据库Blastx核酸蛋白质用核酸序列搜索蛋白质数据库（核酸序列6框翻译成蛋白质序列后和蛋白质数据库中的序列逐一搜索。Tblastn蛋白质核酸用蛋白质序列搜索核酸序列据库（先将核酸数据库中的序列按照6框翻译为蛋白序列然后逐一比对）TBlastx核酸核酸将查询序列和数据库中的序列都按照6个可读框翻译为蛋白序列后再比对如何获得如何获得BLAST服务服务 NCBI主站点： http:/www.ncbi.nlm.nih.gov/BLAST/(网络版) ftp:/ftp.ncbi.nlm.nih.gov/blast/ (单机版)为何使用为何使用BLAST？BLASTBLAST结果会列出跟查询序列相似性比较高结果会列出跟查询序列相似性比较高结果会列出跟查询序列相似性比较高结果会列出跟查询序列相似性比较高符合限定要求的序列结果，根据这些结果可符合限定要求的序列结果，根据这些结果可符合限定要求的序列结果，根据这些结果可符合限定要求的序列结果，根据这些结果可以获取以下一些信息：以获取以下一些信息：以获取以下一些信息：以获取以下一些信息：1. 1.查询序列可能具有某种功能查询序列可能具有某种功能2. 2.查询序列可能是来源于某个物种查询序列可能是来源于某个物种3. 3.查询序列可能是某种功能基因的同源基因查询序列可能是某种功能基因的同源基因4. 4.未知新序列的鉴定未知新序列的鉴定BLAST实例实例n nGGAACACTCATCGACGCCGTGAACAAGCGGGGCAAAAAACAAAGGAACACTCATCGACGCCGTGAACAAGCGGGGCAAAAAACAAAACAAAAGAGGAGGGAATGAAAGCTCGATCATGTGGCTTGCCAGCACAAAAGAGGAGGGAATGAAAGCTCGATCATGTGGCTTGCCAGCTTGGCAATTATAACAGCCTGTGCCGGAGCCATGAAGCTATCAAACTTGGCAATTATAACAGCCTGTGCCGGAGCCATGAAGCTATCAAACTTTCAAGGAAAGCTCCTGATGACCATCAACAACACGGACATTGCTTTCAAGGAAAGCTCCTGATGACCATCAACAACACGGACATTGCGGACGTTATCGTGATCCCCACCTCAAAAGGTGAGAACAGATGTTGGACGTTATCGTGATCCCCACCTCAAAAGGTGAGAACAGATGTTGGGTCCGAGCAATCGACGTTGGTTACATGTGTGAAGACACCATCGGGTCCGAGCAATCGACGTTGGTTACATGTGTGAAGACACCATCACGTACGAATGTCCGAAGCTTGCCGTGGGCAACGATCCGGAGGAACGTACGAATGTCCGAAGCTTGCCGTGGGCAACGATCCGGAGGATGTGGACTGCTGGTGCGACAATCAAGAAGTCTACGTGCAGTATGTGTGGACTGCTGGTGCGACAATCAAGAAGTCTACGTGCAGTATGGTCGCTGCACACGGACCAGGCATTCCAAACGAAGCAGAAGATCCGTCGCTGCACACGGACCAGGCATTCCAAACGAAGCAGAAGATCCGTTTCGGTCCAAACGCATGGGGAAAGCTCACTCGTGAACAAAAAGTTTCGGTCCAAACGCATGGGGAAAGCTCACTCGTGAACAAAAAAGAGGCTTGGCTGGATTCAACGAAGGCCACGCGATACCTCATGAAGAGGCTTGGCTGGATTCAACGAAGGCCACGCGATACCTCATGAAAACGGAGAATTGGATCATAAGGAACCCTGGATATGCTTTCCTGGAAACGGAGAATTGGATCATAAGGAACCCTGGATATGCTTTCCTGGCGGCGGCACTTGGATGGATGCTTGGCAGCAACAGTGGCCAACGTCGGCGGCACTTGGATGGATGCTTGGCAGCAACAGTGGCCAACGTGTGGTGTTCACCATTCTCTTGCTGTTGGTCGCTCCGGCTTACAGCGTGGTGTTCACCATTCTCTTGCTGTTGGTCGCTCCGGCTTACAGCTTTAACTGTCTGGGAATGGGGAATCGGGATTTCATTTTAACTGTCTGGGAATGGGGAATCGGGATTTCATn n 这是什么序列？这是什么序列？http:/blast.ncbi.nlm.nih.gov/Blast.cgiBLAST任务提交（任务提交（1）1.序列信息部分填入查询（query）的序列序列范围（默认全部）选择搜索数据库如果接受其他参数默认设置，点击开始搜索Blast任务提交（任务提交（2）设置搜索的范围，entrez关键词，或者选择特定物种2.设置各种参数部分一些过滤选项，包括简单重复序列，人类基因组中的重复序列等E值上限种子长度如果你对blast的命令行选项熟悉的话，可以在这里加入更多的参数BLAST结果（结果（1）1 1）查询序列的描述）查询序列的描述2 2）显示比对区域的）显示比对区域的框图框图3 3）被搜索到的序列）被搜索到的序列信息信息4 4）比对结果）比对结果5 5）统计信息与算法）统计信息与算法过程的参数过程的参数BLAST结果（结果（1-1）查询序列的描述显示比对区域的框图BLAST结果（结果（1-2）BLAST结果（结果（1-3）被搜索到的序列信息BLAST结果（结果（1-4）比对结果BLAST结果（结果（1-5）统计信息与算法过程的参数BLAST结果（结果（1-4）比对结果BLAST结果（结果（1-5）统计信息与算法过程的参数BLAST结果（结果（1-6）BLAST命中序列的系统进化树常规常规BLAST分析流程总结分析流程总结1.登陆blast主页 http:/www.ncbi.nlm.nih.gov/BLAST/2.根据数据类型，选择合适的程序3.填写表单信息4.提交任务5.查看和分析结果n n热球菌（Pyrococcus abyssi) n n全基因组序列中，有一段重复序列多次出现。n n重复序列特征：18个碱基组成。 序列信息： GTTCC AATAA GACTA AAABLAST搜索发现序列的生物意义搜索发现序列的生物意义n nPyrococcus abyssi GTTCC AATAA GACTA AAA repeat sequence n n随机出现的序列？VS 具有生物学意义的序列？BLAST搜索发现序列的生物意义搜索发现序列的生物意义（2）n nPyrococcus abyssin n环状DNA的全长为1765118 bpn nrepeat sequence GTTCC AATAA GACTA AAA 为随机序列的概率。n n出现一次的概率： （1765118-17）*4-18 = 2.57*10-5 重复出现的概率则更小BLAST搜索发现序列的生物意义搜索发现序列的生物意义（3）n nBLASTN 进行相似性检索，n n参数取E为10，结果参数报告：BLAST搜索发现序列的生物意义搜索发现序列的生物意义（4）n n数据库中序列平均长度：数据库中序列平均长度： 37599093033/14584226257837599093033/145842262578n n数据库中长度为数据库中长度为1818的字符串数：的字符串数： （2578-172578-17）* *14584226=3.7*1014584226=3.7*101010 一个序列产生的一个序列产生的1818个字符的个字符的WORD*WORD*共有共有1458422614584226个序列，则一共个序列，则一共 3.7*103.7*101010个个长度为长度为1818的字符。的字符。n n数据库中出现特定序列的概率数据库中出现特定序列的概率 3.7*103.7*1010 10 4 4-18-18 = =0.570.57 这个结果和搜索结果给出的这个结果和搜索结果给出的E E值值=0.96 =0.96 很接近，因此我们判很接近，因此我们判断断E E数值为数值为0.960.96的序列的击中事件绝非偶然。的序列的击中事件绝非偶然。 BLAST搜索发现序列的生物意义搜索发现序列的生物意义（5）BLAST搜索发现序列的生物意义搜索发现序列的生物意义（6）BLAST搜索发现序列的生物意义搜索发现序列的生物意义（7）n nGTTCC AATAA GACTA AAA 是一段出现在嗜热菌属全基因组中（Pyrococcus ）的序列并且多次重复出现。n n这种重复的序列只存在于嗜热菌属的3个种中，因此将这段序列作为该属的标记序列，可以广泛的应用于嗜热菌属分类与环境监测的实践中。新序列的提交新序列的提交为什么要向公共数据库提交序列为什么要向公共数据库提交序列n n数据的共享 全球研究者的集体智慧 推动生物医学领域的快速发展n n趋势 所有的生物医学期刊发表文章，均要求作者提供相关的新序列的数据库录入号通过何种途径提交新的序列？通过何种途径提交新的序列？n nGenBank：BankIt 、Sequin n nEMBL-EBI: WEBIN （bulk submission procedure . Third Party Annotation）n nDDBJ: SAKURA 、Mass Submission System (MSS) 通过通过BankIt 提交新的序列提交新的序列(1)NCBI HOMEPAGE通过通过BankIt 提交新的序列提交新的序列(2)通过通过BankIt 提交新的序列提交新的序列(3)通过通过BankIt 提交新的序列提交新的序列(4)提交提交序列序列长度长度通过通过BankIt 提交新的序列提交新的序列(5)n本次提交的查询本次提交的查询码码 bankit 789323n需要填写的序列需要填写的序列信息：信息：1.综合的序列提交综合的序列提交信息（条目数，联信息（条目数，联络信息，发布时间络信息，发布时间要求等）要求等）2.序列的背景信息序列的背景信息3.序列的来源信息序列的来源信息4.序列本身的信息序列本身的信息通过通过BankIt 提交新的序列提交新的序列(6)n作者信息n作者通信信息通过通过BankIt 提交新的序列提交新的序列(7)序列发序列发表时间表时间的信息的信息通过通过BankIt 提交新的序列提交新的序列(8)序列测定序列测定者的信息者的信息通过通过BankIt 提交新的序列提交新的序列(9)序列序列的来的来源及源及背景背景信息信息通过通过BankIt 提交新的序列提交新的序列(6)输入序输入序列本身列本身的信息的信息通过通过BankIt 提交新的序列提交新的序列(7)补充输入序列的注释信息补充输入序列的注释信息Validate and Continue 下一步下一步 完成序列提交完成序列提交Submit to GenBank通过通过BankIt 提交新的序列提交新的序列(8)48H 后，后，GenBank 会给序列提交者发送一封邮会给序列提交者发送一封邮件，并分配相应的件，并分配相应的Accession Number.这时候这时候基本完成了序列的提交。基本完成了序列的提交。通过通过BankIt 提交新的序列提交新的序列优点：优点：操作界面友好操作界面友好简单简单缺点：缺点：受网络环境的影响巨大受网络环境的影响巨大效率不高效率不高通过通过Sequin提交新的序列提交新的序列(1)NCBI 下载下载Sequin 软件软件双击双击 Sequin 图标图标n n版本版本 11.011.0n n2011. 1.25 2011. 1.25 发布发布n n可以选择向可以选择向 GB GB 或或EMBLEMBL 提交序列提交序列n n同步显示帮助同步显示帮助信息信息通过通过Sequin提交新的序列提交新的序列(2)通过通过Sequin提交新的序列提交新的序列(3)n输入数据发布的时间立即发布指定日期发布n发表序列文章的暂定名称通过通过Sequin提交新的序列提交新的序列(4)输入通讯作者的信息通过通过Sequin提交新的序列提交新的序列(4)输入测序作者的信息通过通过Sequin提交新的序列提交新的序列(5)输入测序机构信息通过通过Sequin提交新的序列提交新的序列(7)进入序列提交进入序列提交模式：模式：选择常规序列选择常规序列提交对话方式提交对话方式通过通过Sequin提交新的序列提交新的序列(8)被提交序列的类型被提交序列的格式被提交序列的性质通过通过Sequin提交新的序列提交新的序列(8)通过通过Sequin提交新的序列提交新的序列(9)物种名和序列表格物种名和序列表格包括三页：物种页核酸表格页蛋白页该页随前一个序列格式页的提交种类而发生相应的调整。如果输入单个核酸序列信息，则该页面要求输入相关的氨基酸序列；如果输入一个种群、系统发育研究，这一页就变成注释页面，需要提交者提供具体的注释信息）通过通过Sequin提交新的序列提交新的序列(9-1)核酸序列输入界面：1.对核酸序列修饰及追加输入核酸序列2.清除核酸序列3.指定特点的核酸序列类型4.指定序列的拓扑结构通过通过Sequin提交新的序列提交新的序列(9-1)通过通过Sequin提交新的序列提交新的序列(9-1)通过通过Sequin提交新的序列提交新的序列(9-1)通过通过Sequin提交新的序列提交新的序列(10-1)物种表：物种表：有关序列物种来有关序列物种来源等背景资料源等背景资料包括：包括：1、来源物种名、来源物种名2、序列位置、序列位置3、遗传密码、遗传密码通过通过Sequin提交新的序列提交新的序列(10-1)物种名栏：包含多种生物的系统命名，采用滚动栏的方式呈现。使用特点：1.在输入栏输入该系统命名的首字母，则只能移动到正确的位置以供选择。 2.物种名称一但确定，则系统常用名栏和用来翻译的遗传密码也将自动填写。 3.如果所研究的物种不在所列的目录中，可以自行填写物种的名称。 通过通过Sequin提交新的序列提交新的序列(10-1)序列位置栏目：提交序列的位置 ，绝大多数的序列均位于基因组中。但有一些位于特殊的载体介质中。 通过通过Sequin提交新的序列提交新的序列(10-1)通过通过Sequin提交新的序列提交新的序列(10-1)通过通过Sequin提交新的序列提交新的序列(10-1)通过通过Sequin提交新的序列提交新的序列(10-1)保存序列，准备提交至保存序列，准备提交至GenBanK发送邮件发送邮件通过通过Sequin提交新的序列提交新的序列(11)发送邮件发送邮件 gb-subncbi.nlm.nih.gov 通过通过Sequin提交新的序列提交新的序列(11)回复邮件回复邮件 n n至此，恭喜你完成了人生第一次向GenBank提交序列！n n走向科研的道路继续向前。n n 生物信息学实验生物信息学实验 一一n n实验项目：实验项目： 了解常用的数据库，独立完成数据库查询与搜索了解常用的数据库，独立完成数据库查询与搜索 时间：时间：周四：周四：1212（第一组，（第一组，3030人）人） 34 34 （第二组，（第二组，3030人）人） 56 56 （第三组，（第三组，3030人）人） 78 78 （第四组，（第四组，3030人）人）地点：地点：13-44313-443第一组名单第一组名单第二组名单第二组名单第三组名单第三组名单第四组名单第四组名单