Improved bounds on the average length of longest common subsequences

ABSTRACT

It has long been known [Chvátal and Sankoff 1975] that the average length of the longest common subsequence of two random strings of length n over an alphabet of size k is asymptotic to γ_kn for some constant γ_k depending on k. The value of these constants remains unknown, and a number of papers have proved upper and lower bounds on them. We discuss techniques, involving numerical calculations with recurrences on many variables, for determining lower and upper bounds on these constants. To our knowledge, the previous best-known lower and upper bounds for γ₂ were those of Dančík and Paterson, approximately 0.773911 and 0.837623 [Dančík 1994; Dančík and Paterson 1995]. We improve these to 0.788071 and 0.826280. This upper bound is less than the γ₂ given by Steele's old conjecture (see Steele [1997, page 3]) that γ₂ = 2/(1 + &sqrt;2)≈ 0.828427. (As Steele points out, experimental evidence had already suggested that this conjectured value was too high.) Finally, we show that the upper bound technique described here could be used to produce, for any k, a sequence of upper bounds converging to γ_k, though the computation time grows very quickly as better bounds are guaranteed.

REFERENCES

• 1: Alexander, K. S. 1994. The rate of convergence of the mean length of the longest common subsequence. Ann. Appl. Prob. 4, 4, 1074--1082.
• 2: Apostolico, A., and Guerra, C. 1987. The longest common subsequence problem revisited. Algorithmica 2, 315--336.
• 3: Baeza-Yates, R. A., Gavaldà, R., Navarro, G., and Scheihing, R. 1999. Bounding the expected length of longest common subsequences and forests. Theory Comput. Syst. 32, 435--452.
• 4: Chvátal, V., and Sankoff, D. 1975. Longest common subsequences of two random sequences. J. Appl. Prob. 12, 306--315.
• 5: Dančík, V. 1994. Expected length of longest common subsequences. Ph.D. dissertation, Department of Computer Science, University of Warwick.
• 6: Vlado Dančík , Mike Paterson, Upper bounds for the expected length of a longest common subsequence of two binary sequences, Random Structures & Algorithms, v.6 n.4, p.449-458, July 1995 [doi>10.1002/rsa.3240060408]
• 7: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java(TM) Language Specification, The (3rd Edition) (Java (Addison-Wesley)), Addison-Wesley Professional, 2005
• 8: Daniel S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.24 n.4, p.664-675, Oct. 1977 [doi>10.1145/322033.322044]
• 9: Janson, S., Luczak, T., and Rucinski, A. 2000. Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York.
• 10: Tao Jiang , Ming Li, On the Approximation of Shortest Common Supersequencesand Longest Common Subsequences, SIAM Journal on Computing, v.24 n.5, p.1122-1139, Oct. 1995 [doi>10.1137/S009753979223842X]
• 11: Kiwi, M., Loebl, M., and Matoušek, J. 2005. Expected length of the longest common subsequence for large alphabets. Adv. Math. 197, 2, 480--498.
• 12: Kiwi, M., and Soto, J. 2008. On a speculated relation between Chvátal-Sankoff constants of several sequences. Combinatorics, Probability and Computing. To appear. Available on-line at http://arxiv.org/abs/0810.1066.
• 13: C. R. MacCluer, The Many Proofs and Applications of Perron's Theorem, SIAM Review, v.42 n.3, p.487-498, Sept. 2000 [doi>10.1137/S0036144599359449]
• 14: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 15: Michael L. Overton, Numerical computing with IEEE floating point arithmetic, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 16: Mike Paterson , Vlado Dancík, Longest Common Subsequences, Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science 1994, p.127-142, August 22-26, 1994
• 17: Pevzner, P. A. 2000. Computational Molecular Biology: An Algorithmic Approach. The MIT Press, Cambridge, MA.
• 18: Seneta, E. 1981. Non-negative Matrices and Markov Chains, 2nd ed. Springer Series in Statistics. Springer-Verlag, New York.
• 19: Steele, J. M. 1997. Probability Theory and Combinatorial Optimization. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, PA.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Generating functions; Recurrences and difference equations
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Arratia-Steele conjecture, Longest common subsequences, average-case analysis, dynamic programming