Extremal Alignments in LCS‐Inference

ABSTRACT The problem of measuring the similarity or homology of (finite alphabet) strings appears in many areas of applications. A most common similarity measure is the length of the longest common subsequence (LCS). To every common subsequence corresponds at least one alignment, the alignments corresponding to LCS are called optimal. The set of optimal alignments is not unique and in [1] it was proposed to use the diversity of optimal alignments as another measure of similarity. This diversity was quantified via the distance between extremal alignments. In [1], it was shown that for strongly related sequences, this distance increases logarithmically and the more related the sequences, the slower is the growth. In the present paper, we consider another model—a pairwise Markov model—and show that for strongly related sequences the logarithmic growth still holds. Based on this logarithmic growth, a rate of convergence for the mean length of LCS is obtained. This rate is of order , which is faster than the best current rate for the iid independent case. Moreover, we show that extremal alignments are a useful technical tool for studying properties of LCS. In particular, a bound to the unknown Chvatal–Sankoff constant is derived.