Abstract.

Let $f(n)$ be the expected length of a longest common subsequence of two random sequences over a fixed alphabet of size $k$. It is known that $f(n)\to c_kn$ for some constant $c_k$. We define a collation as a pair of sequences with marked matches. A dominated collation is a collation that is not matched optimally. Upper bounds for $c_k$ can be derived from upper bounds for the number of nondominated collations. Using local properties of matches we can eliminate many nondominated collations and improve upper bounds for $c_k$.

Full paper (79K) is available in compressed postscript format.

Bibtex entries:

@Article{Dan94,
  author =       "Vlado Dan{\v c}{\'\i}k",
  title =        "Upper bounds for the expected length of a longest
                  common subsequence",
  journal =      "Bulletin of EATCS",
  year =         "1994",
  volume =       "54",
  pages =        "248",
  month =        "October",
  note =         "Abstract" 
}

Return to Previous Level

USC Computational Biology Home Page