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

摘要：

生物序列的k-mer频次统计是生物信息处理中一个非常基础且重要的问题.本文针对多序列在对齐模式下，不同偏移处一段长度范围内的k-mer频次统计问题进行了研究.提出了一种逆向遍历k-mer计数算法BTKC.该算法能够充分利用长度的k-mer统计信息，快速得到长度的k-mer统计信息，从而避免了统计任意长度的k-mer频次信息时都需要对所有序列进行遍历.算法的时间复杂度分析及实验结果表明，相比于传统的前向遍历 FTKC算法， BTKC算法性能提升非常明显，且其时间复杂度与k-mer长度的变化范围无关，非常适合于在k-mer长度变化范围较大的情况下使用.

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

分类号：TP3;TN9

资助基金：国家自然科学基金60970085

在线出版日期：2014-05-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：121-124,158