Parallel Construction and Inquiry Algorithm of Suffix Trees

A parallel suffix tree constructing algorithm is proposed to get rid of traditional space/time restriction while using suffix trees in bioinformatics. In this algorithm the given string is divided into several continuous substrings. Then, the suffix trees for every substring are constructed in parallel, thus forming a suffix tree structure distributed separately on several processors. This algorithm can not only reduce the time needed to construct suffix trees but also avoid the restriction of main memory. Performance analysis shows that this algorithm outperforms any of existing parallel algorithms. Based on such a suffix tree structure, an efficient pattern matching algorithm is also proposed for the inquiries about traditional suffix trees.