生物序列数据K-mer频次统计问题的算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(60970085)


Algorithms for Biological Sequence K-mer Frequency Counting Problem
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    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频次统计问题的算法.计算机系统应用,2014,23(4):121-124,158

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2013-08-29
  • 最后修改日期:2013-09-26
  • 录用日期:
  • 在线发布日期: 2014-04-25
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号