Increasing the Speed of Smith-Waterman

Smith Waterman algorithm is extremely slow and therefore not useful for searching through a large library of sequences. Several improvements have been proposed to speed it up. The improvements mostly involve seeding and extension. The seeds are themselves stored either in hash-based indices, suffix arrays or lately as Burrows Wheeler Transform combined with FM index. Those concepts will be discussed in the following subsections.