最长模式子序列问题的算法分析

An Algorithm for the Longest Pattern Subsequence Problem

最长模式子序列问题在生物信息学中有重要的应用.本文首次提出求a=a0a1…an-1∈ωn的最长σ模式子序列的O(n2)时间算法,并对σ≤2的情形推广了RSK算法和标准Young表,对算法作了改进,得到了当σ=1时的O(nlogk)时间算法和当σ=2时的O(n)时间算法.

This paper studies the longest pattern subsequence problem based on the dynamic programming algorithm. An O（n^2） time algorithm for the problem is firstly presented. Then the presented algorithm is improved further by generalizing the RSK algorithm and the standard Young tableau. When ｜σ｜ = 1, the time required by the algorithm is improved to O（nlogk）. When ｜σ｜ =2, the time required by the algorithm is improved to O（n）, an optimal algorithm.