大规模多公共最长序列问题的快速有效路径消除算法

背景

在各个领域中，寻找多个(即三个或三个以上)序列的最长公共子序列(LCS)是一个经典但又难以解决的问题。这个问题的主要瓶颈是，目前最先进的算法需要构建一个巨大的图(称为直接无环图，或DAG)，计算机通常没有足够的空间来处理。现有算法由于耗费大量的时间和空间，无法适用于长序列和大规模序列的问题。

结果

为了有效地解决大规模MLCS问题，提出了一种小型有向无环图(mini- dag)模型和一种新的路径消除算法。在mini-DAG中，我们采用分支定界方法在DAG构建过程中减少路径，得到了一个非常小的DAG (mini-DAG)，节省了内存空间和搜索时间。

结论

在一组标准的基准DNA序列上进行了实证实验。实验结果表明，该模型在大规模MLCS问题上的性能优于现有算法。

在癌症治疗等各个领域[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 1" title="1" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e484">1]、癌症检测[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 2" title="2" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e487">2]、蛋白质序列分类[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 3" title="3." href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e490">3.]、基因数据检索[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 4" title="4" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e493">4]，基因数据分析[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 5" title="5" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e496">5]，搜索多个(即三个或三个以上)序列的最长公共子序列(LCS)是一个经典但难以解决的问题。随着序列数量的增加和生物技术的进步，这一问题通常分为两类。首先是找出两个序列之间的最长公共子序列，称为LCS问题;二是在三个或多个序列中找到最长公共子序列，称为MLCS问题。

在过去的几十年里，已经提出了许多致力于解决LCS问题的算法;例如，Sankoff [<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 6" title="6" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e502">6]发表了一篇论文，其中他描述了如何使用动态规划(DP)算法来确定两个序列的LCS。LCS问题可以在<年代p一个nclass="mathjax-tex">\ (O (n ^ 2) \)运行时间和内存空间，其中<我>n是在每种情况下要处理的序列的长度。一般来说，MLCS问题比LCS问题更难解决。许多针对LCS问题开发的算法不适用于MLCS挑战。［<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" title="7" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/#ref-CR7" id="ref-link-section-d152839629e541">7，<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" title="8" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/#ref-CR8" id="ref-link-section-d152839629e541_1">8，<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" title="9" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/#ref-CR9" id="ref-link-section-d152839629e541_2">9，<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" title="10" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/#ref-CR10" id="ref-link-section-d152839629e541_3">10，<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" title="11" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/#ref-CR11" id="ref-link-section-d152839629e541_4">11，<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 12" title="12" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e544">12]，特别是大规模MLCS问题(即具有大量和长序列的问题)。随着序列数量和长度的增加，由于序列的高时间和空间复杂性，所使用的运行时间和内存空间呈指数级增长<年代p一个nclass="mathjax-tex">\ (O (n ^ d) \)［<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 13" title="13" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e581">13),<我>d（<我>d\通用电气(\ \)2)为序列个数<我>n表示序列的长度。

同样，主要的基于点的方法，其核心概念最早是由博多和今井[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 14" title="14" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e614">14，<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 15" title="15" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e617">15]，是针对MLCS问题的一种比前人更有效和高效的算法，它构造了一个有向无环图，将寻找MLCS的问题转化为寻找DAG图上从源节点到结束节点的最长路径。这是基于dp型算法的动态表中绝大多数点都是不相关的，只需要计算和保存关键点，即所谓的优势点[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 13" title="13" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e620">13]。毫无疑问，占主导地位的基于点的方法比dp型方法的搜索范围要窄得多。结果还表明，采用这种方法可以显著降低性能和内存空间。随后，为了进一步提高其性能，提出了几种基于点的主要方法的版本[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" title="16" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/#ref-CR16" id="ref-link-section-d152839629e623">16，<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" title="17" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/#ref-CR17" id="ref-link-section-d152839629e623_1">17，<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" title="18" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/#ref-CR18" id="ref-link-section-d152839629e623_2">18，<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 19" title="19" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e626">19]。为了加快对匹配点后继点的搜索，Chen等人设计了一种特殊的数据结构，称为后继表。[qh]<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 17" title="17" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e630">17被称为Fast-LCS。此外，Wang等。[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 19" title="19" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e633">19]描述了一种被称为Quick-DP的新方法，该方法采用分而治之的策略来加速DAG的生成。在时间复杂度方面，Quick-DP优于Fast-LCS。但是，随着序列数量和长度的增加，Fast-LCS和Quick-DP产生的DAG的大小也会增加。事实证明，Fast-LCS和Quick-DP经常在DAG构建过程中陷入困境。这是因为两种算法的非支配排序方法的时间复杂度是<年代p一个nclass="mathjax-tex">\ (O (N ^ 2) \),在那里<我>N是DAG中赛点的数量，这大大超过<我>n和<我>d。

