Longest common subsequences of two random sequences.

[摘要] 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).

[学科分类] 计算机科学（综合）