Longest common subsequences of two random sequences

1975/06/01 by Václav Chvátal, David Sankoff · 7 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #Algorithms and Data Compression #RNA and protein synthesis mechanisms #Fractal and DNA sequence analysis #Mathematics #Longest common subsequence problem #Combinatorics #Longest increasing subsequence #Limiting #Subsequence #Upper and lower bounds #Monte Carlo method #Statistics #Mathematical analysis

paper · doi:10.2307/3212444

openalex publication_date 1975/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26

Abstract

Summary 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 ≦ 5, and f ( n, 2) where n ≦ 10. We study the limiting behaviour 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).

Cited by

• A guided tour to approximate string matching
• Exact asymptotic results for the Bernoulli matching model of sequence alignment
• Expected length of the longest common subsequence for large alphabets
• Improved bounds on the average length of longest common subsequences
• Unzipping of two random heteropolymers: Ground-state energy and finite-size effects
• Probability
• Longest common subsequence [wikipedia]