最近，wang等。[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 20" title="20." href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e681">20.引入了一种名为Top-MLCS的独特算法，该算法采用了一种新的DAG构建方法和一种向前和向后拓扑排序技术来确定DAG中的最长路径。由于采用了拓扑排序技术，该方法具有较低的时间消耗。然而，随着DAG大小的增长，拓扑排序算法会消耗大量的内存空间，因为它们必须存储整个DAG，包括所有的匹配点和路径(即不能及时识别和删除不必要的匹配点和非最优路径)。由于内存溢出，它们不能很好地解决大规模MLCS问题。Liu等。[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 21" title="21" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e684">21提出了一种字符合并算法(CMA)，该算法可以合并连续重复的字符，缩短序列，最大限度地降低待处理问题的复杂性，从而有效地解决了大规模MLCS问题。该方法对具有较多重复字符的MLCS具有较好的解算效果。2020年[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 22" title="22" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e687">22]，开发了一种新的用于大规模MLCS挑战的PRDAG模型。在PRDAG模型中没有重复的匹配点，每个匹配点被分配一个唯一的路径记录器(一个关键的前体指针)，以跟踪连接源点到自身的最长路径。除了最优算法外，还提出了一些优秀的启发式算法。算法MLCS-A*， [<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 27" title="27" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e690">27]的方法可以找到任意给定数量序列的LCS。MLCS-A*是a *算法的变体，a *算法是一种可证明的最优优先搜索算法[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 28" title="28" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e693">28]。但与在图中寻找代价最小路径的A*不同，MLCS-A*在多维矩阵中搜索与LCS对应的最长路径。2020年，一个新的随时a *搜索[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 26" title="26" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e697">26]，解决各种场景的实例问题;除了提供出色的解决方案外，随时A*搜索几乎可以在任何时候返回已证实的缺口，如果过早终止。然而，随着序列数量和长度的增加，这些策略仍然不能应对大规模MLCS问题的挑战。

在本文中，将创建迷你MLCS以确保在搜索MLCS问题时具有鲁棒性。该算法与现有算法的主要区别在于，mini-MLCS采用了一种基于下界和上界估计的新颖路径消除策略，可以有效地从DAG中去除大量不必要的匹配点和非最优路径，避免了使用非主导排序和拓扑排序，这两种算法都非常耗时且需要大量的内存空间。因此，创建的DAG的大小是适度的，并且mini-MLCS可以有效地识别从DAG到mlcs的最长路径，并且使用最小的运行时间和内存。我们的主要贡献如下:

1. 1

   设计一种新颖的分支定界策略，在构造DAG图时消除不必要的路径。在得到最终的MLCS之前，如果我们能判断当前计算的匹配点不是构成MLCS的点，那么通过该点的路径就不是最长的;这些被称为非点和非最优路径。因此，我们不需要将它们包含在DAG中。

2. 2

   设计一个较小的DAG (mini-DAG)，以防止典型DAG构建过程中的非主导和拓扑排序。所提出的分支定界策略可以在不比较匹配点的情况下消除匹配点。它大大节省了非支配排序和拓扑排序的时间。

3. 3.

   提出了一种快速、高效、时间和空间成本较低的处理大规模序列问题的算法(mini-MLCS)。我们设计了一种新的分支定界图策略MLCS算法，称为mini-MLCS，并将其与目前最先进的算法进行了比较。结果表明，该算法优于这些算法，适用于大规模MLCS问题。

LCS/MLCS问题的定义

定义1

令s =<年代p一个nclass="mathjax-tex">\ \ langle \ ()\ (c₁\)，<年代p一个nclass="mathjax-tex">\ (c₂\),……，<年代p一个nclass="mathjax-tex">\ (c_n \)\ \)范围内(\捕杀表示字符集上的一个序列<年代p一个nclass="mathjax-tex">σ\ (\ \),在那里<年代p一个nclass="mathjax-tex">\(为c_i \)\ (\ \)σ\ (\ \)， 1<年代p一个nclass="mathjax-tex">\ (\ \)我<年代p一个nclass="mathjax-tex">\ (\ \)n,<年代p一个nclass="mathjax-tex">\(\left| \Sigma \right|\)的基数<年代p一个nclass="mathjax-tex">σ\ (\ \),<年代p一个nclass="mathjax-tex">\(左| \ \ | \)表示s的长度，即<年代p一个nclass="mathjax-tex">\(左| \ \ | \)= n<年代p一个nclass="mathjax-tex">\ \ (^ *)＝<年代p一个nclass="mathjax-tex">\ \ langle \ ()\ (c_ {i_1} \)，<年代p一个nclass="mathjax-tex">\ (c_ {i_2} \),……，<年代p一个nclass="mathjax-tex">\ (c_ {i_m} \)\ \)范围内(\捕杀履行1<年代p一个nclass="mathjax-tex">\ (\ \)\ (i_1 \)<<年代p一个nclass="mathjax-tex">\ (i_2 \)< <…<年代p一个nclass="mathjax-tex">\ (i_m \)\ (\ \)n,<年代p一个nclass="mathjax-tex">\ (^ {*} \)表示为s的子序列，用<年代p一个nclass="mathjax-tex">\ (^ {*} \)\ (\ \)Sub (s)，其中Sub (s)是s的所有子序列的集合。

实际上，如果您从给定序列中消除零个或多个有序或无序字符<我>年代，生成的序列将比原始序列短<我>年代。这被称为原始序列的子序列<我>年代。

例如，如果<年代p一个nclass="mathjax-tex">\(s = \text {ACGTA}\)删除字符<我>G和<我>T从序列中<我>年代，结果序列<年代p一个nclass="mathjax-tex">\(s^* = \text {ACA}\)是序列的子序列吗<我>年代。

定义2

给定一个序列集<年代p一个nclass="mathjax-tex">\(Y = \left\{s_1,s_2，…, s_d \ \} \)，其中d是Y和d中包含的序列的个数<年代p一个nclass="mathjax-tex">\通用电气(\ \)2，<年代p一个nclass="mathjax-tex">\ (s_1 \)，<年代p一个nclass="mathjax-tex">\ (s_2 \),……，<年代p一个nclass="mathjax-tex">\ (s_d \)关于字符集<年代p一个nclass="mathjax-tex">σ\ (\ \)，如果有一个序列<年代p一个nclass="mathjax-tex">\ \ (^ *)，它是序列集合Y中任意序列的子序列，那么这个序列<年代p一个nclass="mathjax-tex">\ \ (^ *)称为序列y中所有序列的公共子序列，如果序列的长度是<年代p一个nclass="mathjax-tex">\ \ (^ *)是集合Y中最长的公共子序列，那么这个序列<年代p一个nclass="mathjax-tex">\ \ (^ *)是集合Y中所有序列的最长公共子序列。

例如,<年代p一个nclass="mathjax-tex">\(Y = \left\{s_1 = \textt {AACGTCGT}， s_2 = \textt {cacgtcc}， s_3 = \textt {GACCGTCT} \右\})，存在序列<年代p一个nclass="mathjax-tex">\(s^*_1 = \text {ACGTC}\)，<年代p一个nclass="mathjax-tex">\(s^*_2 = \text {AGC}\)、……<年代p一个nclass="mathjax-tex">\(s^*_m = \text {C}\)都属于的公共子序列<年代p一个nclass="mathjax-tex">\ (s_1 \)，<年代p一个nclass="mathjax-tex">\ (s_2 \)，<年代p一个nclass="mathjax-tex">\ (s_3 \)在集合中<我>Y,<年代p一个nclass="mathjax-tex">_1 \ \ (^ *)是所有公共子序列中最长的，那么这个序列呢<年代p一个nclass="mathjax-tex">_1 \ \ (^ *)它是集合中所有序列的最长公共子序列吗<我>Y。

通常，给定的LCS不止一个<我>d序列。如果<年代p一个nclass="mathjax-tex">\(d = 2\)，寻找LCS的问题通常称为LCS问题;否则,如果<年代p一个nclass="mathjax-tex">\(d \ ge3 \)，这个问题被称为MLCS问题。

定义3

给出一个序列s =<年代p一个nclass="mathjax-tex">\ \ langle \ ()\ (c₁\)，<年代p一个nclass="mathjax-tex">\ (c₂\),……，<年代p一个nclass="mathjax-tex">\ (c_n \)\ \)范围内(\捕杀，对于I = 0,1，…, n,定义<我>精准医疗（<我>年代［<我>我) =<年代p一个nclass="mathjax-tex">\ \ langle \ ()\ (c₁\)，<年代p一个nclass="mathjax-tex">\ (c₂\),……，<年代p一个nclass="mathjax-tex">\(为c_i \)\ \)范围内(\捕杀作为s和的第i个前缀<我>进而（<我>年代［<我>我) =<年代p一个nclass="mathjax-tex">\ \ langle \ ()\ (c_ {i + 1} \)，<年代p一个nclass="mathjax-tex">\ (c_{我+ 2}\)、……<年代p一个nclass="mathjax-tex">\ (c_n \)\ \)范围内(\捕杀作为s的第(i+1)个后缀(不包括第i个字符)。

例如，如果<年代p一个nclass="mathjax-tex">\(s = \text {AACGTCGT}\),然后<年代p一个nclass="mathjax-tex">\(pre(s[5]) = \text {AACGT}\)第5个前缀是<我>年代和<年代p一个nclass="mathjax-tex">\(suf(s[5]) = \text {CGT}\)第6个后缀是<我>年代,<我>精准医疗（<我>年代[0])为空序列，<我>进而（<我>年代[0])是一个完整序列。

动态规划方法

DP方法是解决LCS和MLCS问题的一种历史悠久的方法[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 23" title="23" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e2544">23]。鉴于<我>d长度序列<我>n，<年代p一个nclass="mathjax-tex">\ (s_1 \)，<年代p一个nclass="mathjax-tex">\ (s_2 \),……，<年代p一个nclass="mathjax-tex">\ (s_d \)，它会迭代地构造a<我>d-维度计分表<我>l哪有<年代p一个nclass="mathjax-tex">\ (n ^ d \)元素，其中元素<年代p一个nclass="mathjax-tex">\ (L [i_1, i_2,…i_d] \)表示前缀序列的MLCS的长度<年代p一个nclass="mathjax-tex">\ (pre (s_1 [i_1]) \)，<年代p一个nclass="mathjax-tex">\ (pre (s_2 [i_2]) \),……，<年代p一个nclass="mathjax-tex">\ (pre (s_d [i_d]) \)，可由下式[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 24" title="24" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e2872">24]：

在哪里<年代p一个nclass="mathjax-tex">\({\酒吧{L}} = \左\ {L \离开(i_ {1}, i_ {2}, \ cdots \离开(i_ {k} 1 \右),\ cdots i_ {d} \右]\中期k = 1, 2 \ cdots d正确\ \}\)。

在构造分数表之后<我>l， MLCS可以通过从右下的元素遍历来计算<我>l［<我>n，<我>n、……<我>n]到左上角元素<我>l[0,0，…], 0)。例如，图。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">1说明了分数表<我>l为序列构造<年代p一个nclass="mathjax-tex">\(s_1 = \text {AACGTCGT}\)和<年代p一个nclass="mathjax-tex">\(s_2 = \textt {CGACGTCC}\)，这两个序列的LCS是通过遍历<我>l[8,8] to<我>l(0,0)。

可以从图中观察到。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">1这是给定的<我>d序列，它们的长度是<我>n，该方法的时间和空间复杂度高达<年代p一个nclass="mathjax-tex">\ (O (n ^ d) \)［<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 9" title="9" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e3508">9]。作为<我>d和<我>n扩展，这些方法使用指数级更多的空间和时间。也就是说，DP方法的可扩展性受到限制，使得它不适合大规模MLCS问题。

主要的基于点的方法

在深入研究主要的基于点的方法的细节之前，我们将定义几个术语。

定义4

