Suffix Tree
Wing-Kin Sung · 2009
The suffix tree of a string is a fundamental data structure for pattern matching [305]. It has many biological applications. The rest of this book will discuss some of its applications, including • Biological database searching (Chapter 5) • Whole genome alignment (Chapter 4) • Motif finding (Chapter 10) In this chapter, we define a suffix tree and present simple applications of a suffix tree. Then, we discuss a linear suffix tree construction algorithm proposed by Farach. Finally, we discuss the variants of a suffix tree like suffix array and FM-index. We also study the application of suffix tree related data structures on approximate matching problems.