基因序列相似程度的LCS算法研究  

LCS algorithm research for gene sequence similar degree.

作　　者：王映龙[1] 杨炳儒[1] 宋泽锋[1] 陈卓[1] 唐建军[2] 

机构地区：[1]北京科技大学信息工程学院,北京100083 [2]江西农业大学计算机与信息工程学院,南昌330045

出　　处：《计算机工程与应用》2007年第31期45-47,共3页Computer Engineering and Applications

基　　金：国家自然科学基金(the National Natural Science Foundation of China under Grant No.60675030);教育部科技重点项目(No.教技司 [2000]175)

摘　　要：首先重新审视了采用穷举法求解LCS问题的困难,以及对应的优点;随后针对穷举法的优点进行了两类优化;最后给出了算法实现的图示以及算法的结论。通过实验证明,算法的效率较传统的动态规划的LCS算法有了很大的提升。This paper first re-examines the difficulty of using the exhaustion method to solve the LCS question,as well as corresponding advantages,and then aims at merit of the exhaustion method to present two types of optimizations,finally,produces the algorithm achievement and algorithm conclusions.The experiment proves that the algorithm efficiency than conventional dynamic programming LCS algorithm has been greatly improved.

关 键 词：最长公共子序列 穷举法 基因序列排比 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP309[自动化与计算机技术—计算机科学与技术]