给定一个序列集<年代p一个nclass="mathjax-tex">\(Y = \left\{s_1,s_2，…, s_d \ \} \)，其中d是Y和d中包含的序列的个数<年代p一个nclass="mathjax-tex">\通用电气(\ \)2，<年代p一个nclass="mathjax-tex">\ (s_1 \)，<年代p一个nclass="mathjax-tex">\ (s_2 \),……，<年代p一个nclass="mathjax-tex">\ (s_d \)关于字符集<年代p一个nclass="mathjax-tex">σ\ (\ \),让<年代p一个nclass="mathjax-tex">\ (s_i [p_i] \)代表了<年代p一个nclass="mathjax-tex">\ (p_i \)-最左边序列中的第一个字符<年代p一个nclass="mathjax-tex">\ (s_i \)。如果<年代p一个nclass="mathjax-tex">\ (s_1 (p_1) \)＝<年代p一个nclass="mathjax-tex">\ (s_2 (p_2) \)=……＝<年代p一个nclass="mathjax-tex">\ (s_d [p_d] \)＝<年代p一个nclass="mathjax-tex">σ\ (\ \)，向量p = (<年代p一个nclass="mathjax-tex">\ (p_1 \)，<年代p一个nclass="mathjax-tex">\ (p_2 \),……，<年代p一个nclass="mathjax-tex">\ (p_d \))被称为这些d序列的匹配点。每个赛点p = (<年代p一个nclass="mathjax-tex">\ (p_1 \)，<年代p一个nclass="mathjax-tex">\ (p_2 \),……，<年代p一个nclass="mathjax-tex">\ (p_d \))与一个独特的符号联系在一起<年代p一个nclass="mathjax-tex">σ\ (\ \)。因此，我们经常使用p =<年代p一个nclass="mathjax-tex">σ\ (\ \)（<年代p一个nclass="mathjax-tex">\ (p_1 \)，<年代p一个nclass="mathjax-tex">\ (p_2 \),……，<年代p一个nclass="mathjax-tex">\ (p_d \))表示赛点，其中<年代p一个nclass="mathjax-tex">σ\ (\ \)是p的符号，用Ch(p) =<年代p一个nclass="mathjax-tex">σ\ (\ \)。

例如，如果两个序列<年代p一个nclass="mathjax-tex">\(s_1 = \text {AACGTCGT}\)和<年代p一个nclass="mathjax-tex">\(s_2 = \textt {CGACGTCC}\)是否提供了几个赛点的形式<年代p一个nclass="mathjax-tex">\(\sigma (i, j)\)。共性<年代p一个nclass="mathjax-tex">σ\ (\ \)\ (\ \)σ\ (\ \)，用虚线连接，对应于它的指标<我>我和<我>j在两个序列中，即<年代p一个nclass="mathjax-tex">\ \ (s_1 [i])＝<年代p一个nclass="mathjax-tex">\ (s_2 [j] \)＝<年代p一个nclass="mathjax-tex">σ\ (\ \)，例如<我>一个(1、3)<我>G(4,2).因为<年代p一个nclass="mathjax-tex">\(Ch(1,3) = A\)，赛点<我>一个(1,3)有时缩写为(1,3)。<我>G(4,2)可以表示为(4,2)。

定义5

给定符号集合T上d个序列的两个匹配点p和q，我们说:

1. 1

   P = q<年代p一个nclass="mathjax-tex">给所有\ \ (\)我(1<年代p一个nclass="mathjax-tex">\ (\ \)我<年代p一个nclass="mathjax-tex">\ (\ \)d),<年代p一个nclass="mathjax-tex">\ (p_{我}= q_{我}\)。

2. 2

   P弱支配q，如果<年代p一个nclass="mathjax-tex">给所有\ \ (\)我(1<年代p一个nclass="mathjax-tex">\ (\ \)我<年代p一个nclass="mathjax-tex">\ (\ \)d),<年代p一个nclass="mathjax-tex">\ (p_{我}\)\ (\ \)\ (q_{我}\)和<年代p一个nclass="mathjax-tex">\(\ \)存在我,<年代p一个nclass="mathjax-tex">\ (p_{我}\)<<年代p一个nclass="mathjax-tex">\ (q_{我}\)(用p表示<年代p一个nclass="mathjax-tex">\ \ preceq \ ()问)。

3. 3.

   P优于q或者q优于P，如果<年代p一个nclass="mathjax-tex">给所有\ \ (\)我(1<年代p一个nclass="mathjax-tex">\ (\ \)我<年代p一个nclass="mathjax-tex">\ (\ \)d),<年代p一个nclass="mathjax-tex">\ (p_{我}\)<<年代p一个nclass="mathjax-tex">\ (q_{我}\)(用p表示<年代p一个nclass="mathjax-tex">\ (\ prec \)问)。

4. 4

   如果p, Q被称为p的后继<年代p一个nclass="mathjax-tex">\ (\ prec \)更进一步，如果没有匹配点r来满足p<年代p一个nclass="mathjax-tex">\ (\ prec \)r<年代p一个nclass="mathjax-tex">\ (\ prec \)Q，那么Q被称为p的直接后继。

5. 5

   如果q是p的后继，我们称p为q的前导。

一般来说，一个赛点<我>p不超过<年代p一个nclass="mathjax-tex">\(σ| | \ \)继任者。

定义6

给定一个匹配集合P =<年代p一个nclass="mathjax-tex">\(\left\{P_1, P_2，…, P_m \ \} \)的赛点<年代p一个nclass="mathjax-tex">\ (P_ {j} \)\ (\ \)P，如果<年代p一个nclass="mathjax-tex">\ \ lnot \ ()\(\ \)存在\ (P_{我}\)\ \ preceq \ ()\ (P_ {j} \)， 1<年代p一个nclass="mathjax-tex">\ (\ \)我,我<年代p一个nclass="mathjax-tex">\ (\ \)米,我<年代p一个nclass="mathjax-tex">\ (\ \)j,<年代p一个nclass="mathjax-tex">\ (P_ {j} \)称为P上的非支配点(简称支配点)。P上的所有支配点构成P的支配集。

主要的基于点的方法是基于构造直接无环图(DAG)。他们的组织结构如下。首先，给定<我>d序列，图的源点定义为a<我>d维点<我>O(0, 0, 0)。这个点没有输入边，所以它的in度是0。源点的级别定义为级别0。然后，我们确定当前点的所有继承点<我>O并创建一个有向边缘连接它的每一个继任者。后继点的等级定义为等级1。非支配排序用于计算上所有支配点的集合<我>水平－1．然后，对于每一个非支配点<我>水平-1时，我们识别所有后继点，在上创建一条连接每个非主导点的边<我>水平给每一个继承人加1，把所有继承人的等级定为第二层。我们使用非支配排序来识别上的所有支配点<我>水平2。这个过程一直持续到没有形成额外的后继点，此时DAG构建完成。如果一个点没有后继点，则定义为结束点(<年代p一个nclass="mathjax-tex">\ \ infty \ ()，<年代p一个nclass="mathjax-tex">\ \ infty \ (),……，<年代p一个nclass="mathjax-tex">\ \ infty \ ())。DAG建立后，LCS/MLCS由从源点到终点最长路径上的点所表示的字符序列组成。因此，LCS/MLCS问题的主要问题是如何创建DAG。

例如，如图1所示。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">2，序列<年代p一个nclass="mathjax-tex">\(s_1 = \text {AACGTCGT}\)，<年代p一个nclass="mathjax-tex">\(s_2 = \textt {CGACGTCC}\)和<年代p一个nclass="mathjax-tex">\(s_3 = \textt {GACCGTCT}\)， MLCS是使用基于优势点的方法生成的。

1. 1

   初始化。

   设置源节点<我>O(0,0,0)和结束节点(<年代p一个nclass="mathjax-tex">\ \ infty \ ()，<年代p一个nclass="mathjax-tex">\ \ infty \ ()，<年代p一个nclass="mathjax-tex">\ \ infty \ ())。

2. 2

   第1层的DAG构造。

   为点<我>O(0,0,0) on<年代p一个nclass="mathjax-tex">\ (d0 \)找到所有的继承者;<我>一个(1,3,2)，<我>C(3,1,3)，<我>G(4,2,1)和<我>T(5,6,6)，并从点添加一条直边<我>O(0,0,0)到每一个。这些后继者都是0级后继者，都是1级点。把它们放进去<年代p一个nclass="mathjax-tex">\ (l1 \)的集合。支配点<我>T(5,6,6)在集合中<年代p一个nclass="mathjax-tex">\ (l1 \)使用非主导排序(注意<我>一个(1,3,2)<年代p一个nclass="mathjax-tex">\ (\ prec \)T(5,6,6)，<我>T(5,6,6)是支配点)。集<年代p一个nclass="mathjax-tex">\ (D_1 \)\ (= \)\(左\ \{(1、3、2),C(3、1,3),G (4 2 1) \ \} \),<我>k来<我>k\ \ (+)1.

