一种基于分支定界的大规模最长公共子序列问题求解方法

技术领域

本发明属于信息技术技术领域，涉及一种基于分支定界的大规模最长公共子序列问题求解方法。

背景技术

序列是日常生活中一种常见的数据形式，如文本信息、生物序列、二进制的数据流等。随着大数据时代的来临，如何在海量的大规模序列信息中挖掘对人类有用的信息和模式有重要的意义。而多序列的最长公共子序列(MLCS)问题是序列数据挖掘领域中一个经典的NP难问题，可以作为序列相似性的衡量手段，有重要的应用。

最长公共子序列问题算法按求解的最终结果可以分为近似算法和精确算法。近似算法指算法运行结束后，可以得到一部分的近似解，但是我们并不知道我们求得的是否为最优解，或是我们是否求得了所有的最优解。而精确算法则指的是算法运行结束后，可以输出所有的最优解。最早的精确算法是基于动态规划的算法，它一般被用于解决两个序列的最长共子序列(LCS)问题，它的算法核心思想是对于长度分别为n和m的两个序列，建立一个n*m的矩阵，然后通过回溯的方式得到最终的答案。然而实际中我们往往需要同时比对的序列远不止两条，对于多序列的最长公共子序列(MLCS)问题，基于动态规划的方法已经被证明是不适用的。

对于多序列的最长公共子序列问题，目前比较有效的是基于支配点的算法和基于无冗余的有向无环图的算法。他们都是通过将问题建模在一个有向无环图中，从而将最长公共子序列问题转化为了在有向无环图中寻找最长路径的问题。这两种方法的区别在于，基于支配点的算法的思路是通过非支配排序的方法，在每一层中仅仅保留无法被其它节点支配的节点，然后在向后逐步扩展，直到所有的节点都没有后继节点。之后我们可以通过回溯的方式得到所有的最优解。该算法的最大缺点在于追着搜索的进行，同一层的节点数会呈指数级增长，也就意味着非支配排序的次数也会呈指数级增长，当面对大规模的序列比对问题时，算法往往难以在合理的时间内得到最终结果。而最近提出的基于无冗余的有向无环图算法则通过使用哈希表(Hashtable)这一数据结构，在构图的过程中避免了非支配排序的使用，节省了大量的构图时间，可是在构图后它需要两次拓扑排序得到最终的结果，并且对于大规模问题时需要给哈希表(Hashtable)开辟大量的储存空间。最关键的是，由于缺少合理的剪枝策略，该算法的搜索空间过大，对计算资源和存储资源的浪费比较严重。

发明内容

本发明的目的是提供一种基于分支定界的大规模最长公共子序列问题求解方法，解决了现有技术中存在的问题。

本发明所采用的技术方案是，

基于分支定界的大规模最长公共子序列问题求解方法，包括如下步骤：

步骤1，初始化有向无环图；具体包括如下步骤：

步骤1.1，构建初始节点O(0,0,…,0)和终节点E(∞,∞,…,∞)；初始节点和终节点中向量的维数等于需要比对的序列数；

步骤1.2，通过贪心策略找到一条尽可能长的路径，并将其长度作为下界LowerBound；

步骤1.3，寻找初始节点O(0,0,…,0)的所有后继节点p

步骤2，按照k的大小，由小到大依次处理每个Hashtable(k)；若Hashtable(k)≠φ，执行步骤3，否则执行步骤4；

步骤3，处理Hashtable(k)中所有节点，包括如下步骤：

步骤3.1，从Hashtable(k)中取出节点p，并估计p到终节点E(∞,∞,…,∞)的剩余路径长度Leftstep

步骤3.2，如果Level

步骤3.3，如果Level

步骤4，若Hashtable(k)＝φ，则删除Hashtable(k)，k＝k+1；

步骤5，若还有未处理的Hashtable(k)，则对未处理的Hashtable(k)执行步骤2；否则，输出有向无环图，执行步骤6；

步骤6，根据有向无环图，求解得到最长公共子序列问题的结果。

进一步的，所述步骤1.2中，所述的尽可能长的路径是指待求解的最长公共子序列问题的一个近似解。

进一步的，所述步骤1.2中，所述的判断p

若

若p

与现有技术相比，本发明的有益效果如下：

1、本发明在构建有向无环图的过程中不断更新节点的层数，从而在算法运行结束后可以直接得到节点的层数，无需正反两次拓扑排序。

2、本发明通过一种新的哈希表(Hashtable)构建策略，将节点存储在不同的哈希表(Hashtable)中，并在搜索的过程中及时删除之前创建的哈希表(Hashtable)从而减少了大量的计算机存储资源。

3、本发明给出了一种分支定界的策略，用于判断一个节点的路径是否能形成最优解，若可以形成最优解则继续搜索它的后继节点，否则不搜索它的后继节点，从而极大地减少了算法的搜索空间，从而节省了大量的计算和存储资源。

附图说明

图1是本发明的方法的流程图。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明。

本实施例的基于分支定界的大规模最长公共子序列问题求解方法，包括如下步骤：

步骤1，初始化有向无环图；具体包括如下步骤：

步骤1.1，构建初始节点O(0,0,…,0)和终节点E(∞,∞,…,∞)；初始节点和终节点中向量的维数等于需要比对的序列数；

步骤1.2，通过贪心策略找到一条尽可能长的路径，并将其长度作为下界LowerBound；所述的尽可能长的路径是指待求解的最长公共子序列问题的一个近似解；

步骤1.3，寻找初始节点O(0,0,…,0)的所有后继节点p

步骤2，按照k的大小，由小到大依次处理每个Hashtable(k)；若Hashtable(k)≠φ，执行步骤3，否则执行步骤4；

步骤3，处理Hashtable(k)中所有节点，包括如下步骤：

步骤3.1，从Hashtable(k)中取出节点p，并估计p到终节点E(∞,∞,…,∞)的剩余路径长度Leftstep

步骤3.2，如果Level

步骤3.3，如果Level

(i)若

(ii)若p

步骤4，若Hashtable(k)＝φ，则删除Hashtable(k)，k＝k+1；

步骤5，若还有未处理的Hashtable(k)，则对未处理的Hashtable(k)执行步骤2；否则，输出有向无环图，执行步骤6；

步骤6，根据有向无环图，求解得到最长公共子序列问题的结果。

为了说明本发明的方法的有效性，本发明给出如下实验：

本实验在配置为cpu:inter(R)Xeon(R)Gold 5115,内存:128G的一台云服务器上对真实DNA数据集(NCBI：www.ncbi.nlm.nih.gov)进行对比试验。对比算法为2016年CCF A类会议上提出的Top-MLCS算法(Y.Li,Y.Wang,Z.Zhang,Y.Wang,D.Ma,J.Huang,A novelfast and memory efficient parallel mlcs algorithm for long and large-scalesequences alignments,in:32nd IEEE