N-SAMSAM: A simple and faster algorithm for solving approximate matching in DNA sequences

Abstract

This work proposes a novel algorithm to do approximate matching in a database consisting of multiple sequences. We apply Agrep algorithm in an indexing structure, the r-cut numerical substring array (r-NSA). The structure basically indexes all the substrings of length r. The advantage of using the r-NSA is two-fold: (1) The space requirement of the r-NSA is much smaller than that of the other existing indexing structures, such as the generalized suffix tree. (2) We propose an algorithm to apply Agrep in the r-NSA, in which the substrings are processed sequentially. Since the common substrings are processed only once, the cost of our algorithm is smaller than that of the full scanning search by Agrep. Consequently, the matching time of our algorithm is also reduced. We design experiments to validate and compare the performance of our algorithm against the full scanning search by Agrep. We define the speed-up of our algorithm as the time required by the full scanning search by Agrep over that of our algorithm. We use eight sets of real DNA sequences in our experiments, and the results show that our algorithm achieves significant speed-up. We also investigate the speed-up of difference data sets, and analyze their differences in detail. © 2008 IEEE.