The expected number of matches in optimal global sequence alignments

Abstract
Sequence comparison is used in molecular biology to detect and characterise the homology between two or more sequences. Many optimal alignment 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 determined by simulation or Monte Carlo methods or chosen to give “biologically interesting” results. This paper outlines how lattice walks and generating functions could be used to find the expected number of matches in the optimal alignment of two sequences, in several special cases. Solving the resulting equations proves difficult.

This publication has 19 references indexed in Scilit: