  FM-index is an efficient data structure for string search and is widely used
in next-generation sequencing (NGS) applications such as sequence alignment and
de novo assembly. Recently, FM-indexing is even performed down to the read
level, raising a demand of an efficient algorithm for FM-index construction. In
this work, we propose a hardware-compatible Self-Aided Incremental Indexing
(SAII) algorithm and its hardware architecture. This novel algorithm builds
FM-index with no memory overhead, and the hardware system for realizing the
algorithm can be very compact. Parallel architecture and a special prefetch
controller is designed to enhance computational efficiency. An SAII-based
FM-index constructor is implemented on an Altera Stratix V FPGA board. The
presented constructor can support DNA sequences of sizes up to 131,072-bp,
which is enough for small-scale references and reads obtained from current
major platforms. Because the proposed constructor needs very few hardware
resource, it can be easily integrated into different hardware accelerators
designed for FM-index-based applications.