3. 3.

   第2层的DAG构造。

   对于中的每个点<年代p一个nclass="mathjax-tex">\ (D_1 \)\ (= \)\(\left\{A(1,3,2)， C(3,1,3)， G(4,2,1) \右\}\)，找到它的所有继承者。<我>C(3,4,3)，<我>G(4,5,5)，和<我>T(5, 6, 6)都是点的后继者<我>一个(1,3,2)<年代p一个nclass="mathjax-tex">\ (\ \)\ (D_1 \)都包含在<年代p一个nclass="mathjax-tex">\ (l2 \)。创建一个直接边缘连接点<我>一个(1, 3, 2)给每一个继承者。为点<我>C(3,1,3)，<我>C(6,4,4)，<我>G(4,2,5)，和<我>T(5, 6, 6)都是它的继承者，都包含在<年代p一个nclass="mathjax-tex">\ (l2 \)。添加一条直边<我>C(3, 1, 3)给每个继承者。为点<我>G(4,2,1)，<我>C(6,4,3)，<我>G(7,5,5)，和<我>T(5, 6, 6)都是它的后继函数，并加上一条直接边<我>G(4, 3, 2)每个继承者，把这些继承者放入<年代p一个nclass="mathjax-tex">\ (l2 \)。排除多余的继任者<年代p一个nclass="mathjax-tex">\ (l2 \)。主导点<我>G(4,5,5)，<我>T(5,6,6)和<我>G(7, 5, 5)使用非支配排序删除<年代p一个nclass="mathjax-tex">\ (l2 \)。允许<年代p一个nclass="mathjax-tex">\ (D_2 \)＝<年代p一个nclass="mathjax-tex">\(左\ \ {C(3、4、3),C(6、4、4),G(4、2、5),C(6、4、3)\ \}\),<我>k来<我>k\ \ (+)1.

4. 4

   重复步骤3，直到集合中的所有点都不存在后继点<年代p一个nclass="mathjax-tex">\ (D_k \)。然后替换<年代p一个nclass="mathjax-tex">\((\ inty， \ inty， \ inty)\)对于点来说<年代p一个nclass="mathjax-tex">\ (D_k \)，完成DAG的构建。

如上所述，主要的基于点的技术有以下明显的缺点:

1. 1

   每个关卡可能包含许多重复的赛点和劣势点。(例如,<我>T(5,6,6)出现了三次<年代p一个nclass="mathjax-tex">\ (l2 \)还有三点<我>G(4,5,5)，<我>T(5,6,6)，<我>G(7,5,5)是控制点)，并且在一个关卡中出现的赛点可能在随后的关卡中出现多次(例如，<我>T(5,6,6)出现在<年代p一个nclass="mathjax-tex">\ (l1 \)-<年代p一个nclass="mathjax-tex">\ (L_4 \))，并且只在最后一个关卡中有用。因此，创建的DAG将非常大，以至于计算机将耗尽存储它的内存。

2. 2

   非主导排序方法将需要大量的工作来获得<年代p一个nclass="mathjax-tex">\ (D_k \)。它有一个<年代p一个nclass="mathjax-tex">\ (O (d {N_ {k}} ^ 2) \)级别的时间复杂度<我>k,在那里<年代p一个nclass="mathjax-tex">\ (N_k \)赛点数输入了吗<年代p一个nclass="mathjax-tex">\ (L_k \)和<我>d表示序列的数量。请注意,<年代p一个nclass="mathjax-tex">\ (N_k \)会非常巨大(在最坏的情况下，<年代p一个nclass="mathjax-tex">\(N_k = |\Sigma |^k\)随着水平呈指数增长<我>k增加)。因此,当<我>n，<我>d,<年代p一个nclass="mathjax-tex">\(\left| \Sigma \right|\)，即当MLCS问题成为一个大规模问题时，非主导排序方法变得非常耗时。

Fast-LCS [<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 17" title="17" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e6849">17]及Quick-DP [<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 19" title="19" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e6852">19]是这类算法的两个代表性算法。

mini-MLCS的主要框架

如前所述，现有办法由于需要大量时间和空间，无法解决大规模MLCS问题[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 22" title="22" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e6868">22]。这背后的根本原因是，作为数字<我>d和长度<我>n对于序列增长，非优势排序和拓扑排序将花费大量时间在匹配点之间的比较上。事实证明，计算时间和存储空间需求超过了最大限制。为了解决这些问题，提出的mini-MLCS在DAG构建过程中快速发现不必要的匹配点和非最优路径，然后及时消除它们，以限制DAG的大小。

为了准确地得到序列的最终MLCS, mini-MLCS首先设计了一种快速预测真MLCS的策略<我>R下界<我>较低的（<我>R)。然后，在决定是否包含赛点之前<我>p在DAG中，mini-MLCS计算上界<年代p一个nclass="mathjax-tex">\(Upper(p， \infty)\)从赛点开始的任意路径的长度<我>p到最后的赛点。假设之间的真实距离<我>p终点是<我>距离（<我>p)，即得到的上界<年代p一个nclass="mathjax-tex">上层(p, \ \ (infty) \)应该大于等于<我>距离（<我>p)。最后，判断从起点到终点的估计距离是否小于<我>较低的（<我>R(注意从起始点0到<我>p是当前级别的值吗<我>水平（<我>p)，当DAG计算为<我>p)。如果<年代p一个nclass="mathjax-tex">上层(O p \ \ (infty) \)＝<我>水平（<我>p) +<年代p一个nclass="mathjax-tex">上层(p, \ \ (infty) \)<<我>较低的（<我>R)，则没有路径通过<我>p是最长的路径。因此，<我>p是一个不必要的匹配点，并且所有经过它的路径在DAG中并不是最长的。基于这一发现，所有不必要的匹配点和非最优路径可以立即删除。

下界的估计<我>较低的（<我>R)在短时间内

我们并不知道MLCS的真正长度<我>R直到我们得到它，但我们可以得到一个最低限度<我>较低的（<我>R)，生成一个估计的MLCS。那么这个估计的MLCS的长度是一个下界<我>R估计的MLCS长度越长，越接近<我>R。我们的目标是尽可能快地找到一个估计的MLCS。一种计算下界的快速启发式策略<我>较低的（<我>R)是基于这些概念设计的。关键阶段如下所示。

对于一个<我>d维匹配点<我>p\ (= \)（<年代p一个nclass="mathjax-tex">\ (p_1 \)，<年代p一个nclass="mathjax-tex">\ (p_2 \),……，<年代p一个nclass="mathjax-tex">\ (p_d \))，<我>马克斯（<我>p)表示赛点中最大的数字<我>p，<我>最小值（<我>p)表示赛点中最小的数字<我>p,<年代p一个nclass="mathjax-tex">\(\varphi (p) = max(p) - min(p)\)的最大位置偏移<我>d赛点中的序列<我>p。在每个关卡的所有赛点中，我们选择第一个<我>t最小的<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())。因为可以从图中观察到。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">1，赛点越小越好<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())倾向于包含一个较大的主导区域，而不是较大的点<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())，而较大的主导区域可能包含更多的赛点，所以较小的<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())是否更有可能是构成最长公共子序列的赛点而不是较大的赛点<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())。例如，在图1中。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">1，<我>C(3,4)包含的主导区域多于<我>C(3,7)所以<我>C(3,4)更有可能形成最长公共子序列。基于这一思想，提出了两种策略来获得准确的下界。

策略1:赋一个小的初始值<我>t在DAG施工过程中意味着<我>t用最小的比赛点<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())在DAG的每个级别中选择值。的作用<我>t是减少搜索空间而得到一个合适的吗<我>较低的（<我>R)以更快的速度。这样我们就得到了一个首字母<我>较低的（<我>R)。接下来，添加一定的步长<年代p一个nclass="mathjax-tex">\μ(\ \)来<我>t每次都是这样<年代p一个nclass="mathjax-tex">\(t = t + \mu)，并继续构建DAG来计算<我>较低的（<我>R)。更新<我>较低的（<我>R)如果它改变了，如果没有改变<我>较低的（<我>R)超过<年代p一个nclass="mathjax-tex">\ \(τ\)(我们自己定义)的次数，那么它可以被认为是更准确的<我>较低的（<我>R)已获取。

下面是计算下界的一个例子。

假设<我>t是一个小的正整数(例如，<年代p一个nclass="mathjax-tex">\(t = 4\)),<我>D是一个集合<我>t随机选择第一个赛点<我>t的最低值<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())

1. 1

   初始化:设置<年代p一个nclass="mathjax-tex">\(o =(0,0，…，0)\)作为第一个选择的赛点，即，<年代p一个nclass="mathjax-tex">\(D = \left\{O \right\}\)，并设置<年代p一个nclass="mathjax-tex">\(Lower(R) = 0\)。

2. 2

   更新<我>较低的（<我>R):接电话<我>t先行者的后继者<我>t的最低值<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())所有的继承者<我>D(如果有的话<年代p一个nclass="mathjax-tex">β\ (\ \)继任者与<年代p一个nclass="mathjax-tex">β\ (\ \)\ (\ \)t，那么让<年代p一个nclass="mathjax-tex">\ (t = \)β\ (\ \))。更新<我>D通过删除其所有现有元素并插入所选择的匹配点，并让<年代p一个nclass="mathjax-tex">\(Lower(R) = Lower(R) + 1\)。

3. 3.

   返回<我>较低的（<我>R)如果<我>D是空的;否则，继续执行步骤2。

