论文部分内容阅读
基因数据分析是当前的研究热点,倍受机器学习、数据挖掘研究者的关注。基因读段定位是基因数据分析的关键环节,而基因聚类则是基因功能分析的重要途径,是生物学家寻找未知基因功能的重要手段,受到研究者的广泛关注。随着新一代测序技术的飞速发展,基因读段数据海量增长,导致传统的串行读段定位算法不再适用,效率低。同时,直接将现有的串行基因聚类算法应用于大规模基因表达数据同样存在效率低的问题。为此,如何设计高效的基因读段定位并行算法和基因聚类并行算法成为本文的关键内容。MapReduce并行技术作为主流的并行技术之一,在学界和产业界得到广泛的认同。本文侧重运用MapReduce技术对基因读段定位和基因聚类的并行化进行了深入的研究,主要工作如下：1.提出了基于MapReduce的基因读段定位算法(PSeqMap和PJuncSeqMap)。 PSeqMap算法将MapReduce和SeqMap软件中基于空位种子的读段定位算法结合,实现并行不跨越剪切位读段定位算法；PJuncSeqMap算法对PSeqMap算法进行改进,将读段进行分割、匹配和拼接,实现并行跨越剪切位读段定位算法；PSeqMap算法和PJuncSeqMap算法都采用了一种负载平衡的解决方案,该方案使用随机抽样尝试执行的方法,检测可能负载较高的节点,并平均分配负载。在拟南芥菜基因数据集上进行了实验验证,实验结果表明该算法的有效性和高效性。2.提出了基于MapReduce的基因读段定位改进算法(MPJuncSeqMap)。该算法运用了Hadoop分布式缓存机制、融入了有效的生物信息、降低了PJuncSeqMap算法的时间复杂度,从而设计出基于MapReduce的基因读段定位改进算法。在拟南芥菜基因数据集上进行了实验验证,实验结果表明该算法能够在略微降低定位敏感度的情况下,进一步提高读段定位效率。3.提出了基于MapReduce的密度层次聚类算法(DisDHC)。该算法在MapReduce框架下,将每个基因数据子集利用密度层次聚类算法(DHC)进行聚类获得稀疏化的数据,在此基础上再次进行DHC聚类,从而设计出DisDHC算法。在酵母数据集(GAL)、酵母细胞周期数据集(Cellcycle)和入血清数据集(Serum)上进行了实验验证,实验结果表明该算法能够在保持原始聚类算法精度的前提下,有效提高聚类效率。