[HTML][HTML] Replacing suffix trees with enhanced suffix arrays

MI Abouelhoda, S Kurtz, E Ohlebusch - Journal of discrete algorithms, 2004 - Elsevier
MI Abouelhoda, S Kurtz, E Ohlebusch
Journal of discrete algorithms, 2004Elsevier
The suffix tree is one of the most important data structures in string processing and
comparative genomics. However, the space consumption of the suffix tree is a bottleneck in
large scale applications such as genome analysis. In this article, we will overcome this
obstacle. We will show how every algorithm that uses a suffix tree as data structure can
systematically be replaced with an algorithm that uses an enhanced suffix array and solves
the same problem in the same time complexity. The generic name enhanced suffix array …
The suffix tree is one of the most important data structures in string processing and comparative genomics. However, the space consumption of the suffix tree is a bottleneck in large scale applications such as genome analysis. In this article, we will overcome this obstacle. We will show how every algorithm that uses a suffix tree as data structure can systematically be replaced with an algorithm that uses an enhanced suffix array and solves the same problem in the same time complexity. The generic name enhanced suffix array stands for data structures consisting of the suffix array and additional tables. Our new algorithms are not only more space efficient than previous ones, but they are also faster and easier to implement.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果