THE EXPECTED NUMBER OF MATCHES IN OPTIMAL GLOBAL SEQUENCE ALIGNMENTS

Sequence comparison is used in molecular biology to detect and charact erise the homology between two or more sequences. Many optimal alignme nt algorithms have been developed to produce the alignment with least overall cost. However, each of these methods depend upon the relative cost of a null being given a priori. This cost has usually been determ ined by simulation or Monte Carlo methods or chosen to give ''biologic ally interesting'' results. This paper outlines how lattice walks and generating functions could be used to find the expected number of matc hes in the optimal alignment of two sequences, in several special case s. Solving the resulting equations proves difficult.