Computer Science – Data Structures and Algorithms
Scientific paper
2009-03-11
Computer Science
Data Structures and Algorithms
25 pages, 6 figures. Ready to be submitted
Scientific paper
The problem of finding the longest common subsequence (LCS) for a set of sequences is a very interesting and challenging problem in computer science. This problem is NP-complete, but because of its importance, many heuristic algorithms have been proposed, such as Long Run algorithm and Expansion algorithm. However, the performance of many current heuristic algorithms deteriorates fast when the number of sequences and sequence length increase. In this paper, we have proposed a post process heuristic algorithm for the LCS problem, the Deposition and Extension algorithm (DEA). This algorithm first generates common subsequence by the process of sequences deposition, and then extends this common subsequence. The algorithm is proven to generate Common Subsequences (CSs) with guaranteed lengths. The experiments show that the results of DEA algorithm are better than those of Long Run and Expansion algorithm, especially on many long sequences. The algorithm also has superior efficiency both in time and space.
No associations
LandOfFree
Deposition and Extension Approach to Find Longest Common Subsequence for Multiple Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Deposition and Extension Approach to Find Longest Common Subsequence for Multiple Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deposition and Extension Approach to Find Longest Common Subsequence for Multiple Sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-124273