A Practical Algorithm for the All-Pairs Suffix-Prefix Problem

Abstract

The all-pairs suffix-prefix problem occurs as a subproblem of DNA sequence assembly where it is the most time-consuming part of the whole assembly process. In stringology, the optimal algorithms have been already proposed for the problem using a generalized suffix tree and enhanced suffix array. Since the generalized suffix tree and enhanced suffix array are heavy machineries, practical algorithms which are non-optimal but fast in practice have been proposed in bioinformatics. Among them, Readjoiner and SOF are state-of-the-art practical algorithms.

In this thesis, we present an algorithm for the all-pairs suffix-prefix problem that uses a simple data structure for storing input strings and advanced algorithmic techniques for matching, which together lead to fast running time in practice. Experimental results shows that our algorithm is about 10 times faster than SOF and about 20 times faster than Readjoiner on average in 16 real datasets and 2 random datasets. We also obtain reasonable scalability with a parallel implementation of our algorithm. We estimate the running time of matching step of our algorithm and present that the ratio of running time of SOF and our algorithm has a tendency to be proportional to $m/B$ of datasets through experimental analyses. We also show the relation between the running time of three algorithms (i.e., Readjoiner, SOF, and our algorithm) and the number of overlaps for datasets.