All-Against-All Sequence Matching

In this paper we present an algorithm which attempts to align pairs of subsequences from a database of DNA sequences. The algorithm simulates the classical dynamic programming alignment algorithm over a digital index of the database. The running time of the algorithm is subquadratic on average with respect to the database size. A similar algorithm solves the approximate string matching problem in sublinear average time. 1 Introduction An all-against-all matching is defined as an attempt to find an alignment for each possible subsequence against each other possible subsequence in a DNA or peptide database. These alignments are done with the standard methods of dynamic programming (Needleman & Wunsch algorithm [NW70]) and are based on a matrix describing the likelihood of homology between pairs of entries in the sequence (e.g. a Dayhoff matrix [DSO78]). The output of this matching will consist of all pairs of subsequences which achieve a given level of similarity. Note that we are not a..