Title :
An Improve Algorithm for the Longest Common Subsequence Problem
Author :
Xiang, Xuyu ; Zhang, Dafang ; Qin, Jiaohua
Author_Institution :
Hunan Univ., Changsha
Abstract :
There are two general approaches to the longest common subsequence problem. The dynamic programming approach takes quadratic time but linear space, while the nondynamic-programming approach takes less time but more space. We propose a new implementation of the latter approach which seems to get the best for both time and space for the DNA application.
Keywords :
DNA; dynamic programming; DNA application; dynamic programming approach; linear space; longest common subsequence problem; nondynamic-programming approach; Counting circuits; DNA; Dynamic programming; Filling; Genetic mutations; Heuristic algorithms; Information technology; Sequences;
Conference_Titel :
Convergence Information Technology, 2007. International Conference on
Conference_Location :
Gyeongju
Print_ISBN :
0-7695-3038-9
DOI :
10.1109/ICCIT.2007.124