Approximate p-values for local sequence alignments. A technical report

Assume that two sequences from a finite alphabet are optimally aligned according to a scoring system that rewards similarities according to a general scoring scheme and penalizes gaps (insertions and deletions). Under the assumption that the letters in each sequence are independent and identically distributed and the two sequences are also independent, approximate p-values are obtained for the optimal local alignment when either (i) there are at most a fixed number of gaps, or (ii) the gap initiation cost is sufficiently large. In the latter case the approximation can be written in the same form as the well known case of ungapped alignments. 1 1 Introduction. An important step in learning the function of a new gene (DNA sequence) or protein (amino acid sequence) is to compare the new sequence with existing sequences in a data base search, e.g., of the DNA data base GenBank maintained by the National Institutes of Health. In addition to the sequence information these data bases contain whateve