在无花果。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">3.，我们使用前面的示例来演示该方法。<年代p一个nclass="mathjax-tex">\(Lower(R) = 0\)起初，和<年代p一个nclass="mathjax-tex">\(d = 0 \)。<我>O有四个后继(1,3,2)，(3,1,3)，(4,2,1)，(5,6,6)因为<年代p一个nclass="mathjax-tex">\ (t = \)4、这些接班人都是选定的。因此，我们更新<我>D通过<年代p一个nclass="mathjax-tex">\ (D = \ \{(1、3、2),(3、1,3),(4、2、1),(5 6 6)\ \}\)并设置<年代p一个nclass="mathjax-tex">\(Lower(R)= Lower(R)+ 1\)。计算中每个匹配点的后继点<我>D，共有10位后继者(见图2)。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">2，为了尽快找到下界，不进行点滤波，即包括所有滤波后的点，包括后继点<我>C(6,7,7)的<我>T(5,6,6))，有四个后继(3,4,3)，(4,5,5)，(5,6,6)，(6,4,4)，前四个最小<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())选择的值(注意最小)<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())值匹配点是(3,4,3)，(4,5,5)，(5,6,6)和第二最小的<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())值匹配点有两个:(6,4,4)和(7,5,5)具有相同的值<年代p一个nclass="mathjax-tex">\ \ (\ varphi ())价值。在这个场景中，我们只需要从(6,4,4)和(7,5,5)(假设(6,4,4)被选中)中随机选择一个并更新<我>D通过<年代p一个nclass="mathjax-tex">\ (D = \)\(左\ \{(3、4、3),(4、5、5、)(5 6 6),(6、4、4)\ \}\)和更新<我>较低的（<我>R)<年代p一个nclass="mathjax-tex">\(Lower(R) = 2\)。同样,与<年代p一个nclass="mathjax-tex">\(Lower(R) = 3\)，<年代p一个nclass="mathjax-tex">\ (D = \)\(左\ \{(4、5、5),(5 6 6),(6、7、7),(6、7、4)\ \}\)。当<年代p一个nclass="mathjax-tex">\(Lower(R) = 4\)，适当的<年代p一个nclass="mathjax-tex">\ (D = \)\(\left\{(6,7,7)，(5,6,6) \右\}\)。最后，我们得到<年代p一个nclass="mathjax-tex">\(low (R) = 5\)适当的<年代p一个nclass="mathjax-tex">\ (D = \)\(\left\{(6,7,7) \right\}\)。

上界的估计<年代p一个nclass="mathjax-tex">上层(O p \ \ (infty) \)与效率

假设<我>p是DAG上的一个当前点，我们想知道所有路径的长度<我>O到最后的赛点<我>p。然而，这些路径的长度是未知的，直到它们被构建。但是如果我们能估计一个上界<年代p一个nclass="mathjax-tex">上层(O p \ \ (infty) \)这些路径的长度并知道它小于下界<我>较低的（<我>R)(例如,<年代p一个nclass="mathjax-tex">上层(O p \ \ (infty) \)<<我>较低的（<我>R))，那么我们可以得出这些路径经过<我>p不是最长的路径，可以从DAG中删除。这样，新的DAG将比以前的DAG小得多。

值得注意的是，DAG当前的赛点<我>p已经确定，最长路径的长度从<我>O来<我>p可能是确定的。事实上，它是DAG水平<我>p(用<我>水平（<我>p))。

另外，最长路径的真实长度<我>距离（<我>p)之间的当前赛点<我>p而最终的赛点通常是未知的。一种可能的方法是估计上界<年代p一个nclass="mathjax-tex">上层(O p \ \ (infty) \)。然后<年代p一个nclass="mathjax-tex">上层(O p \ \ (infty) =水平(p) +上(p \ infty) \)任意路径长度的上界是什么<我>p。下面，我们将设计一些快速估算的策略<年代p一个nclass="mathjax-tex">上层(p, \ \ (infty) \)让它尽可能接近真实的价值<年代p一个nclass="mathjax-tex">(p \ infty) \ \(距离)尽可能的小(也就是说，尽可能的小)。

鉴于<我>d序列<年代p一个nclass="mathjax-tex">\ (s_1 \)，<年代p一个nclass="mathjax-tex">\ (s_2 \),……，<年代p一个nclass="mathjax-tex">\ (s_d \)在字符集和匹配点上<年代p一个nclass="mathjax-tex">\ (p = \)（<年代p一个nclass="mathjax-tex">\ (p_1 \)，<年代p一个nclass="mathjax-tex">\ (p_2 \),……，<年代p一个nclass="mathjax-tex">\ (p_d \))，得到以下结论:

定理1

对于匹配点p = (<年代p一个nclass="mathjax-tex">\ (p_1 \)，<年代p一个nclass="mathjax-tex">\ (p_2 \),……，<年代p一个nclass="mathjax-tex">\ (p_d \))和结束匹配点，n为max(p)对应的序列长度。因此上(p,<年代p一个nclass="mathjax-tex">\ \ infty \ ()) = n - max(p)是匹配点之间任意最长路径长度的上界。<年代p一个nclass="mathjax-tex">\ (p_1 \)，<年代p一个nclass="mathjax-tex">\ (p_2 \),……，<年代p一个nclass="mathjax-tex">\ (p_d \))和结束赛点<年代p一个nclass="mathjax-tex">\ \ infty \ ()，和Upper(O,p，<年代p一个nclass="mathjax-tex">\ \ infty \ ()) = level(p) + n - max(p)是从0到0的最长路径长度的上界<年代p一个nclass="mathjax-tex">\ \ infty \ ()通过p。

证明

表示<年代p一个nclass="mathjax-tex">\(= n - max(p)\)。很明显,<我>距离（<我>p)等于序列的最长公共子序列<年代p一个nclass="mathjax-tex">\(suf(s_i[p_i])(1 \le I \le d)\)，<年代p一个nclass="mathjax-tex">距离(p) \le \xi\因为对于对应的序列<我>马克斯（<我>p)最多<年代p一个nclass="mathjax-tex">它后面的字符。因此<年代p一个nclass="mathjax-tex">\(Upper(p，\infty) = n - max(p)\),即<年代p一个nclass="mathjax-tex">\(Upper(O,p，\infty) = level(p) + n - max(p)\)。

在定理1的基础上可以得到一些扩展。选择第一个<年代p一个nclass="mathjax-tex">\三角洲(\ \)马克斯（<我>p赛点)<我>p，然后计算序列的LCS<年代p一个nclass="mathjax-tex">\({suf(s_i[max_i(p)])\ (}1 \le I \le \delta)\)。把它作为的上界<我>p。得到的上界无疑更接近<我>距离（<我>p)比定理1得到的上界要大，但计算每个匹配点所需的时间更长。

让我们分析一下图中提到的例子。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">2进一步深入地演示识别不必要的赛点的策略。MLCS的估计下限是已知的，即<年代p一个nclass="mathjax-tex">\(low (R) = 5\)，如图所示。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">3.。根据定理1，<年代p一个nclass="mathjax-tex">上层(p, \ \ (infty) \)可以估计，和<我>水平（<我>p)可以在DAG施工过程中实现，如图1所示。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">4一个。

赛点<我>C(3, 1, 3<我>水平（<我>C)定义为1。<我>C(3,1,3)之后是三个后续:<我>C(6,4,4)，<我>G(4,2,5)和<我>T(5,6,6).集合<我>水平（<我>p)，每个后继者等于2，即<年代p一个nclass="mathjax-tex">\(水平(C(6、4、4))=水平(G(4、2、5))=水平(T (5 6 6)) = 2 \)，因为从起始匹配点到每个后继点的最长路径长度为1，并且<年代p一个nclass="mathjax-tex">\(low (R) = 5\)，如图所示。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">3.。根据定理1，<年代p一个nclass="mathjax-tex">\(上层(C(6、4、4),\ infty) = 8 - max (C(6、4、4))= 2 \)，<年代p一个nclass="mathjax-tex">\(上层(C(4、2、5)\ infty) = 8 - max (C(4、2、5))= 3 \)和<年代p一个nclass="mathjax-tex">\(上层(C (5 6 6), \ infty) = 8 - max (C (5 6 6)) = 2 \)。如图所示。<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">4A、赛点<我>C(6,4,4)和<我>T(5、6、6)因为相遇而被明确认定为不必要的赛点

上层(O p \ \ (infty) =水平(p) +上(p \ infty) \)<<我>较低的（<我>R）

没有任何路径(分支)连接<我>O它们将被纳入DAG。

