New Implementation for the Multi-sequence All-Against-All Substring Matching Problem

The threshold all-against-all problem in approximate string matching has important applications in bioinformatics. For two input sequences, an algorithm has been developed which depends linearly on the sizes of each of the sequences. However, this algorithm doesn’t extend efficiently to more than two sequences in a straightforward manner. After modifying the problem somewhat, we have developed a fast algorithm which reports patterns unusually conserved between any number of input sequences, and also returns all of their approximate matches