Sparse dynamic programming II: convex and concave cost functions
Sparse dynamic programming II: convex and concave cost functions
复制标题
稀疏动态规划二：凸凹成本函数
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
G. Italiano
中科院分区：
文献类型：
--
作者：
D. Eppstein;Z. Galil;R. Giancarlo;G. Italiano
考虑了两个递归方程的动态规划解，这两个递归方程用于从两个字符串之间的匹配片段集计算序列比对，并用于预测RNA二级结构。这些递归是在输入大小为二次的多个点上定义的；然而，只有稀疏集对结果有影响。当配准中的间隙或二级结构中的环的代价被视为间隙或环长度的凸函数或凹函数时，给出了求解这些问题的有效算法。我们算法的时间复杂性几乎线性地依赖于需要考虑的点数；当问题是稀疏的时，这导致比已知算法有很大的加速。
Dynamic programming solutions to two recurrence equations, used to compute a sequence alignment from a set of matching fragments between two strings, and to predict RNA secondary structure, are considered. These recurrences are defined over a number of points that is quadratic in the input size; however, only a sparse set matters for the result. Efficient algorithms are given for solving these problems, when the cost of a gap in the alignment or a loop in the secondary structure is taken as a convex or concave function of the gap or loop length. The time complexity of our algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse, this results in a substantial speed-up over known algorithms.