Preface; Contents; Contributors; Part I Indexing, Compression, and Storage of NGS Data; 1 Algorithms for Indexing Highly Similar DNA Sequences; 1.1 Introduction; 1.2 Basic Concepts; 1.3 Basic Data Structures; 1.3.1 Trie; 1.3.1.1 Structure Construction; 1.3.1.2 Search for a Pattern P of Length m; 1.3.2 Suffix Tree; 1.3.2.1 Structure Construction; 1.3.2.2 Search for a Pattern P of Length m; 1.3.3 DAWG; 1.3.3.1 Structure Construction; 1.3.3.2 Search for a Pattern P of Length m; 1.3.4 Suffix Array; 1.3.4.1 Structure Construction; 1.3.4.2 Search for a Pattern P of Length m

1.4 Advanced Data Structures1.4.1 FM Index; 1.4.1.1 Burrows-Wheeler Transform; 1.4.1.2 Backward Search; 1.4.2 Compressed Suffix Array ; 1.4.2.1 Grossi-CSA; 1.4.2.2 Sadakane-CSA; 1.4.2.3 Grossi-Gupta-CSA; 1.4.3 Lempel-Ziv Indexes; 1.4.3.1 LZ78 Algorithm; 1.4.3.2 LZ Index; 1.5 More Advanced Data Structures; 1.5.1 Common and Differentiating Segments; 1.5.1.1 Model 1; 1.5.1.2 Model 2; 1.5.1.3 A Second Solution; 1.5.2 Fast Relative Lempel-Ziv Self-index; 1.5.3 BIO-FMI Index; 1.5.3.1 Description; 1.5.4 Suffix Tree of an Alignment; 1.5.4.1 Structure Construction

1.5.4.2 Search for a Pattern P of Length m1.5.5 Suffix Array of an Alignment; 1.5.5.1 Structure Construction; 1.5.5.2 Search for a Pattern P of Length m; 1.6 Conclusion; References; 2 Full-Text Indexes for High-Throughput Sequencing; 2.1 Introduction; 2.1.1 Notations; 2.1.2 Padding; 2.2 Background; 2.2.1 Suffix Trie; 2.2.2 Suffix Tree; 2.2.3 Suffix Array; 2.2.4 Burrows-Wheeler Transform; 2.2.4.1 Inversion; 2.3 Suffix Trie Realizations; 2.3.1 Suffix Array; 2.3.2 FM-Index; 2.3.2.1 Rank Dictionaries; 2.3.2.2 Top-Down Traversal; 2.3.2.3 Sparse Suffix Array; 2.4 Suffix Tree Realizations

2.4.1 Enhanced Suffix Array2.4.1.1 LCP Table; 2.4.1.2 Child Table; 2.4.1.3 Top-Down Traversal; 2.4.2 Lazy Suffix Tree; 2.4.2.1 The WOTD Algorithm; 2.4.2.2 The Data Structure; 2.4.2.3 Node Expansion; 2.4.2.4 Generalization to Multiple Sequences; 2.5 q-Gram Index Realizations; 2.5.1 Direct Addressing; 2.5.2 Open Addressing; 2.6 Applications; 2.6.1 Depth-First Traversal; 2.6.2 Exact String matching; 2.6.3 Approximate String Matching; 2.7 Conclusion; References; 3 Searching and Indexing Circular Patterns; 3.1 Introduction; 3.2 Circular Dictionary Matching

3.2.1 Properties of the Partitioning Technique3.2.2 Circular String Matching via Filtering; 3.2.2.1 Longest Common Extension; 3.2.2.2 Algorithm CSMF; 3.2.2.3 Algorithm CSMF-Simple; 3.2.3 Circular Dictionary Matching via Filtering; 3.2.4 Key Results; 3.3 Circular Pattern Indexing; 3.3.1 The CPI-II Data Structure; 3.3.2 A Folklore Indexing Data Structure; 3.3.3 Key Results; 3.4 Final Remarks and Outlook; References; 4 De Novo NGS Data Compression; 4.1 Introduction; 4.2 Generic Text Compression; 4.2.1 Coding; 4.2.2 Modeling; 4.2.2.1 Basic Modeling; 4.2.2.2 Statistical-Based Approach