基于区域过滤的测序序列比对算法研究

Study on the alignment algorithm for sequencing based on region filtering

随着二代测序平台的发展,二代测序技术可短时间产生数以千万计长度在100位点左右的测序片段数据(read),如何快速、准确地将这些read比对到参考基因组上成为测序序列比对算法的严峻挑战。传统测序比对算法大多是使用种子进行细粒度过滤的方法,种子候选位置较多,造成算法验证时间过大。提出一种基于区域的粗粒度过滤方法,与细粒度过滤方法相结合来提高过滤效果,以提升测序序列比对算法处理速度,并将此过滤方法应用到找全比对Bit Mapper算法中。在线虫基因组和人类基因组上的实验结果表明,融合了区域过滤方法后的算法时间和过滤效果均有明显提升。

With the continuous development of the second-generation DNA sequencing platform,the second-generation DNA sequencing technique can generate hundreds of thousands of sequencing fragment data（ reads）,whose length is about 100 points,in a short time. How to quickly and accurately compare these reads to the reference genome has became a serious challenge for the DNA sequencing sequence alignment tasks. Most traditional alignment algorithms are based on the seed for fine-grained filtering. As there are a lot of candidate positions for the seeds,the dynamic algorithm used to verify is always time consuming. In this paper,a region-based coarse-grained filtering method is proposed,which is combined with the fine-grained filtering method to improve the filtering effect,so as to improve the processing speed of the sequencing sequence alignment algorithms. We test the method on the elegans genome and human genome. The results showed that the method increased the filtering effect and improved Bit Mapper＇s efficiency.