Longest common subsequences of two random sequences
- 1 March 1975
- journal article
- research article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 12 (02) , 306-315
- https://doi.org/10.1017/s0021900200047999
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).Keywords
This publication has 3 references indexed in Scilit:
- A test for nucleotide sequence homologyJournal of Molecular Biology, 1973
- Matching Sequences under Deletion/Insertion ConstraintsProceedings of the National Academy of Sciences, 1972
- ber die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen KoeffizientenMathematische Zeitschrift, 1923