除了上面介绍的求上界的方法外，文献[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 26" title="26" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e11098">26]及[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 27" title="27" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e11101">27提到了两种更紧凑的求上界的策略。他们在预处理阶段构建向量，然后在DAG构建阶段使用它们来寻找每个匹配点的上界。具体细节在策略2和策略3中展开。

策略2:让<年代p一个nclass="mathjax-tex">\ ({num_ {s_{我}}^ c} \)表示字符的编号<我>c按顺序<年代p一个nclass="mathjax-tex">\({s_i\ (}1 \le I \le d)\)。对于每个赛点之间的最长路径<我>p= (<年代p一个nclass="mathjax-tex">\ (p_1 \)，<年代p一个nclass="mathjax-tex">\ (p_2 \),……，<年代p一个nclass="mathjax-tex">\ (p_d \))和结束赛点。对于任何情况，都可以得出以下结论<我>c在<年代p一个nclass="mathjax-tex">σ\ (\ \)，数目<我>c在序列上的路径从<我>p到结束节点不会超过<年代p一个nclass="mathjax-tex">\(左分钟\ \ {num_{进而(s_1) (p_1)} ^ c, num_{进而(s_2 [p_2])} ^ c,…,num_{进而(s_d [p_d])} ^ c正确\ \}\)。

因此,

数字<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">4B展示了策略2的应用。赛点<我>一个(1, 3, 2)在<我>水平2,即<我>C(3,4,3)，<我>G(4,5,5)和<我>T(5,6,6)<我>G(4,5,5)，<年代p一个nclass="mathjax-tex">\(suf(s_1[4]) = \text {TCGT}\)，<年代p一个nclass="mathjax-tex">\(suf(s_2[5]) = \textt {TCC}\)和<年代p一个nclass="mathjax-tex">\(suf(s_3[5]) = \textt {TCT}\)。<年代p一个nclass="mathjax-tex">\(上层(G(4、5、5),\ infty) = \ \和限制_{σc \ \} \敏\左\ {num_{进而(s_1) (p_1)} ^ c, num_{进而(s_2 [p_2])} ^ c, num_{进而(s_3 [p_3])} ^ c正确\ \}= 1 + 1 + 0 + 0 = 2 \)，因为<年代p一个nclass="mathjax-tex">\ (\ texttt C {} \)和<年代p一个nclass="mathjax-tex">\ (\ texttt {T} \)的最小出现次数<年代p一个nclass="mathjax-tex">\ \(进而(s_1 [4]))，<年代p一个nclass="mathjax-tex">\ \(进而(s_2 [5]))和<年代p一个nclass="mathjax-tex">\ \(进而(s_3 [5]))是一次,<年代p一个nclass="mathjax-tex">\ (\ texttt {} \)和<年代p一个nclass="mathjax-tex">\ (\ texttt {G} \)中至少出现0次<年代p一个nclass="mathjax-tex">\ \(进而(s_1 [4]))，<年代p一个nclass="mathjax-tex">\ \(进而(s_2 [5]))和<年代p一个nclass="mathjax-tex">\ \(进而(s_3 [5]))。<年代p一个nclass="mathjax-tex">\(上层(O, G(4、5、5),\ infty) =水平(G(4、5、5))+上(G(4、5、5)\ infty) = 2 + 2 \)<<我>较低的（<我>R)，赛点<我>G(4,5,5)被识别为不必要的点，没有任何路径(分支)连接<我>O和<我>G(4,5,5)将被纳入DAG。

策略3:对于每个赛点之间的最长路径<我>p= (<年代p一个nclass="mathjax-tex">\ (p_1 \)，<年代p一个nclass="mathjax-tex">\ (p_2 \),……，<年代p一个nclass="mathjax-tex">\ (p_d \))、结束匹配点和一个向量<年代p一个nclass="mathjax-tex">\ (m_{我}\),在那里<年代p一个nclass="mathjax-tex">\ (m_{我}[p_ {}, p_ {i + 1}] \)与<年代p一个nclass="mathjax-tex">\(p_{i} = 1，…、| s_{我}| \)和<年代p一个nclass="mathjax-tex">\(p_{i+1} = 1，…、| s_ {i + 1} | \)，存储字符串LCS的长度<年代p一个nclass="mathjax-tex">\(进而(s_i [p_{我}))\)和<年代p一个nclass="mathjax-tex">\(进而(s_ {i + 1} [p_ {i + 1})) \)。

因此,

数字<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="figure anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">4C表示策略3的应用。对于赛点<我>G(4,2,1)上<我>水平1,<年代p一个nclass="mathjax-tex">\(suf(s_1[4]) = \text {TCGT}\)，<年代p一个nclass="mathjax-tex">\(suf(s_2[2]) = \text {ACGTCC}\)和<年代p一个nclass="mathjax-tex">\(suf(s_3[1]) = \textt {ACCGTCT}\)。结果是<年代p一个nclass="mathjax-tex">\(上层(G(4、2、1),\ infty) \)\(= min(3,5) = 3\)的LCS最小值<年代p一个nclass="mathjax-tex">\ \(进而(s_1 [4]))和<年代p一个nclass="mathjax-tex">\ \(进而(s_2 [2]))和LCS<年代p一个nclass="mathjax-tex">\ \(进而(s_2 [2]))和<年代p一个nclass="mathjax-tex">\ \(进而(s_3 [1])),即<年代p一个nclass="mathjax-tex">\(上层(O, G(4、2、1),\ infty) =水平(G(4、2、1))+上(G(4、2、1),\ infty) = 3 + 1 = 4 <低(R) \)，赛点<我>G(4,2,1)被识别为不必要的点，没有任何路径(分支)连接<我>O和<我>G(4,2,1)将被纳入DAG。

对于策略2和策略3，当规模为<我>n和<我>d特别大，则需要很长时间进行预处理。因此，为了减少预处理时间，我们不需要将所有序列都应用到预处理中，而是进行选择<年代p一个nclass="mathjax-tex">\三角洲(\ \)序列越不同越好。这样可以在较短的时间内得到预处理结果。

幸运的是，Wang等。[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 25" title="25" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e13979">25定义一个度量来比较两个序列。这个度量被称为多样性度量。

让<年代p一个nclass="mathjax-tex">\ ({num_ {s_{我}}^ c} \)表示字符的编号<我>c按顺序<年代p一个nclass="mathjax-tex">\ (s_i \)。的值越大<年代p一个nclass="mathjax-tex">\(左\ | {num_ {s_{我}}^ c} - {num_ {s_ {j}} ^ c} \右| \)，就越多样化<年代p一个nclass="mathjax-tex">\ (s_i \)和<年代p一个nclass="mathjax-tex">\ (s_j \)，这两个序列之间的差异越大。通过考虑这一因素，之间的差异<年代p一个nclass="mathjax-tex">\ (s_i \)和<年代p一个nclass="mathjax-tex">\ (s_j \)定义为:

这里有几个例子可以说明上述问题。

我们可以使用序列选择多样性更大的第二个序列<年代p一个nclass="mathjax-tex">\ (s_1 \)基于多样性测量。

\(s_1 = \text {AACGTCGT}\)。

\(s_2 = \textt {CGACGTCC}\)。

\(s_3 = \textt {GACCGTCT}\)，我们选择<年代p一个nclass="mathjax-tex">\ (s_1 \)＝<年代p一个nclass="mathjax-tex">\ (s_i \)，然后我们计算每个字符在这些序列中出现的次数。

\({num_{s_{1}}^A} = 2\)，<年代p一个nclass="mathjax-tex">\({num_{s_{1}}^C} = 2\)，<年代p一个nclass="mathjax-tex">\({num_{s_{1}}^G} = 2\)，<年代p一个nclass="mathjax-tex">\({num_{s_{1}}^T} = 2\)

\({num_{s_{2}}^A} = 1\)，<年代p一个nclass="mathjax-tex">\({num_{s_{2}}^C} = 4\)，<年代p一个nclass="mathjax-tex">\({num_{s_{2}}^G} = 2\)，<年代p一个nclass="mathjax-tex">\({num_{s_{2}}^T} = 1\)

\({num_{s_{3}}^A} = 1\)，<年代p一个nclass="mathjax-tex">\({num_{s_{3}}^C} = 3\)，<年代p一个nclass="mathjax-tex">\({num_{s_{3}}^G} = 2\)，<年代p一个nclass="mathjax-tex">\({num_{s_{3}}^T} = 2\)

\(多样性\离开(s_{1},{年代}_{2}\右)= \压裂{2}{8}| 2 - 1 | + \压裂{2}{8}| 2 - 4 | + \压裂{2}{8}| 2 - 2 | + \压裂{2}{8}| 2 - 1 | = \压裂{3}{4}\)

\(多样性\离开(s_{1},{年代}_{2}\右)= \压裂{2}{8}| 2 - 1 | + \压裂{2}{8}| 2 - 3 | + \压裂{2}{8}| 2 - 2 | + \压裂{2}{8}| 2 - 2 | = \压裂{1}{2}\)

因此，我们得出结论<年代p一个nclass="mathjax-tex">\ (s_1 \)和<年代p一个nclass="mathjax-tex">\ (s_2 \)是否有更多的不同<年代p一个nclass="mathjax-tex">\ (s_1 \)和<年代p一个nclass="mathjax-tex">\ (s_3 \)。

因此，当序列的规模较大时，我们选择<年代p一个nclass="mathjax-tex">\(s_1 = s_i\)然后捡起来<年代p一个nclass="mathjax-tex">\三角洲(\ \)\(\ δ \ll d)\)大多数不同(包含<年代p一个nclass="mathjax-tex">\ (s_1 \)序列)从给定的序列<我>d这样，我们大大减少了策略2和策略3的预处理时间。

构建mini-DAG

基于上述分支消去方法，我们逐级构建了mini-DAG。首先，零级<年代p一个nclass="mathjax-tex">\ (d0 \)仅由开始赛点组成<我>O，然后从一级到一级<我>R，代表为<年代p一个nclass="mathjax-tex">\ (D_1 \)，<年代p一个nclass="mathjax-tex">\ (D_2 \),……，<年代p一个nclass="mathjax-tex">\ (D_R \)，分别连续创建，其中<我>R为最终MLCS的长度。为了最小化时间和空间，我们每次只创建和存储一个关卡。

后<年代p一个nclass="mathjax-tex">\ (D_k \)构造(当前，<年代p一个nclass="mathjax-tex">\ (d0 \)是构造的)，下列程序可以采取构造吗<年代p一个nclass="mathjax-tex">\ (D_ {k + 1} \)：

1. 1

   选择每个赛点<年代p一个nclass="mathjax-tex">\(p \in D_k\)，搜索其继承集<我>年代ucc（<我>p)。

