On random strings and sequence comparisons
David E. Foulser · 1986
Sequence analysis is concerned with the comparison of finitely long strings of letters drawn from a finite alphabet. This dissertation considers two models of comparing random strings and examines the random length of their resulting features, the longest generalized success run in a semi-Markov chain and the longest common subsequence of two or more compared sequences. The first chapter examines a semi-Markov renewal process in which certain durations are labeled success durations and the remainder are failure durations. We derive the limiting distribution of the first passage time until a success duration of length at least x. We also characterize the limiting behavior of the longest observed success duration until epoch t and provide its lower and upper limiting distributions. Applications of these results include long runs of heads in many tosses of a Markov dependent coin, runs of general patterned types in Markov dependent sequences, runs admitting a prescribed number of errors, and the longest continous occupation time of the positive axis in a random walk on the integers. The second principal subject of the dissertation examines the behavior of long monotone paths. The longest common subsequence (LCS) of two or more target sequences is a common measure of sequence similarity. We derive asymptotic lower and upper bounds on the expected LCS fraction, the expected ratio of LCS length to target sequence length, assuming non-uniform letter densities. A related problem considers the longest monotone path (LMP) through matches located at random on a square lattice. New asymptotic bounds for this process are also displayed. The third principal division investigates special versions of the LCS and LMP problems. We produce exact asymptotic match fractions and variances for a case in which one target sequence obeys a deterministic pattern. Exact asymptotic match fractions are also given for LCS and LMP calculations in which the longest monotone path is required to remain within a finite-width band centered on the main diagonal.