Abstract.

The length of a longest common subsequence (LLCS) of two or more strings is a useful measure of their similarity. The LLCS of a pair of strings is related to the `edit distance', or number of mutations/errors/editing steps required in passing from one string to the other.

In this talk, we explore some of the combinatorial properties of the sub- and super-sequence relations, survey various algorithms for computing the LLCS, and introduce some results on the expected LLCS for pairs of random strings.

Full paper (132K) is available in compressed postscript format.

Bibtex entry:

@InProceedings{PaDa94,
  author =       "Mike Paterson and Vlado Dan{\v c}{\'\i}k",
  title =        "Longest Common Subsequences",
  editor =       "I. Pr{\`\i}vara, B. Rovan, P. Ru{\v z}i{\v c}ka",
  pages =        "127-142",
  booktitle =    "19th International Symposium Mathematical
                  Foundations of Computer Science, Proceedings",
  year =         "1994",
  publisher =    "Lecture Notes in Computer Science 841, Springer-Verlag",
}

Return to Previous Level

USC Computational Biology Home Page