Report Number: CS-TR-75-477
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