NGS 数据mapping 算法简介
简介
取得测序序列信息后，在有参考基因的情况下我们通过Mapping 到参考基因组进行后续分析；没有则重头拼接序列。
一般而言，基因组的组装将比read alignment 消耗更多的计算资源。然而，read alignment 也有一些基础的挑战。
- 参考基因组，组装不完整，存在一些gap。来源这些gap的read 将unmapped 或是 错误map 到相似区域。
- 基因组存在重复区，reads 会map 到多个区域，比对软件一般会随机选择一个区域。
- 比对软件需要容忍read 和参考基因之间的差异（SNV、Indel）
Read Alignment
一般流程
read alignment 一般分三个步骤。
- 对参考基因组建立索引
- 利用index 找到read 在参考基因组的大致位置（一般有多个候选位置）
- 对read 和 参考基因组相关区域进行pairwise alignment（SW、NW、汉明距离）
索引技术
Hashing 是最流行的参考基因组索引技术。
利用哈希表构建短序列（seed、K-mer）和参考基因组对应位置的映射关系。在mapping 时，从read 中截取相应长度的seed ，从哈希表中检索到参考基因组位置列表（精确比对）。
后缀树索引
基于后缀树的索引，通常更快。后缀树是一种树型数据结构，各个分支记录了基因组不同的后缀，共有的前缀只会被记录一次。
Pattern Searching using Suffix Tree - GeeksforGeeks
与哈希表索引不同，后缀树索引能够通过绕过某些node进行非精确匹配。除了少量工具单独使用后缀树索引，更多的工具采用BWT-FM 索引，来模拟后缀树遍历过程，同时可以减少内存消耗。
小结
基于Hashing 索引和BWT-FM索引的两大类方法，在运行效率上没有明显的差异。但是BWT-FM工具，对内存的消耗更少（Hashing 是其3.8倍以上）。
确定Reads 基因组比对位置
大部分的工具采用定长的seed来检索到reads 在基因组上的位置。一般这种seed 定位到的基因组位置比较多（取决于seed大小），大部分工具会采用启发式算法，计算每个给定位置的分值，设定检测阈值，从而避免检查seed 在基因组中出现的每一个位置。
提高seed长度，能同时减少每条read的seed数量以及，seed在基因组的位置数量。但是会降低比对的灵敏度（seed 越长，对应长度的read 可以容纳的错配数越低）。为了提高seed的长度，同时不降低比对的灵敏度，可以采用spaced seeds。
在比对过程中使用不同长度的seed，可以提高错配的容忍度，一般称为hybrid seeding。由于基于哈希表的索引方式，针对不同长度的seed要建立多个hash tables，会需要额外的计算资源，所以hybrid seeding 更多的是被BWT-FM索引工具采用。
Pairwise alignment
比对算法的最后一步就是计算，候选区域和reads 的实际相似程度，选择最佳的比对位置。
这一步的算法分为两大类，1. 基于动态规划的算法；2.非动态规划类算法。
动态规划类算法(DP)主要是，局部比对算法Smith-Warterman、全局比对算法Needleman-Wunsch。
非动态规划类算法(non-DP)：Hamming distance 、Rabin-Karp algorithm。
对indel感兴趣的话，DP类算法更好。也可以结合使用。
长读长reads 比对算法
随着长读长技术发展，相应也产生了对应的比对工具。目前长读长比对算法沿袭短读长算法的三步走方式。
有些算法甚至将长读长的read切割成的短读长，再分别进行比对。长读长算法要解决的主要问题是，较大的测序错误和异常多的seed。所以现行的算法，要通过启发式的方法从reads中截取比较少的seed 。最近的算法从基因组区域内的一组相邻的种子中寻找种子的最小代表集，而不是为整个种子集创建一个哈希表，称为minimizers。使用这种技术可以提高比对效率，降低准确性。
RNA-Seq 比对算法
RNA-Seq比对的难点在于，这是spliced alignment，需要解决的问题是，reads 可能会跨越内含子，存在一个大的gap。
Hashing 是RNA-Seq最常用的比对技术。
参考文献
Alser, M., Rotman, J., Deshpande, D. et al. Technology dictates algorithms: recent developments in read alignment. Genome Biol 22, 249 (2021). https://doi.org/10.1186/s13059-021-02443-7
