生物序列数据K-mer频次统计问题的算法  

Algorithms for Biological Sequence K-mer Frequency Counting Problem

作　　者：张鑫鑫[1,2] 陈波[1,2] 何继凌[1] 徐云[1,2] 

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230027 [2]安徽省高性能计算重点实验室,合肥230027

出　　处：《计算机系统应用》2014年第4期121-124,158,共5页Computer Systems & Applications

基　　金：国家自然科学基金(60970085)

摘　　要：生物序列的k-mer频次统计是生物信息处理中一个非常基础且重要的问题.本文针对多序列在对齐模式下,不同偏移处一段长度范围内的k-mer频次统计问题进行了研究.提出了一种逆向遍历k-mer计数算法BTKC.该算法能够充分利用长度的k-mer统计信息,快速得到长度的k-mer统计信息,从而避免了统计任意长度的k-mer频次信息时都需要对所有序列进行遍历.算法的时间复杂度分析及实验结果表明,相比于传统的前向遍历FTKC算法,BTKC算法性能提升非常明显,且其时间复杂度与k-mer长度的变化范围无关,非常适合于在k-mer长度变化范围较大的情况下使用.K-mer counting of biological sequence is a fundamental and very important problem in biological information processing. This paper focuses on counting k-mers at each position of multiple sequences within aligned mode. We present a new backward traverse k-mer counting algorithm called BTKC. BTKC algorithm takes full advantage of the k＋1-mer’s statistic information to obtain k-mer’s statistic information quickly. Thus, it’s no need to traverse the whole sequences when counting each single k-mer. Both the algorithm’s time complexity and experiment results show that BTKC gets an obvious improvement compared with forward traverse k-mer counting algorithm FTKC, and its time complexity was found not to be realted with the range of k-mer length.

关 键 词：k-mer计数 频次统计 逆向遍历 生物信息处理 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]