2. 2

   对于每个继承者<年代p一个nclass="mathjax-tex">\(q \in succ(p)\)，设置级别<我>问(即，从的当前最长路径的长度<我>O来<我>问),<年代p一个nclass="mathjax-tex">\(level(q) = k + 1\)。

3. 3.

   确定是否<我>问根据定理1、策略2和策略3，是一个无用的赛点。如果有，不要放<我>问在DAG中，执行步骤5。否则,将<我>问成<年代p一个nclass="mathjax-tex">\ (D_ {k + 1} \)。

4. 4

   添加一条有向边<我>p来<我>问在DAG。

5. 5

   如果后继者的所有赛点都在<年代p一个nclass="mathjax-tex">\ (D_k \)已检查完毕，施工情况如何<年代p一个nclass="mathjax-tex">\ (D_ {k + 1} \)完成为止。否则请转步骤1。

Mini-MLCS算法

为了更详细地描述新算法，在算法1中给出了mini-MLCS算法的伪代码。

一开始，估计的下界<我>较低的（<我>R)是计算出来的。该算法的关键步骤是第3行<年代p一个nclass="mathjax-tex">\ \ (sim \)第21行，解释了如何逐级构建迷你dag。<我>Ch（<我>问)表示匹配点所表示的字符<我>问，如定义4所述，以及<我>问。<我>前的表示从开始匹配点开始的最长公共子序列<我>O到当前点<我>问。最后，从mini-DAG中，可以获得MLCSs对应的最长路径，所有MLCSs将在第22行中返回<年代p一个nclass="mathjax-tex">\ \ (sim \)线23。

Mini-MLCS时间复杂度

为了展示算法1与其他算法相比的效率，这里给出了提出的算法1和比较算法的时间复杂度。首先，序列的长度表示为<我>n,<我>d表示序列的数量。在初始化过程中，我们构建了Fast-LCS提出的后继节点表(Successor Table)，以便快速发现点的后继节点<年代p一个nclass="mathjax-tex">\(O(d |\Sigma | n)\)［<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 17" title="17" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e16266">17]。其次，我们估计找到后续节点并将它们添加到向量哈希表的时间成本。使用<我>N表示mini-DAG中所有点的集合，时间复杂度为<我>O(|<我>N|)。最后，在mini-DAG中，我们使用<我>E表示整个边集合，时间复杂度为<我>O(|<我>E|)。对于策略1，构建一次DAG并找到其下界的时间复杂度为<年代p一个nclass="mathjax-tex">| \ \ (O (dσ| |多层陶瓷| t) \)。然后计算上界的时间复杂度。在定理1中，求上界的时间复杂度为<我>O（<我>d)。在预处理阶段(在mini-DAG构建之前)，我们选择<年代p一个nclass="mathjax-tex">\三角洲(\ \)序列从<我>d按式(4)排序，并将其应用于策略2和策略3。采用适当的数据结构将预处理结果存储起来，可以计算出<年代p一个nclass="mathjax-tex">上层(p, \ \ (infty) \)策略2在任何赛点的时间复杂度为<年代p一个nclass="mathjax-tex">\(O(\delta |\Sigma |)\)对于每个赛点。预处理阶段的策略3<年代p一个nclass="mathjax-tex">O(\ \(δn ^ {2}) \)。因此，考虑到最坏情况，mini-MLCS的时间复杂度为<年代p一个nclass="mathjax-tex">\(O(d |\Sigma | n)\)+<年代p一个nclass="mathjax-tex">| \ \ (O (dσ| |多层陶瓷| t) \)+<年代p一个nclass="mathjax-tex">O(\ \(δn ^ {2}) \)+<我>O(|<我>E|) +<我>O(|<我>N|)。自<年代p一个nclass="mathjax-tex">\(O(d |\Sigma | n) \ll O(\ δ n^{2})\)，<年代p一个nclass="mathjax-tex">\(O(d|\Sigma ||MLCS|t) \ll O(\ δ n^{2})\)，<我>O(|<我>N|) =<我>O(|<我>E|)和<年代p一个nclass="mathjax-tex">O(\ \(δn ^ {2}) \)<<我>O(|<我>N|)，我们提出的算法1的时间复杂度为<我>O(|<我>N|)。

对于比较的算法，Quick-DP采用<年代p一个nclass="mathjax-tex">\ (O \离开(d) (\ log n ^ {d2的}\左| N_ {Q} \右| \)\)［<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 19" title="19" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e16897">19),<年代p一个nclass="mathjax-tex">\ (N_ {Q} \)为Quick-DP构建的DAG中点的集合，Top-MLCS的时间复杂度为<年代p一个nclass="mathjax-tex">\ (O (| N_ {T} |) \)［<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 20" title="20." href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e16962">20.),<年代p一个nclass="mathjax-tex">\ (N_ {T} \)为Top-MLCS构建的ICSG中点的集合。需要注意的是，由于缺乏合理的缩小搜索空间的方案，Top-MLCS构建的DAG比Quick-DP和mini-MLCS构建的DAG大得多，其中Quick-DP构建的DAG比mini-MLCS构建的DAG大，即<年代p一个nclass="mathjax-tex">\ (| N_ {T} | \)\ \ gg \ ()\ (| N_ {Q} | \)> |<我>N|。但是Quick-DP使用耗时的非支配排序方法来减少搜索空间，因此<年代p一个nclass="mathjax-tex">\ (O \离开(d) (\ log n ^ {d2的}\左| N_ {Q} \右| \)\)><年代p一个nclass="mathjax-tex">\ (O (| N_ {T} |) \)。因此,<年代p一个nclass="mathjax-tex">\ (O \离开(d) (\ log n ^ {d2的}\左| N_ {Q} \右| \)\)><年代p一个nclass="mathjax-tex">\ (O (| N_ {T} |) \)\ \ gg \ ()O(|<我>N|)。

Mini-MLCS空间复杂度

接下来，我们计算算法1的空间复杂度。后继表占用的空间为<年代p一个nclass="mathjax-tex">\(O(d |\Sigma | n)\)；对于策略2，空间复杂度为<年代p一个nclass="mathjax-tex">\(O(\delta |\Sigma | n)\)时，策略3的空间复杂度最大<年代p一个nclass="mathjax-tex">\ (Oδn ^ 2) (\ \)，但存储点所花费的空间是<我>O（<我>d|<我>N|)。存储边占据了空间<我>O(|<我>E|)区域。自<年代p一个nclass="mathjax-tex">\(O(d|\Sigma |n) \ll O(d| n |) + O(|E|)\)，<年代p一个nclass="mathjax-tex">\(O(\delta |\Sigma | n) \ll O(d| n |) + O(|E|)\)，<年代p一个nclass="mathjax-tex">\(O(d|N|) = O(|E|)\)和<年代p一个nclass="mathjax-tex">\(O(\ n²)\ ll O(d| n |) + O(|E|)\)，算法1的空间复杂度为<我>O（<我>d|<我>N|)。Quick-DP和Top-MLCS的空间复杂度可以表示为<年代p一个nclass="mathjax-tex">\ (O (d | N_ {Q} |) \)［<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 19" title="19" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e17799">19),<年代p一个nclass="mathjax-tex">\ (O (d | N_ {T} |) \)［<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 20" title="20." href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e17845">20.),分别。为<年代p一个nclass="mathjax-tex">\ (| N_ {T} | \)><年代p一个nclass="mathjax-tex">\ (| N_ {Q} | \)> |<我>N，我们可以推断出我们的mini-MLCS算法由于使用了分支定界策略，比两个比较的算法具有更低的空间复杂度。

