A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
复制标题
加权最长公共子序列的可扩展近似算法
DOI：
10.1007/978-3-030-85665-6_23
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Moseley, B.
中科院分区：
文献类型：
--
作者：
Buhler, J.;Lavastida, T.;Lu, K.;Moseley, B.
介绍了一种新的加权最长公用子序列的并行计算方法及其推广--全子串公用子序列。以前的工作是通过Monge矩阵乘法为这些问题开发出高效的算法，这是进一步改进的限制因素。与这些方法不同的是，我们使用了一种不同的、自然的动态程序来控制地放松算法的最优性保证，该程序可以用分而治之的方式来描述和求解，从而提高了并行的效率。此外，为了计算算法的基本情况，我们提出了一种新的高效的方法来计算所有子串的WLCS，该方法的灵感来自于以前在未加权的全子串LCS上所做的工作，该方法利用了典型的小范围的权重。据我们所知，这是BSP中所有子串WLCS和WLCS的最快近似算法。此外，随着处理器数量的增加，这是加权LCS的渐近最快的并行算法。
This work introduces novel parallel methods for weighted longest common subsequence (WLCS) and its generalization, all-substrings WLCS. Previous work developed efficient algorithms for these problems via Monge matrix multiplication, which is a limiting factor for further improvement. Diverging from these approaches, we relax the algorithm’s optimality guarantee in a controlled way, using a different, natural dynamic program which can be sketched and solved in a divide-and-conquer manner that is efficient to parallelize.Additionally, to compute the base case of our algorithm, we develop a novel and efficient method for all-substrings WLCS inspired by previous work on unweighted all-substrings LCS, exploiting the typically small range of weights.Our method fits in most parallel models of computation, including the PRAM and the BSP model. To the best of our knowledge this is the fastest-approximation algorithm for all-substrings WLCS and WLCS in BSP. Further, this is the asymptotically fastest parallel algorithm for weighted LCS as the number of processors increases.
序列比对的蒙日性质
影响因子：
1.1
作者：
L. Russo
通讯作者：
L. Russo
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Shuhei Denzumi
通讯作者：
Shuhei Denzumi
DOI：
10.1016/s1046-2023(05)80165-3
发表时间：
1991-01-01
期刊：
Methods (Orlando)
影响因子：
--
作者：
STATES D J;GISH W;ALTSCHUL S F
通讯作者：
ALTSCHUL S F