Path properties of LCSoptimal alignments

We investigate the behavior of optimal alignment paths for related and non-related random sequences. An alignment between two finite sequences is optimal if it corresponds to the longest common subsequence (LCS). We prove the exis-tence of lowest and highest optimal alignments and study their differences. High differences between the extremal alignments imply the high variety of all optimal alignments. We present several simulations indicating that the related sequences have typically the distance between the extremal alignments of much smaller size than independent (unrelated) sequences. In particular, the simulations suggest that for the related sequences, the growth of the distance between the extremal align-ments is logarithmical. The main theoretical results of the paper prove that (under some assumptions) this is the case, indeed. The paper suggests that the properties of the optimal alignment paths characterize the relatedness of the sequences