实验设置和比较算法

为了说明mini-MLCS在大规模MLCS问题上的性能，我们将其与四种最先进的算法Fast-LCS进行了比较实验[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 17" title="17" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e17938">17]、Quick-DP [<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 19" title="19" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e17941">19]， Top-MLCS [<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 20" title="20." href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e17944">20.]和A* search [<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 26" title="26" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e17947">26]。所有实验均在一台配备4个Intel(R) Xeon(R) E5-2640 2.40 GHz十核cpu、160 GB RAM、4个NVidia Tesla K40显卡和1.1TB磁盘空间的服务器上进行。操作系统为Ubuntu 16.04。所有算法都是在Eclipse中编写的，并使用C和c++代码进行编译。来自NCBI的生物序列<一个href="http://www.ncbi.nlm.nih.gov/nuccore/110645304?report%20=%20fasta">http://www.ncbi.nlm.nih.gov/nuccore/110645304?report = fasta作为测试集。这是铜绿假单胞菌PAO1的完整基因组序列，实验数据将从该基因组中随机选取。相关文献[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 26" title="26" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e17958">26]为LCS问题提供了一个公共基准集。基准基准[<一个d一个t一个-tr一个ck＝"click" data-track-action="reference anchor" data-track-label="link" data-test="citation-ref" aria-label="Reference 26" title="26" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5" id="ref-link-section-d152839629e17961">26]由450个问题实例组成，按输入字符串数量的不同值分组(<我>d)，输入字符串的最大长度(<我>n)，以及字母大小(<年代p一个nclass="mathjax-tex">\(σ| | \ \))。对于的每个组合<我>d，<我>n,<年代p一个nclass="mathjax-tex">\(σ| | \ \)该集合提供了十个随机均匀生成的实例。我们进行了以下四类实验。这些结果总结在表格中<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">1，<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">2，<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">3.和<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">4。

对于第一类实验，我们将序列长度固定为120，并在9个样本上进行试验，序列计数从10,000到50,000不等。对于第二种实验，我们将序列数量限制在20,000，并在16种情况下进行实验，序列长度从90到120不等。第三类实验，我们从BL集合中提取序列长度为100的实例，得到平均结果如表所示<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">3.。对于最后一类实验，为了证明估计方法的稳健性，我们对<我>t在<我>较低的（<我>R)的值<我>t通过实验。

表中第1列<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">1和<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">3.为DNA序列总数;表中的第1列<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">2和<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">4为DNA序列的总长度;表中第2列<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">1，<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">2和<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">4总长度<我>RMLCS在测试序列中的分布。在表中<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">1，<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">2和<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">4，第3至6列分别提供mini-MLCS、Top-MLCS、Quick-DP和Fast-MLCS的平均运行时间/内存(GB)。黑体数字表示数据集的最低运行时间，“+”表示运行时间超过5000s时未得到结果。对于表<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">3.， '−'表示运行内存超过32GB，无法获取结果。

实验结果及分析

如表所示<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">1在美国，由于运行时间过长，Fast-LCS算法一直无法处理长度为1万至5万的DNA序列。同时，Quick-DP算法同样无法处理长度在10,000到25,000之间的DNA序列。结果表明，任务难度不随序列数的增加而增加。这是因为，对于固定长度的序列，增加序列数量会增加搜索所有MLCS的成本，但是一旦序列数量达到一定水平，MLCS的数量和长度都会下降。从而降低了搜索MLCS的成本。这两种算法花费如此长时间的主要原因是它们需要太多时间进行非主导排序(注意，随着序列数量的增加，非主导排序需要大量的时间和空间)，而Top-MLCS和mini-MLCS不需要非主导排序，因此花费的时间要少得多。

如表所示<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">2随着DNA序列长度的增加，Fast-LCS和Quick-DP的耗时显著增加。然而，Top-MLCS和mini-MLCS的时间消耗增长要慢得多。此外，当序列长度小于95时，Quick-DP比Top-MLCS和mini-MLCS运行速度更快。在这种情况下，Quick-DP优于Top-MLCS和mini-MLCS，因为非主导排序所需的时间短。

表格<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">3.列出平均解长度<年代p一个nclass="mathjax-tex">R \({\眉题{}}\)，平均次数<年代p一个nclass="mathjax-tex">\({\眉题{t}} \)在达到已证明的最优性之前的几秒钟内，以及可以求解到最优性的实例数量<年代p一个nclass="mathjax-tex">\ (\ \)选择(每行10个选项)三种方法。可以看出，在处理小实例集时，mini-MLCS比Top-MLCS和A*更高效，因为它过滤了大部分的匹配点，不会造成内存溢出。然而，没有一个实例<年代p一个nclass="mathjax-tex">\(σ| | \ \)= 4和<我>d\通用电气(\ \)由于内存限制，A*和Top-MLCS可以求解到最优。如表所示<一个d一个t一个-tr一个ck＝"click" data-track-label="link" data-track-action="table anchor" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/s12859-022-04906-5">4，有一个参数<我>t在提出的算法中计算下界<我>较低的（<我>R)的MLCS长度。为了评估估计方法的稳健性，我们考察了<我>较低的（<我>R)通过改变的值<我>t在整个实验中。预测的下限越精确<我>较低的（<我>R)，可以找到更多不必要的匹配点并从DAG中删除。问题的实验包括2万个长度在90到120之间的序列。从实验结果可以看出，对于每一个长度恒定的测试问题<我>较低的（<我>R)的值变化对其影响很小<我>t。这表明的效果<我>t在<我>较低的（<我>R)是可以忽略不计的<我>较低的（<我>R)估计方法是稳健的。

本文提出了一种独特的分支消除策略(mini-MLCS)，通过识别无用的匹配点来有效地解决大规模MLCS问题。在构建DAG的过程中，快速识别不必要的匹配点，减少了对前一个DAG的每个级别进行非支配排序所花费的时间。实验结果表明，该算法优于当前最先进的Fast-LCS、Quick-DP和Top-MLCS算法，能够解决大规模MLCS问题。该方法比Fast-LCS、Quick-DP和Top-MLCS占用的时间和空间要少得多，特别是对于大规模MLCS问题。

这个程序代码可以在<一个href="https://github.com/BioLab310/mini_MLCS.">https://github.com/BioLab310/mini_MLCS。NCBI (<一个href="http://www.ncbi.nlm.nih.gov/nuccore/110645304?report%20=fasta">http://www.ncbi.nlm.nih.gov/nuccore/110645304?report = fasta)作为测试集。

不适用。

国家自然科学基金项目(61772124)资助。

作者及单位

1. 东北大学计算机科学与工程学院，辽宁沈阳

   于长勇，林鹏喜，赵玉海，任天美

2. 北京理工大学计算机科学与技术学院，中国北京

   Guoren王

贡献

CY实现了算法，进行了实验，分析了数据，并撰写了论文。PL和YZ设计实验和算法，分析数据，审稿。TR和GW对数据进行了分析，并审阅了论文的草稿。所有作者已阅读并批准稿件发表。

相应的作者

对应到<一个我d＝"corresp-c1" href="//www.mivven.com/bmcbioinformatics/articles/10.1186/mailto:zhaoyuhai@mail.neu.edu.cn">宵夜赵。

相互竞争的利益

作者宣称他们没有竞争利益。

伦理批准并同意参与

不适用。

发表同意书

不适用。

出版商的注意

伟德体育在线施普林格·自然对已出版的地图和机构关系中的管辖权要求保持中立。

开放获取本文遵循知识共享署名4.0国际许可协议，该协议允许以任何媒介或格式使用、共享、改编、分发和复制，只要您适当地注明原作者和来源，提供知识共享许可协议的链接，并注明是否进行了更改。本文中的图像或其他第三方材料包含在文章的知识共享许可协议中，除非在材料的署名中另有说明。如果材料未包含在文章的知识共享许可中，并且您的预期用途不被法律法规允许或超过允许的用途，您将需要直接获得版权所有者的许可。如欲查阅本许可证副本，请浏览<一个href="http://creativecommons.org/licenses/by/4.0/" rel="license">http://creativecommons.org/licenses/by/4.0/。创作共用公共领域免责声明(<一个href="http://creativecommons.org/publicdomain/zero/1.0/" rel="license">http://creativecommons.org/publicdomain/zero/1.0/)适用于本文中提供的数据，除非在数据的信用额度中另有说明。

转载及权限