###

DOI:

计算机系统应用英文版:2014,23(4):121-124,158

View/Add Comment 过刊浏览高级检索 HTML

←前一篇 | 后一篇→

码上扫一扫！

下载全文

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

张鑫鑫^1,2, 陈波^1,2, 何继凌¹, 徐云^1,2

(1.中国科学技术大学计算机科学与技术学院, 合肥 230027;2.安徽省高性能计算重点实验室, 合肥 230027)

Algorithms for Biological Sequence K-mer Frequency Counting Problem

ZHANG Xin-Xin^1,2, CHEN Bo^1,2, HE Ji-Ling¹, XU Yun^1,2

(1.School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China;2.Key Laboratory of High Performance Computing of Anhui Province, Hefei 230027, China)

摘要

图/表

参考文献

相似文献

本文已被：浏览 2209次下载 7544次
Received:August 29, 2013 Revised:September 26, 2013

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

中文关键词: 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.

keywords: k-mer k-mer counting frequency statistic backward traverse biological sequence processing

文章编号： 中图分类号： 文献标志码：

基金项目:国家自然科学基金（60970085）

Author Name	Affiliation
ZHANG Xin-Xin	School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China Key Laboratory of High Performance Computing of Anhui Province, Hefei 230027, China
CHEN Bo	School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China Key Laboratory of High Performance Computing of Anhui Province, Hefei 230027, China
HE Ji-Ling	School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China
XU Yun	School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China Key Laboratory of High Performance Computing of Anhui Province, Hefei 230027, China

Author Name	Affiliation
ZHANG Xin-Xin	School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China Key Laboratory of High Performance Computing of Anhui Province, Hefei 230027, China
CHEN Bo	School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China Key Laboratory of High Performance Computing of Anhui Province, Hefei 230027, China
HE Ji-Ling	School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China
XU Yun	School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China Key Laboratory of High Performance Computing of Anhui Province, Hefei 230027, China

引用文本：
张鑫鑫,陈波,何继凌,徐云.生物序列数据K-mer频次统计问题的算法.计算机系统应用,2014,23(4):121-124,158
ZHANG Xin-Xin,CHEN Bo,HE Ji-Ling,XU Yun.Algorithms for Biological Sequence K-mer Frequency Counting Problem.COMPUTER SYSTEMS APPLICATIONS,2014,23(4):121-124,158