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

An Algorithm for the Longest Pattern Subsequence Problem

作　　者：王晓东[1] 吴英杰[1] 

机构地区：[1]福州大学计算机科学与技术系,福建福州350002

出　　处：《小型微型计算机系统》2008年第1期135-138,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60172017)资助;福建省自然科学基金项目(A0510008)资助

摘　　要：最长模式子序列问题在生物信息学中有重要的应用.本文首次提出求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.

关 键 词：σ模式子序列 动态规划算法 RSK算法 标准Young表 

分 类 号：TP30[自动化与计算机技术—计算机系统结构]