多序列的近似LCS改进算法  

Improved Approximation Algorithms for Longest Common Subsequence of Multiple Sequences

作　　者：胡婕[1] 业宁[1,2] 罗晓波[1] 崔静[1] 董程玲[1] 

机构地区：[1]南京林业大学信息科学技术学院,南京210037 [2]山东大学计算机科学技术学院,济南250101

出　　处：《计算机工程》2011年第2期166-168,171,共4页Computer Engineering

基　　金：江苏省自然科学基金资助项目(BK2009393)

摘　　要：提出2种针对3条源序列的近似LCS算法,近似因子均为1/|∑|。其中,线性近似LCS算法的时空复杂度均为O(n),n为最长源序列的长度,适于解决大规模问题。递归近似LCS算法时空复杂度均为O(nlogn),适于要求高精度问题。同时,这2种算法都能用于解决多序列的LCS和CLCS问题。实验验证了这2种算法的有效性。This paper proposes two approximation algorithms for LCS problem of three input strings. Even if the approximation factors of the two algorithms are still 1/∑, they can both get much better results in comparison of Gotthilf＇s approximating LCS algorithm in most eases. Linear approximating LCS algorithm, takes O（n） time and O（n） space, where n is the length of the longest input sequence. It can work well in the case of large scale input strings. Recursivc approximating LCS algorithm, whose time and space complexities both are O（nlogn）, can receive the best precision among these algorithms at the most time. It is applicable to meet the desire of good precision for corresponding LCS problem. The two algorithms can be used to solve the LCS problem of multiple sequences and CLCS problem of multiple sequences. Experimental results prove the validity of the two algorithms.

关 键 词：生物信息学 最长公共子序列 近似因子 约束 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]