Back to Search
Start Over
A New Efficient Algorithm for Computing the Longest Common Subsequence.
- Source :
-
Theory of Computing Systems . Aug2009, Vol. 45 Issue 2, p355-371. 17p. 12 Diagrams. - Publication Year :
- 2009
-
Abstract
- The Longest Common Subsequence (LCS) problem is a classic and well-studied problem in computer science. The LCS problem is a common task in DNA sequence analysis with many applications to genetics and molecular biology. In this paper, we present a new and efficient algorithm for solving the LCS problem for two strings. Our algorithm runs in O(ℛlog log n+ n) time, where ℛ is the total number of ordered pairs of positions at which the two strings match. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 45
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 41328879
- Full Text :
- https://doi.org/10.1007/s00224-008-9101-6