导向定位测序数据的甲基化序列比对算法优化

Optimization of Methylation Sequences Alignment Algorithm Based on GPS Data

导向定位测序(GPS)是一种全基因组DNA甲基化检测的新测序技术,产生的测序数据具有成本低、没有序列偏好等优势.目前,甲基化分析中最重要的一步是将其测序产生的序列比对到参考基因组上.但是,现有导向定位测序的方法使用Smith-Waterman进行局部序列比对,时间消耗过大且容易对序列比对位置产生误判.因此,提出一种导向定位测序数据的改进比对算法,该算法利用其双端测序的优势,先用甲基化序列端数据进行序列比对,对多位置匹配的序列再利用常规数据端数据进行比对位置确定.实验结果表明:本文方法和现有方法的准确率相当,而具有更高的唯一比对比率,时间性能有3倍以上的提升.

Guide Positioning Sequencing(GPS) is a novel method for genome-wide DNA methylation detection. The generated sequencing data has the advantages of low detection cost and no sequence preference. At present, the most important step in methylation analysis is to align the sequences to the reference genome. However, the existing method uses Smith-Waterman for local sequence alignment, which takes too much time and affects the mapping efficiency.Therefore, a new alignment algorithm for the GPS data is proposed. The algorithm uses the advantages of paired-end sequencing to determine the alignment positions. The methylation sequences are first aligned to the reference genome, and then corresponding regular sequences are used to determine the final positions. The experimental results show that compared with the existing method, the method presented in this paper has a high mapping efficiency with comparable accuracy and the time performance improved by more than 3 times.