chapter  16
22 Pages

A BWT-Based Suffix Array Construction

In this chapter, we offer a different perspective on using SeqAn as a research tool and ask, how easily can SeqAn itself be extended? We do not want to plug together existing components, but write a component ourselves. We choose a relatively unknown suffix array construction algorithm called BwtWalk. Choosing SeqAn as an implementation platform gives us various benefits. First, we can easily compare the new algorithm to the existing suffix array construction algorithms that have already been implemented in SeqAn. Second, by using the same standard interface as those other algorithms, our algorithm can be used in all situations in which an arbitrary suffix array construction algorithm is required. And since the algorithm has been integrated into SeqAn, the implementation is available to the community. We describe the ideas behind BwtWalk, how we extend SeqAn with its implementation, and how we use SeqAn to test and benchmark it. The reader should be familiar with the suffix array basics described in Chapter 11.