论文部分内容阅读
随着近些年来测序技术的飞速发展,人类产生了海量的生物序列数据,亟需通过有效的计算手段进行分析和处理。而在众多的生物序列分析与处理问题中,生物序列数据的k-mer频次信息是一种非常关键且重要的序列特征,它在序列比对、序列拼接、序列聚类、模体发现等诸多的问题上得到了广泛的应用。面对大规模数据,k-mer频次统计的算法以及其可视化问题就显得至关重要,本文就围绕着这两个方面进行研究,其主要内容和贡献包括: (1) k-mer频次统计算法研究 按照k-mer频次的计数方式,该问题可以分为两类:全序列k-mer频次统计、序列间k-mer频次统计。对于全序列k-mer频次统计问题,本文先对有限内存和磁盘空间限制下的DSK算法进行了分析,该算法主要存在磁盘I/O开销过大。对于同样规模或更大规模的问题,云计算平台可以减少各节点的磁盘I/O开销,因此,我们对DSK算法进行了适用于MapReduce云计算框架下的并行化改造,提出了PDSK算法。理论分析及实验结果表明,PDSK算法能够对数据进行均匀划分,减小各个节点的磁盘I/O开销,提高全序列k-mer频次统计的效率。 对于序列间k-mer频次统计问题,通过对传统的基于前向遍历的FTKC算法进行改进,我们提出了新的基于逆向遍历的k-mer频次统计算法BTKC。该算法能够利用k+1长度的k-mer频次统计结果,推导出k长度的统计结果,从而避免了统计每一长度的k-mer频次结果时均需要对所有序列重新遍历。算法时间复杂度分析及实验结果表明,相比于传统FTKC算法,BTKC算法性能提升明显,非常适合于k-mer长度有一定连续变化范围的情况下使用。 (2) k-mer频次可视化软件的设计及应用 当前生物信息学的软件和应用中,一直缺乏一款专门对生物序列的k-mer频次信息进行多维度多层次的统计与分析的可视化软件,因而我们设计了专门针对生物序列数据k-mer及k-mer频次在横向和纵向进行可视化展示的软件。该软件包括序列下载、序列格式转换与解析、序列数据k-mer频次统计、k-mer频次可视化展示等功能。并提供了两个适用于该软件的典型应用,分别是模式串的查找与频次展示、扩展的序列Logo图生成。