The enhanced suffix array and its applications to genome analysis

MI Abouelhoda, S Kurtz, E Ohlebusch - Algorithms in Bioinformatics …, 2002 - Springer
MI Abouelhoda, S Kurtz, E Ohlebusch
Algorithms in Bioinformatics: Second International Workshop, WABI 2002 Rome …, 2002Springer
In large scale applications as computational genome analysis, the space requirement of the
suffix tree is a severe drawback. In this paper, we present a uniform framework that enables
us to systematically replace every string processing algorithm that is based on a bottomup
traversal of a suffix tree by a corresponding algorithm based on an enhanced suffix array (a
suffix array enhanced with the lcp-table). In this framework, we will show how maximal,
supermaximal, and tandem repeats, as well as maximal unique matches can be efficiently …
Abstract
In large scale applications as computational genome analysis, the space requirement of the suffix tree is a severe drawback. In this paper, we present a uniform framework that enables us to systematically replace every string processing algorithm that is based on a bottomup traversal of a suffix tree by a corresponding algorithm based on an enhanced suffix array (a suffix array enhanced with the lcp-table). In this framework, we will show how maximal, supermaximal, and tandem repeats, as well as maximal unique matches can be efficiently computed. Because enhanced suffix arrays require much less space than suffix trees, very large genomes can now be indexed and analyzed, a task which was not feasible before. Experimental results demonstrate that our programs require not only less space but also much less time than other programs developed for the same tasks.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果