具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC ...具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path inDAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.展开更多
对比模式挖掘是序列模式挖掘的一个重要分支,带有密度约束的对比模式有助于生物学家发现生物序列中的特殊因子的分布情况。为此,文中提出了MPDG(Mining distinguishing sequence Patterns based on Density and Gap constraint)算法,该...对比模式挖掘是序列模式挖掘的一个重要分支,带有密度约束的对比模式有助于生物学家发现生物序列中的特殊因子的分布情况。为此,文中提出了MPDG(Mining distinguishing sequence Patterns based on Density and Gap constraint)算法,该算法应用网树结构挖掘满足密度约束和间隙约束的对比模式,在仅需扫描一遍序列库的情况下,该算法可计算当前模式的所有超模式的支持度,从而提高挖掘效率。最后,在真实蛋白质数据集上进行实验,实验结果验证了MPDG算法的有效性。展开更多
文摘具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path inDAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.
文摘对比模式挖掘是序列模式挖掘的一个重要分支,带有密度约束的对比模式有助于生物学家发现生物序列中的特殊因子的分布情况。为此,文中提出了MPDG(Mining distinguishing sequence Patterns based on Density and Gap constraint)算法,该算法应用网树结构挖掘满足密度约束和间隙约束的对比模式,在仅需扫描一遍序列库的情况下,该算法可计算当前模式的所有超模式的支持度,从而提高挖掘效率。最后,在真实蛋白质数据集上进行实验,实验结果验证了MPDG算法的有效性。