An $O(n^2)$ Algorithm for Computing Longest Common Cyclic Subsequence

Details An $O(n^2)$ Algorithm for Computing Longest Common Cyclic Subsequence An $O(n^2)$ Algorithm for Computing Longest Common Cyclic Subsequence

2009-11-26

arxiv.org/abs/0911.5031v2

Computer Science

Data Structures and Algorithms

This paper has been withdrawn by the author due to a crucial error in the proofs

Scientific paper

The {\em longest common subsequence (LCS)} problem is a classic and well-studied problem in computer science. LCS is a central problem in stringology and finds broad applications in text compression, error-detecting codes and biological sequence comparison. However, in numerous contexts, words represent cyclic sequences of symbols and LCS must be generalized to consider all circular shifts of the strings. This occurs especially in computational biology when genetic material is sequenced form circular DNA or RNA molecules. This initiates the problem of {\em longest common cyclic subsequence (LCCS)} which finds the longest subsequence between all circular shifts of two strings. In this paper, we give an $O(n^2)$ algorithm for solving LCCS problem where $n$ is the number of symbols in the strings.

Affiliated with

Also associated with

No associations

Rating

An $O(n^2)$ Algorithm for Computing Longest Common Cyclic Subsequence 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 An $O(n^2)$ Algorithm for Computing Longest Common Cyclic Subsequence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An $O(n^2)$ Algorithm for Computing Longest Common Cyclic Subsequence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-116407