title: A bioinformatician's guide to the forefront of suffix array construction algorithms.
abstract: The suffix array and its variants are text-indexing data structures that have become indispensable in the field of bioinformatics. With the uninitiated in mind, we provide an accessible exposition of the SA-IS algorithm, which is the state of the art in suffix array construction. We also describe DisLex, a technique that allows standard suffix array construction algorithms to create modified suffix arrays designed to enable a simple form of inexact matching needed to support 'spaced seeds' and 'subset seeds' used in many biological applications.
authors.affiliation: Computational Biology Research Center, AIST, Tokyo, Japan. computome@gmail.com.
authors.forename: Anish Man Singh
authors.initials: AM
authors.lastname: Shrestha
authors.forename: Martin C
authors.initials: MC
authors.lastname: Frith
authors.forename: Paul
authors.initials: P
authors.lastname: Horton
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030561:Databases, Nucleic Acid / Q000706:statistics & numerical data; D006801:Humans; D010363:Pattern Recognition, Automated / Q000706:statistics & numerical data; D012984:Software
keywords: linear-time algorithm; spaced seeds; subset seeds; suffix array construction; text index