《后缀树的应用》PPT课件.ppt

生物信息学概论讲义,第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+k2的子串aca,生物信息学概论讲义,后缀树的应用,多字符串的公共子串生物应用识别两个或多个基因组的保守区域，探索生物结构的本质特征问题定义给定K个字符串,对所有的k(2kK),计算至少被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)=3sandollar,handlot,handler,grand(2)l(5)=2sandollar,handlot,handler,grand,pantry,生物信息学概论讲义,后缀树的应用,遇难者身份识别问题生物应用识别遇难者(例如,在战争中死亡的士兵)身份问题定义给定一个长度为m的字符串Q和一个字符串数据库,查找该字符串数据库中所有包含Q的字符串,生物信息学概论讲义,后缀树的应用,遇难者身份识别问题解决方案(1)构建包含数据库中所有字符串的广义后缀树O(n)(2)遍历建立的广义后缀树,发现字符串Q的所有发生位置O(m+occ),生物信息学概论讲义,后缀树的应用,最长公共前缀问题定义给定长度为n的字符串S,对任意的位置i和j,发现S中Suffi和Suffj的最长公共前缀的长度解决方案构建字符串S的后缀树O(n)输出Suffi和Suffj字符串深度最大的公共祖先O(1),生物信息学概论讲义,后缀树的应用,回文问题生物应用特殊位点识别（如:限制性酶剪切位点）问题定义给定长度为n的字符串S,发现S中所有最大的回文给定长度为n的字符串S,发现S中所有最大的互补回文,生物信息学概论讲义,后缀树的应用,回文问题回文给定字符串S中的一个子串u,称其为一个回文,当且仅当u=ur。其中,ur代表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被称为一个最大回文,当且仅当ii+|u|-1,Si.j都不是回文,生物信息学概论讲义,后缀树的应用,回文问题解决方案预处理:构建S和Sr的广义后缀树O(n)执行如下循环:Fori=1ton发现的最长公共前缀。如果最长公共前