后缀树的应用.ppt

《后缀树的应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章后缀树的应用精确字符串匹配问题最长重复子串问题最长公共子串问题DNA污染问题多字符串的公共子串问题遇难者身份识别问题最长公共前缀问题回文问题......生物信息学概论讲义后缀树的应用精确字符匹配（ESM）生物应用识别DNA序列中的起始密码子ATG（RNA的转录翻译起始点）问题定义给定长度为n的字符串S,对任意长度为m的查询Q,要求发现S中所有Q的发生位置生物信息学概论讲义后缀树的应用精确字符匹配（ESM）解决方案预处理：构建字符串S的后缀树O(n)查询：自根向下,根据路径标识向下匹配查询Q至节点x。如果不存在这样的节点x,则Q不在

2、S中。O(m)节点x的子树中,每个叶子对应Q在字符串S中的一个发生。对节点x的子树,需要一次遍历。O(k)ESM的后缀树解决方案要好于其它的解决方案m+k<

3、重复序列引起的问题定义给定长度为n的字符串S，发现其中的最长重复子串字符串S中的子串和形成了一个最长重复子串，当且仅当：(1)=(2)最左(或右)侧的字符不等于最左(或右)侧的字符(3)的长度大于任何其它重复子串'的长度生物信息学概论讲义后缀树的应用最长重复子串（LRS）解决方案构建字符串S的后缀树O(n)遍历后缀树发现最深的内部节点vO(n)每个内部节点的路径标识对应一个重复子串节点v的路径标识对应最长重复子串注意，此处的节点深度是指节点的字符串深度后缀树结构出现之前，算法的时间复杂度为O(n2)利用后缀树之后，算法的

4、时间复杂度变为O(n)生物信息学概论讲义后缀树的应用最长重复子串（LRS）例给定S=acacag,发现S中的最长重复子串acacag$g$g$135cacag$g$24g$6$7QS中的最长重复子串为aca生物信息学概论讲义后缀树的应用最长公共子串（LCS）生物应用发现多个序列的同源性(回想曾经介绍过的序列比对)问题定义给定字符串P1,P2,…,Pk(k>1),发现它们的最长公共子串1970年，在后缀树出现以前，DonKnuth曾断言不可能存在线性时间复杂度的算法解决最长公共子串问题。然而，使用后缀树恰恰完成了这个“不可能完成的任务”生

5、物信息学概论讲义后缀树的应用最长公共子串（LCS）解决方案在每个字符串的末尾添加不同的终结符O(k)构建n个字符串的广义后缀树O(n)标记树中拥有代表来自所有k个字符串后缀的内部节点O(n)输出字符串深度最大的标记节点O(1)后缀树结构出现之前，算法的时间复杂度为O(n2)利用后缀树之后，算法的时间复杂度变为O(n)生物信息学概论讲义后缀树的应用最长公共子串（LCS）例给定P1=acgat,P2=cgt,两者的最长公共子串为cgag5#6$4cgat#1t#4cgat#2t$1at#3t$2t#$3生物信息学概论讲义后缀树的应用DNA污

6、染问题生物应用如何准确的测定DNA序列（难道恐龙更接近人，而不是更像鸟或者鳄鱼?）问题定义给定一个新测序的DNA序列S1和一个来自可能的污染物的DNA序列S2,发现S2中所有出现在S1中且长度超过给定阈值x的子串如果S2中的某个子串出现在S1中，S1可能已经被污染了生物信息学概论讲义后缀树的应用DNA污染问题解决方案构建S1和S2的广义后缀树O(n)标记树中拥有代表来自字符串S1和S2后缀的内部节点O(n)输出所有字符串深度大于阈值x的标记节点O(1)DNA污染问题是最长公共子串问题的变种(发现长度大于x的公共子串)生物信息学概论讲义后

7、缀树的应用DNA污染问题例给定S1=acacag$,S2=aca#,x=2,判断S1是否已被污染S1已被污染,存在一个公共的长度>2的子串aca生物信息学概论讲义后缀树的应用多字符串的公共子串生物应用识别两个或多个基因组的保守区域，探索生物结构的本质特征问题定义给定K个字符串,对所有的k(2kK),计算至少被k个字符共有的最长公共子串的长度l(k)多字符串的公共子串问题是最长公共子串问题的变种生物信息学概论讲义后缀树的应用多字符串的公共子串解决方案在每个字符串的末尾添加不同的终结符O(k)构建n个字符串的广义后缀树O(n)遍历建立的

8、广义后缀树,计算每一个内部节点的C(v)值O(Kn)C(v)代表以节点v为根的子树中不同终结符的数目遍历广义后缀树,对每个内部节点v,如果l(C(v))