Institution: Stanford University, Department of Computer Science

Title: Longest common subsequences of two random sequences.

Author: Chvatal, Vaclav

Author: Sankoff, David

Date: January 1975

Abstract: Given two random k-ary sequences of length n, what is f(n,k), the expected length of their longest common subsequence? This problem arises in the study of molecular evolution. We calculate f(n,k) for all k, where n $\leq$ 5 , and f(n,2) where n $\leq$ 10. We study the limiting behavior of $n^{-1}$f(n,k) and derive upper and lower bounds on these limits for all k. Finally we estimate by Monte-Carlo methods f(100,k), f(1000,2) and f(5000,2).

http://i.stanford.edu/pub/cstr/reports/cs/tr/75/477/CS-TR-75-477.pdf