A graph approach to the threshold all-against-all substring matching problem
Marina Barsky, Ulrike Stege, Alex Thomo, Chris Upton · ACM Journal of Experimental Algorithmics · 2008
We present a novel graph model and an efficient algorithm for solving the “threshold all against all” problem, which involves searching two strings (with length M and N , respectively) for all maximal approximate substring matches of length at least S , with up to K differences. Our algorithm solves the problem in time O ( MNK 3 ), which is a considerable improvement over the previous known bound for this problem. We also provide experimental evidence that, in practice, our algorithm exhibits a better performance than its worst-case running time.