- 1. Introduction
- 1.1 Introduction
- 1.2 The World of Mapping Programs
- 1.3 Why Do Biologists Need So Many Mapping Programs?
- 1.4 The Mapping Problem
- 1.5 Search Score and E-value
- 2. Core Algorithms
- 2.1 Smith-Waterman Algorithm
- 2.2 Increasing the Speed of Smith-Waterman
- 2.3 Indexing
- 2.4 Suffix Arrays
- 2.5 Reversible Transform and Data Compression
- 2.6 Burrows Wheeler Transform
- 2.7 Reversibility of BWT
- 2.7 LF Property
- 2.8 Reversibility of BWT
- 2.9 Thinking Conceptually about BWT
- 2.11 Search Using LF Property
- 2.12 FM Index
- 2.13 Summary
- 3. Advanced Concepts
- 3.1 Introduction
- 3.2 BWT-SW
- 3.3 Bidirectional BWT
- 3.4 SA-IS for Constructing Suffix Array
- 3.5 External Memory Construction of Suffix Array
- 3.6 Bauer-Cox-Rosone Algorithm for LightWeight BWT Construction
- 3.7 Lyndon Word and Lyndon Factorization
- 4. Implementations
- 4.1 The World of Mapping Programs
- 4.2 FASTA
- 4.3 BLAST
- 4.4 BLAT
- 4.5 Exonerate
- 4.6 Mummer
- 4.7 AVID
- 4.8 LAGAN
- 4.9 Mauve
- 4.11 Lastz
- 4.12 SSAHA
- 4.13 ELAND
- 4.14 SOAP
- 4.15 MAQ
- 4.16 SHRiMP
- 4.17 BWA
- 4.18 Bowtie
- 4.19 BFAST
- 4.21 Stampy
- 4.22 SOAP2
- 4.23 BWA-SW
- 4.24 Bowtie2
- 4.25 BLASR
- 4.26 BWA-MEM
- 4.27 Hidden Markov Model-based Algorithms
- 5. Hardware-accelerated Implementations
- 5.1 Introduction
- 5.2 Hardware-accelerated Smith-Waterman
- 5.3 GPU-accelerated SOAP3-dp
- 5.4 FPGA-accelerated Shepard
- 5.5 CPU-accelerated STAR
- 6. References and Future Challenges
- 6.1 Historical Developments on Suffix Array
- 6.2 Review Paper
- 6.3 Burrows Wheeler Transform
- 6.4 Mapping
- 6.5 Hardware Acceleration of Mapping
- 6.6 Unsolved problems
Note: These tutorials are incomplete. More complete versions are being made available for our members. Sign up for free.
FPGA-accelerated Shepard
Uses minimal perfect hash in FPGA.
