基因组序列比对（read alignment）技术，是将测序得到的read与已有的参考基因组进行比对，找到read与参考基因组匹配的对应位置，继而得到序列比对的详细结果。 由于参考基因组碱基数极多，测序得到的read数据量极大，且测序的DNA序列中存在各种碱基变异和测序错误，因此不能直接将read与参考基因组进行比对。 而需要采用一些方法，对参考基因组和read数据进行处理，运用一些算法进行序列比对，以减少内存的耗费，提高序列比对的速度和准确度。
传统的序列比对方法Needleman-Wunsch算法[10]和Smith-Waterman算法[11]均采用的是动态规划算法原理，计算量大，耗时长，不适用于高通量数据的处理。 之后产生的 FASTA[12]、BLAST[13]等较为系统的序列比对算法，基本能够适应数据量较小的序列比对问题的需求。 但是，由于高通量测序数据的序列比对面临着参考基因组长度大、read数量多、read存在测序错误等多个方面的问题，经典的序列比对方法已难以满足需要。 当前，序列比对主要通过对参考基因组或read文件建立索引，进行映射定位，并根据索引特性和应用需求设计相应的比对处理方法以提高效率。
目前主流的 read 映射定位方法按索引的不同可分为两大类： （1）基于哈希表（Hash Table）的映射定位方法，如SSAHA[14]、BLAST[13]、YAHA[15]、rHAT[16]、MAQ[17]、mr FAST[18]、mrs FAST[19]、SHRi MP[20]、SHRi MP2[21]等； （2）基于前缀或后缀树（Prefix/Suffix Trie）索引的映射定位方法[22][23]，如BLASR[24]、BWA[25]、BWT-SW[26]、BWA-SW[27]、BWA-MEM[28]、Bowtie[29]、Bowtie2[30]、SOAP2[31]、SOAP2-dp[32]等。
基于哈希表索引的映射定位方法的核心思想是，将参考基因组切分为碱基长度为k的短片段，即k-mer，通过哈希表存储不同k-mer的键值以及在参考基因组中出现的位置，以此作为索引，构建哈希索引表。在比对时，依次扫描read中的k-mer与参考基因组中的k-mer对应的所有哈希命中，然后对这些命中数据进行处理和分析，进而得到序列比对结果。
基于前缀、后缀树索引的映射定位方法的主要思路是建立参考基因组的前缀、后缀树，并将read与参考基因组之间的非精确匹配转换成某种精确匹配，进而通过前缀、后缀树查询参考基因组上所有精确匹配的子串位置。基于前缀或后缀树的方法较为复杂，而基于哈希索引表的方法简单易懂，易于编程实现，本文仅讨论基于哈希表映射定位进行序列比对的方法。
现在已有的高通量序列比对算法当中，更多的是面向第二代测序技术测得的序列数据，进行序列比对或基因变异检测的工具，如GEM[33]、STAR[34]、SeqAlto[35]、BWA[25]等。或在此基础上改进，利用短序列比对技术的工具，进而处理第三代测序技术测得的序列数据，如LAMSA[36]等。也有能够比对长read的序列比对算法，如SSAHA[14]、BLAT[37]、LAST[38]，但效率比较低，不能处理高通量数据。 专门针对第三代测序技术的序列比对算法中，有BLASR[24]、rHAT[16]等，提出的新算法数量较少，仍在不断研究当中，具有较大的研究空间和改进余地。
标签：参考,read,测序,基因组,哈希,序列,alignment From： https://www.cnblogs.com/wangprince2017/p/17903850.html