基于Q-gram过滤的海量基因序列比对算法研究课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,基于,Q-gram,过滤的,海量基因序列比对算法研究,基于Q-gram过滤的,2,算法实现,1,研究,意义,3,实验结果,4,总结,2,2算法实现1研究意义3实验结果4总结2,1,研究,意义,2,算法实现,3,实验结果,4,总结,3,1研究意义2算法实现3实验结果4总结3,序列比对,S1,（已知功能的序列,）,=TAAGGAGCAAGGGCTTGACATCAAA,S2,（未知,功能的序列）,=AAGGAGCAAGGGCTTGACATCATAC,T,A,A,G,G,A,G,C,A,A,G,G,G,C,T,T,G,A,C,A,T,C,A,-,A,A,-,A,A,G,G,A,G,C,A,A,G,G,G,C,T,T,G,A,C,A,T,C,A,T,A,C,4,序列比对S1（已知功能的序列）=TAAGGAGCAAGGG,1,研究,意义,2,算法实现,3,实验结果,4,总结,5,1研究意义2算法实现3实验结果4总结5,2,算法实现,6,基因序列数据库,过滤算法,候选,数据库,比对,算法,比,对结果,过滤算法,比,对算法,2算法实现6基因序列数据库过滤算法候选数据库比对算法比对结果,过滤算法,7,Q-gram,距离函数（简单且高效）,核心：相似度衡量,过滤算法7Q-gram距离函数（简单且高效）核心：相似度衡,Q-gram,定义,:,(q=4,d=1),ATCGATCGAT,过滤算法,ATCG,TCGA,CGAT,ATCG TCGA CGAT,GATC,8,Q-gram定义:(q=4,d=1)过滤算法ATCG T,过滤算法,预处理阶段,输入阶段,过滤阶段,验证阶段,输出阶段,9,过滤算法预处理阶段9,过滤算法,预处理阶段,10,ID1:ACCACAC,ID2:CACCAAC,ACC,CCA,AAC,ACA,CAC,q-gram,倒排索引,索引项,地址列表：地址项,过滤算法预处理阶段10ID1:ACCACACACC1,过滤,算法,输入,阶段,查询,序列,误差范围,过滤,阶段,验证,阶段,输出,阶段,输出到文件,为比对算法提供数据,11,过滤器,过滤算法输入阶段查询序列过滤阶段验证阶段输出阶段输出到文件1,过滤,算法,数量过滤器,（最早的,q-gram,过滤定理）,ed(A,B)t,的必要条件,是,|,grams(A)grams(B)|max(|A|,|B|)-,q+1-tq,长度过滤器,若,ed(A,B)t,，则,|A-B|,t,位置过滤器,若,ed(A,B)t,，序列,A,中的任意,q-gram,与序列,B,中该,q-gram,的位置相差一定在,t,的范围之内,Q-gram,基本过滤器,12,过滤算法数量过滤器（最早的q-gram过滤定理）Q-gram,过滤,算法,前缀,过滤器,q,a,q,b,q,u,q,v,?,?,?,?,?,?,?,?,x:,y:,q,c,q,w,q*t+1,l-q*t-1=LB,str(x);str(y),-1,L,假设,x,，,y,为序列,A,，,B,的两个,q-gram,数组：,若,ed(A,B)t,，,则,A,和,B,的,qt+1,个前缀,q-gram,中,至少,要有一个公共的匹配,q-gram,13,过滤算法前缀过滤器qaqbquqv?x:y:q,过滤,算法,前缀,过滤器,q,a,q,b,q,u,q,v,?,?,?,?,?,?,?,?,x:,y:,q,c,q,w,q*t+1,l-q*t-1=LB,str(x);str(y),-1,L,传统,做法：直接选取每个序列的前,qt+1,个,q-gram,Zipf,定律：,一个单词出现的频率与它在,频率表里,的排名成,反比,统计,q-gram,的出现次数,14,过滤算法前缀过滤器qaqbquqv?x:y:q,过滤,算法,误配过滤器,位置误配：非聚集编辑,错误（,最少,编辑,错误,）,内容误配：聚集编辑错误,15,过滤算法误配过滤器位置误配：非聚集编辑错误（最少编辑错误）1,过滤,算法,16,过滤顺序模型,基本过滤器,(LPC),Length_Filter();,Position_Filter();,Count_Filter();,ED_Filter();,过滤算法16过滤顺序模型 基本过滤器(LPC),过滤,算法,All-Pairs-Ed,/,过滤阶段,Prefix_Filter,();,Length_Filter,();,Position_Filter,();,/,验证阶段,Count_Filter,();,Mismatch_Filter();,ED_Filter();,17,过滤顺序模型,Ed-join,/,过滤阶段,MinimumPrefix_Filter,();,Length_Filter,();,Position_Filter();,/,验证阶段,Count_Filter();,Mismatch_Filter();,ED_Filter();,最小前缀,长度,(MinimumPrefix):,min(,前缀长度，最少编辑错误,),过滤算法 All-Pairs-Ed17过滤顺序模型,2,算法实现,过滤算法,比,对算法,18,计算阶段,回溯,阶段,2算法实现过滤算法18计算阶段回溯阶段,比对,算法,计算得分矩阵,19,A,G,A,C,G,T,T,A,A,C,G,T,A,C,G,T,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,X,Needleman-Wunsch,全局比对算法,比对算法计算得分矩阵19AGACGTTAACGTACGT00,比对,算法,计算得分矩阵,20,A,G,A,C,G,T,T,A,A,C,G,T,A,C,G,T,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,X,Needleman-Wunsch,全局比对算法,比对算法计算得分矩阵20AGACGTTAACGTACGT00,比对,算法,计算得分矩阵,21,A,G,A,C,G,T,T,A,A,C,G,T,A,C,G,T,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,1,2,2,2,3,3,3,3,1,2,2,2,3,4,4,4,1,2,3,4,4,4,4,5,1,2,3,3,3,4,4,5,1,2,3,4,5,5,5,5,1,2,3,4,5,6,6,6,0,0,0,0,0,0,0,0,0,X,Needleman-Wunsch,全局比对算法,比对算法计算得分矩阵21AGACGTTAACGTACGT00,比对,算法,22,A,G,A,C,G,T,T,A,A,C,G,T,A,C,G,T,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,1,2,2,2,3,3,3,3,1,2,2,2,3,4,4,4,1,2,3,4,4,4,4,5,1,2,3,3,3,4,4,5,1,2,3,4,5,5,5,5,1,2,3,4,5,6,6,6,0,0,0,0,0,0,0,0,0,回溯,阶段,X,比对算法22AGACGTTAACGTACGT00000000,比对,算法,23,A,G,A,C,G,T,T,A,A,C,G,T,A,C,G,T,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,1,2,2,2,3,3,3,3,1,2,2,2,3,4,4,4,1,2,3,4,4,4,4,5,1,2,3,3,3,4,4,5,1,2,3,4,5,5,5,5,1,2,3,4,5,6,6,6,0,0,0,0,0,0,0,0,0,回溯,阶段,_,A,T,T,ACGTACG_,A_G_ACGT,X,比对算法23AGACGTTAACGTACGT00000000,比对,算法,Control,ALU,ALU,ALU,ALU,Cache,DRAM,DRAM,CPU,GPU,GPU,实现,24,计算单元,控制单元,数据缓存,NVIDIA,：,CUDA,平台,GPU,与,CPU,的架构不同,比对算法ControlALUALUALUALUCacheDR,比对,算法,GPU,实现难点,Shared Memory,Registers,Registers,Thread(0,0),Thread(1,0),Block(0,0),Shared Memory,Registers,Registers,Thread(0,0),Thread(1,0),Block(1,0),Global Memory,Constant Memory,Host,Grid,Tesla GPU,计算能力为,1.3,：,每个,SM,（计算核心）允许,16KB,共享内存,字符串为,32,个字符长,需要,1KB,存储,得分矩阵,每个,SM,可包含,16,个线程,不足以隐藏,延迟,字符串为,128,个字符长,需要,16KB,存储,得分矩阵,每个,SM,包含,1,个线程,不足以并行,25,CUDA,存储器模型,比对算法GPU实现难点Shared MemoryRegist,比对,算法,计算得分矩阵,计算阶段：保留矩阵的两个,连续行,数,字符串为,32,个字符长,分块为,8*8,第一阶段：需要,32*2,个字节,26,A,G,A,C,G,T,T,A,A,C,G,T,A,C,G,T,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,1,2,2,2,3,3,3,3,1,2,2,2,3,4,4,4,1,2,3,4,4,4,4,5,1,2,3,3,3,4,4,5,1,2,3,4,5,5,5,5,1,2,3,4,5,6,6,6,0,0,0,0,0,0,0,0,0,X,1,2,3,比对算法计算得分矩阵计算阶段：保留矩阵的两个连续行数字符串为,比对,算法,27,A,G,A,C,G,T,T,A,A,C,G,T,A,C,G,T,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,1,3,1,3,1,4,1,2,3,3,3,4,4,5,1,5,1,5,0,0,0,0,0,0,0,0,0,X,回溯阶段,：分块思想,得分矩阵：左边界,，上边界,字符串为,32,个字符长,分块为,8*8,第二阶段：需要,32/8*32/8*32,个,字节存储边界,需要,8*8,个字节计算每个分块的,内容,回溯,阶段,比对算法27AGACGTTAACGTACGT00000000,比对,算法,28,A,G,A,C,G,T,T,A,A,C,G,T,A,C,G,T,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,1,3,1,3,1,？,4,4,4,5,1,2,3,3,3,4,4,5,1,5,5,5,5,1,5,6,6,6,0,0,0,0,0,0,0,0,0,X,字符串为,32,个字符长,分块为,8*8,第二阶段：需要,32/8*32/8*32,个,字节存储边界,需要,8*8,个字节计算每个分块的内容,回溯,阶段,回溯阶段,：分块思想,得分矩阵：左边界,，上边界,比对算法28AGACGTTAACGTACGT00000000,比对,算法,29,A,G,A,C,G,T,T,A,A,C,G,T,A,C,G,T,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,1,3,1,？,3,1,2,3,4,4,4,4,5,1,2,3,3,3,4,4,5,1,2,3,4,5,5,5,5,1,2,3,4,5,6,6,6,0,0,0,0,0,0,0,0,0,X,回溯,阶段,字符串为,32,个字符长,分块为,8*8,第二阶段：需要,32/8*32/8*32,个,字节存储边界,需要,8*8,个字节计算每个分块的内容,回溯阶段,：分块思想,得分矩阵：左边界,，上边界,比对算法29AGACGTTAACGTACGT00000000,比对,算法,30,A,G,A,C,G,T,T,A,A,C,G,T,A,C