基于矩阵运算加速的改进社区发现遗传算法

社区发现算法是复杂网络领域的重要研究工具,然而传统的社区发现遗传算法在大规模网络下存在初始种群质量不佳和运行效率低下的问题。为此,本文提出一种基于矩阵运算加速的改进社区发现遗传算法。针对初始种群质量不佳的问题,提出一种新的初始化算子,采用闭包系数有偏向地选择节点构建高质量初始社区;针对计算效率低下的问题,基于矩阵运算重构了传统社区发现遗传算法各个算子,使得算法能使用GPU加速,提升计算效率。仿真实验结果表明,在不同规模的真实网络和LFR合成网络下,本文算法既能保证良好的划分精度,又展现出较其他主流同类算法更高的计算效率。     

基于投影位置的序列模式挖掘算法

针对PrefixSpan算法在产生频繁序列模式(特别是挖掘密数据集和长序列模式)时会产生大量的投影数据库,使得算法性能下降的问题,提出一种基于投影位置的序列模式挖掘(PSPM)算法.该算法利用Apriori性质舍弃对非频繁项存储,节省了存储空间和扫描不可能出现序列的挖掘时间;在递归挖掘过程中,利用投影位置表直接定位投影序列位置进行挖掘局部频繁项,避免了构造投影数据库,从而提高执行效率.实验结果表明:与PrefixSpan(with pseudo-pro)算法相比,PSPM具有更好的执行效率和可伸缩性.     

基于K-spectrum的下一代测序数据的纠错算法分析

【目的】对现有的下一代测序(Next Generation Sequencing,NGS)纠错算法和工具进行分析,提出基于Hadoop平台的纠错算法,以解决大数据处理中计算机内存不足和运行时间长的问题,提升纠错性能。【方法】使用特定的数据对现有的基于K-spectrum的纠错算法进行测试,对各纠错工具的运行时间、内存峰值和纠错结果进行比较来衡量纠错工具的性能。在此基础上提出Hadoop分布式并行纠错算法(Parallel algorithm),并与串行程序、Lighter和Racer进行比较,分析分布式并行实现的可行性。【结果】现有的基于Kspectrum的纠错工具普遍存在较大的内存消耗现象,其中Racer和Sga的纠错效果较好。而Hadoop分布式并行纠错算法对计算机单机内存的消耗较低,当数据量超过一定值时,并行分布式程序的运算时间比串行单机程序明显减少。【结论】本研究提出的Hadoop分布式并行纠错算法不仅降低了内存消耗,而且提高了运算性能,更有利于大规模基因数据的分析处理。     

基于DNA结合特异性权重矩阵的TAL效应物靶标预测

计算预测出TAL效应物的候选靶标有助于高效地确定TAL效应物的靶基因,进而阐明TAL效应物的生物学功能,但是目前在TAL效应物靶标计算预测方面的研究仍然很少.为了设计出预测TAL效应物靶标的有效算法,基于TAL效应物的已知靶标数据,构建了TAL效应物靶点的RVD-核苷酸关联矩阵,并将RVD-核苷酸关联矩阵归一化成RVD特异性概率矩阵,为靶标预测构造新的打分函数.实验结果表明,改进的TAL效应物靶标预测算法对大部分已知靶标预测的打分排名比已有算法更靠前,并且结合基因表达数据可以预测出TAL效应物的新的候选靶标.