关键词: 后缀树, 并行构造, 字符串匹配, 生物序列, 生物信息学

Abstract: 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. The 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.