Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (31): 45-47.

• 学术探讨 • Previous Articles     Next Articles

LCS algorithm research for gene sequence similar degree

WANG Ying-long1,2,YANG Bing-ru1,SONG Ze-feng1,CHEN Zhuo1,TANG Jian-jun2   

  1. 1.School of Information Engineering,University of Science and Technology Beijing,Beijing 100083,China
    2.School of Computer and Information Engineering,Jiangxi Agriculture University,Nanchang 330045,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-11-01 Published:2007-11-01
  • Contact: WANG Ying-long

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

王映龙1,2,杨炳儒1,宋泽锋1,陈 卓1,唐建军2   

  1. 1.北京科技大学 信息工程学院,北京 100083
    2.江西农业大学 计算机与信息工程学院,南昌 330045
  • 通讯作者: 王映龙

Abstract: 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.

摘要: 首先重新审视了采用穷举法求解LCS问题的困难,以及对应的优点;随后针对穷举法的优点进行了两类优化;最后给出了算法实现的图示以及算法的结论。通过实验证明,算法的效率较传统的动态规划的LCS算法有了很大的提升。