下一代测序技术(也可称为大规模并行测序)允许人们在低成本条件下以惊人的吞吐量累积获得海量核酸序列,并提供更短的读数。吞吐量的大量增加和序列读数的减小产生的代价是短读的准确性显著低于传统的测序手段,同时使短读序列和参考序列的匹配在计算速度和精准度上产生了巨大挑战,导致数据转换为可用信息的计算时间变得更长;另外,海量数据也使计算机有限的内存资源相形见绌。短读序列映射过程中数据规模巨大,而目前已经引入的各类索引技术无法高效的利用有限的内存资源,内存占用率较高。对此本文提出了一个新颖的索引数据结构—精简(稀疏)哈希索引数据结构,应用于短读序列匹配来缓解此问题。该数据结构是经典Q-gram索引的变种,通过参数设置决定内存使用率,如对于人类参考基因组内存占用可减少至经典哈希的1/k。同时,实现了一种高效的并行构造方法。另外,短读序列映射过程的时间占了基因数据分析总时间的相当大一部分。针对下一代测序技术吞吐量大量增加导致的短读序列匹配计算速度减慢和匹配精度降低的问题,本文基于新提出的精简哈希索引结构设计了两个选种算法一分组选种和可变长度选种,用于过滤策略中以减少校验次数,从算法层面来提升计算速度。在此基础上进一步设计了一个快速高效的短读序列完全匹配器—FEM(Fast and Efficient read Mapper),FEM可以返回在给定编辑距离阈值内短读序列在参考基因组上的所有映射位置。FEM采用了多线程进行数据处理,设计了负载均衡模式以充分利用计算资源,并在算法细节上采用SIMD指令集实现,从体系结构方面进行计算优化。本文实验结果表明FEM是可扩展的,并且在处理速度和内存占用两方面,性能要优于其他目前最前沿的完全匹配器。内存占用方面,精简哈希索引的内存占用率是经典索引的1/k;而处理速度方面,相较于Masai,FEM使用单线程时,要快5倍,而使用多线程能够快两个数量级。还有,FEM 比BitMapper快大约3倍,而和BitMapper2和Hobbes3相比也有快一个数量级的加速比。