后缀树的应用

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,生物信息学概论讲义,*,第4章 后缀树的应用,精确字符串匹配问题,最长重复子串问题,最长公共子串问题,DNA污染问题,多字符串的公共子串问题,遇难者身份识别问题,最长公共前缀问题,回文问题,.,后缀树的应用,精确字符匹配（ESM）,生物应用,识别DNA序列中的起始密码子ATG（RNA的转录翻,译起始点）,问题定义,给定长度为n的字符串S, 对任意长度为m的查询Q, 要,求发现S中所有Q的发生位置,后缀树的应用,精确字符匹配（ESM）,解决方案,预处理：构建字符串S的后缀树 O(n),查询：,自根向下,根据路径标识向下匹配查询,Q,至节点,x,。如果不存在这样的节点,x,则,Q,不在,S,中。,O(,m,),节点,x,的子树中,每个叶子对应,Q,在字符串,S,中的一个发生。对节点,x,的子树,需要一次遍历。,O(,k,),ESM的后缀树解决方案要好于其它的解决方案,m+k1), 发现它们的最长公共子串,1970年，在后缀树出现以前，Don Knuth曾断言不可能存在线性时间,复杂度的算法解决最长公共子串问题。然而，使用后缀树恰恰完成了,这个“不可能完成的任务”,后缀树的应用,最长公共子串（LCS）,解决方案,在每个字符串的末尾添加不同的终结符,O(,k,),构建,n,个字符串的广义后缀树,O(n,),标记树中拥有代表来自所有,k,个字符串后缀的内部节点,O(n,),输出字符串深度最大的标记节点,O(1),后缀树结构出现之前，算法的时间复杂度为O(n,2,),利用后缀树之后，算法的时间复杂度变为O(n),后缀树的应用,最长公共子串（LCS）,例 给定P,1,=acgat, P,2,=cgt, 两者的最长公共子串为cg,a,g,5,#,6,$,4,c,g,a,t,#,1,t,#,4,c,g,a,t,#,2,t,$,1,a,t,#,3,t,$,2,t,#,$,3,后缀树的应用,DNA污染问题,生物应用,如何准确的测定DNA序列（难道恐龙更接近人，而不,是更像鸟或者鳄鱼?）,问题定义,给定一个新测序的DNA序列S,1,和一个来自可能的污染,物的DNA序列S,2, 发现S,2,中所有出现在S,1,中且长度超过,给定阈值x的子串,如果S,2,中的某个子串出现在S,1,中， S,1,可能已经被污染了,后缀树的应用,DNA污染问题,解决方案,构建,S,1,和,S,2,的广义后缀树,O(n,),标记树中拥有代表来自字符串,S1,和,S2,后缀的内部节点,O(n,),输出所有字符串深度大于阈值,x,的标记节点,O(1),DNA污染问题是最长公共子串问题的变种(发现长度大于x的公共子串),后缀树的应用,DNA污染问题,例 给定,S,1,=,acacag$,S,2,=,aca#,x=2, 判断S,1,是否已被污染,S,1,已被污染, 存在一个公共的,长度,2,的子串aca,后缀树的应用,多字符串的公共子串,生物应用,识别两个或多个基因组的保守区域，探索生物结构的,本质特征,问题定义,给定K个字符串, 对所有的k (2,k,K), 计算至少被,k,个,字符共有的最长公共子串的长度,l,(,k,),多字符串的公共子串问题是最长公共子串问题的变种,后缀树的应用,多字符串的公共子串,解决方案,在每个字符串的末尾添加不同的终结符,O(,k,),构建,n,个字符串的广义后缀树,O(n,),遍历建立的广义后缀树,计算每一个内部节点的,C(,v,),值,O(Kn,),C(,v,),代表以节点,v,为根的子树中不同终结符的数目,遍历广义后缀树,对每个内部节点,v,如果,l,(C(,v,),v,的字符串深度,令,l,(C(,v,)=,v,的字符串深度,O(n,),后缀树的应用,多字符串的公共子串,例 给定字符串集合,S=sandollar, handlot, handler, grand, pantry，,计算,l,(4)和,l,(5),l,(4)=3,s,and,ollar,h,and,lot, h,and,ler, gr,and,(2),l,(5)=2,s,an,dollar,h,an,dlot, h,an,dler, gr,an,d, p,an,try ,后缀树的应用,遇难者身份识别问题,生物应用,识别遇难者 (例如, 在战争中死亡的士兵)身份,问题定义,给定一个长度为m的字符串Q和一个字符串数据库, 查,找该字符串数据库中所有包含Q的字符串,后缀树的应用,遇难者身份识别问题,解决方案,(1) 构建包含数据库中所有字符串的广义后缀树 O(n),(2) 遍历建立的广义后缀树, 发现字符串Q的所有发生位置 O(m+occ),后缀树的应用,最长公共前缀,问题定义,给定长度为n的字符串S, 对任意的位置i和j, 发现S中,Suff,i,和Suff,j,的最长公共前缀的长度,解决方案,构建字符串,S,的后缀树,O(n,),输出,Suff,i,和,Suff,j,字符串深度最大的公共祖先,O(1),后缀树的应用,回文问题,生物应用,特殊位点识别（如: 限制性酶剪切位点）,问题定义,给定长度为,n,的字符串,S,发现,S,中所有最大的回文,给定长度为,n,的字符串,S,发现,S,中所有最大的互补回文,后缀树的应用,回文问题,回文,给定字符串S中的一个子串u, 称其为一个回文, 当且,仅当u=u,r,。其中, u,r,代表u的反转字符串,例如 u=acagaca是一个回文，因为acagaca=(acagaca),r,后缀树的应用,回文问题,回文,如果Si.i+k-1=Srn-i+1.n-i+k, 那么u=Si-k+1.i+k-1,是一个奇数长度的回文,后缀树的应用,回文问题,回文,如果Si.i+k-1=Srn-i+2.n-i+k+1, 那么u=Si-k.i+k-1,是一个偶数长度的回文,后缀树的应用,回文问题,互补回文,给定字符串S中的一个子串u, 称其为一个互补回文,当且仅当u=,r,。其中,代表u的互补字符串,例如 acaugu是一个互补回文,最大回,文,字符串S中的一个回文u=Si.i+|u|-1被称为一个最大,回文, 当且仅当,i,i+|u|-1, Si,.j,都不是回文,后缀树的应用,回文问题,解决方案,预处理: 构建S和S,r,的广义后缀树 O(n),执行如下循环:,For i=1 to n,发现 的最长公共前缀。如果最长公共前缀的长度是,k,找到一个奇数长度的最大回文,Si-k+1.i+k-1 O(1),(2),发现 的最长公共前缀。如果最长公共前缀的长度是,k,找到一个偶数长度的最大回文,Si-k.i+k-1 O(1),