Parsimony-spaced suffix trees for DNA sequences

Abstract

In recent years, bioinformatics becomes an important research field because there are more and more genetic data to be analyzed. The suffix tree is a powerful data structure for string analysis and has many applications on bioinformatics. Besides, its linear construction time, linear construction space and short search time all make it very impressive. However, consuming huge space is a fatal drawback especially while using suffix trees to handle the large amount of DNA sequences. In this paper, we utilize some characteristics of DNA sequences to reduce the space requirement of suffix trees. A new bit layout is proposed for the node of a suffix tree which requires less space than others. We also use an index table, called "prefix table", which can reduce the number of internal nodes in suffix trees. In addition, we propose a preprocessing technique to improve the construction time based on our data structure. The experiments shows that our proposed method is the most space-parsimony implementation of suffix trees for DNA sequences and it also has a good performance in construction time.