一种基于“基因表达谱”的并行聚类算法

跨物种的生物序列比较已经被广泛应用于基因功能预测,而越来越多的实验表明序列相似性并不足以保证基因功能相似.为了精确确定基因功能,不仅需要考虑序列性质,还需探索基因表达信息的特性,因为基因表达的改变往往伴随着基因功能的改变.通过聚类分析基因表达谱,可以直观判断协同表达基因及其规律,这是考察基因功能的重要一步.由于生物组织基因表达的复杂性,以及识别表达的microarray技术和理念的不断更新,表达数据的规模也呈指数规律递增,聚类分析遭遇了巨大瓶颈——过高的时空复杂度.根据“基因表达谱”的数据特征,对处理表达谱数据的分层聚类提出了一种并行分层聚类算法——PHCA,主要解决了并行设计的负载平衡问题,并实现了MPI平台的并行程序设计.并行程序性能分析表明,PHCA算法较大幅度降低了分层聚类算法的时空复杂度.

“基因电脑克隆”软件SiClone的并行优化研究与实现

生物信息学中,发现、鉴别新基因是承上启下的一步,它既承接了过往如“基因组测序”的工作,又是未来“后基因时代”研究的基石．“基因电脑克隆”是利用计算手段发现、鉴别新基因的方法,SiClone软件实现了“基因电脑克隆”功能．本文对SiClone软件操作的数据库提出并行处理方案,并详述了基于MPI(message passing interface)平台实现的并行优化版本PSiClone．根据已得到的EST数据库,展示了软件并行版PSiClone的运行性能,试验数据库EST序列条数仅仅是NCBI(The National Center for Biotechnology Information)dbEST庞大数据库的很小部分,这也暗示我们软件的并行工作对于大数据库的比较和运算将更有应用前景．

分子空间结构比较方法优化与点部署的并行实现

分子空间结构相似性比较的指标函数可以定量地描述两个分子空间结构相似性大小,但难题在于如何确定分子初始相对位置,以保证得到全局最优叠合.由于以往都是利用程序随机生成初始相对位置,所以没有规则也不确定.为保证得到全局最优叠合,需要大量的初始相对位置优化计算.利用“均匀设计”的实验设计手段,在空间规则地筛选部署分子初始相对位置,使其具有代表性和均匀分布性,这样只需少数确定数目的初始相对位置,便可以稳定地得到指标函数的全局最优解.而后利用并行处理方法,把初始相对位置集合部署在Np个处理器上同时工作,大幅度地减少了运行时间,并输出与串行执行相同的运算结果.

超大规模序列比对计算的并行优化

针对生物信息学研究中的超大规模序列比对计算问题进行了研究,解决了现有的e-PCR软件包在处理小麦基因引物扩增比对任务中存在的内存瓶颈、I/O瓶颈和计算时间瓶颈问题,利用数据和任务分割的基本方法,使其最关键的引物与模板的比对计算能够大规模并行,进而采用基于主从通信模式的MPI通信框架进行编程实现,并从任务的缩减、负载平衡、容错和多作业并发等方面进行了优化,最终在百万亿次超级计算机上顺利实现了千核级大规模并行计算,在数十日内即可完成原本预期需要数年的小麦序列扩增比对计算。

Motif识别算法简介及软件性能研究

Motif在转录和后转录水平的基因表达调控中起着重要的作用。目前,识别Motif的算法和相应的软件已有不少,但是却鲜有对各种算法及软件性能共同评测的研究和报告。介绍了算法的分类以及三种常见的Mo-tif识别算法W ordup,MM和G ibbs采样,并对A lignACE,MEME,MotifSampler,W eeder等13种Motif寻找软件进行性能比较分析。通过生物学意义的研究和性能比较结果可以得出:由于唯有W eeder算法考虑了Motif保守核心位置,因而它在各种软件中识别效果较好;大部分算法只考虑简单而且短的Motif,所以各种软件对酵母菌这种单细胞生物的Motif识别性能比多细胞生物要高。

基于新测序技术的比对与组装算法

针对新型超高通量测序仪Solexa测序仪所产生的测序片段read的比对与组装问题,提出一种短序列比对与组装算法SRMA,采用对参考序列进行hash的方法,将测序片段read分3段快速、准确地定位于参考序列,对不能定位的read采取从头(Denovo)组装的方法进行组装。测试结果表明SRMA算法具有较高的性能和敏感度,以及良好的应用前景。

mRNA可变剪接问题的并行化研究

对mRNA可变剪接问题进行了并行化分析和研究,解决了原AltSplice程序中Nbest参数选取欠合理的问题,结合实验实现了基于MPI平台的并行AltSplice版本MPI_AltSplice,并在5万亿次的联想深腾6800高性能计算机上获得了较好的运行性能。

基于CUDA的蛋白质翻译后修饰鉴定MS-Alignment算法加速研究

对MS-Alignment算法进行分析得出该算法很难满足大规模数据对鉴定速度的要求,而且具有的一个特点是相同的任务在不同的数据上重复计算,为数据划分提供了基础。基于CUDA编程模型使用图形处理器（GPU）对步骤数据库检索及候选肽段生成进行加速优化,设计了该步骤在单GPU上的实现方法。测试结果表明,此方法平均加速比为30倍以上,效果良好,可以满足蛋白质翻译后修饰鉴定中大规模数据快速计算的需求。

InsPecT的2种并行优化方案

InsPecT软件能通过盲搜索对蛋白质翻译后修饰进行鉴定,但其计算时间和复杂度较高。针对该问题分别采用对等模式和主从模式实现2种并行优化方案。比较结果表明,以主从模式并行的InsPecT软件通过动态数据分配和主从处理器间的及时响应,维持了更优的负载平衡,其加速效果较明显。

一种Tiling Array信号识别流程的并行优化

针对一种非常有效的信号识别算法——滑窗法(sliding window,SW),在其嵌入的串行信号识别流程基础上提出并行处理方案,并基于MPI(message passing interface)平台实现并行优化版本。这在基因芯片研究领域是个崭新的思路。最后,根据公共数据Affymetrix(2005) Tiling Array,展示SW并行流程的运行性能。实验结果表明,信号识别流程的并行化对大规模的数据运算非常有效且十分必要。

TilingArray技术与应用研究进展

Tiling Array实验技术是从传统的微阵列(microarray)基因芯片技术发展而来,在Tiling Array新技术产生发展的5年间,它已经成为了全基因组生物信息挖掘的主要工具,其高密度、高通量的特性使人们可以从全基因组水平考察生命过程和探索生命奥秘.对Tiling Array技术和应用研究最新进展进行了较为详尽的描述,其中包括Tiling Array技术概述、Tiling Array应用研究、Tiling Array重要的实验和发现以及对这些发现做出所有可能性的预测和解释.除此之外,对Tiling Array表达信号识别算法进行了简明的概述,并对其中3种具有典型意义的算法给出了评价和比较.

隔离迁移(Isolation with Migration)模型数值计算的并行实现

在群体遗传学和分子生态学研究中,种群的分化分析是一个重要的内容。IM(Isolation with Migration)模型以DNA序列数据为基础同时评估两个种群分化过程中分化时间和迁移概率。IM模型能够模拟许多真实世界中一个种群分行为两个种群的现象。IM模型应用MCMC(Markov Chain Monte Carlo)方法进行参数的推断。然而马尔科夫链需要经过漫长的时间才能达到一个稳定的概率分布,并且参数推断所需要的空间可能超过一个计算机的内存。本文利用MPI(Message Passing Interface)实现了基于数据并行的IM模型,在减少单个计算机内存使用和总的运行时间方面都有很好的效果。

四种肿瘤体细胞单核苷酸突变检测方法的比较

随着高通量测序成本的不断降低,基于DNA测序技术的肿瘤基因组研究已经成为揭示肿瘤分子机制的主流方法,并在临床诊断和治疗中逐渐得到应用。肿瘤体细胞单核苷酸突变变异(single nucleotide variant,SNV)作为最简单的一种基因变异类型,其检测会受到家系多态性、肿瘤异质性、测序和分析误差等多个因素的影响,从而导致一些假阳性的结果。目前,已有一些基于肿瘤基因组测序数据的体细胞SNV检测软件,如Varscan2,Mutect2,Strelka,Somatic Sniper等。本文选取四种典型的检测方法,对每种方法的检测原理进行研究,并使用ICGC-TCGA提供的全基因组数据,对上述四种变异检测软件进行测试。参照每种方法的分析流程,获得每种方法识别的候选变异位点集,并与真实的变异位点集合进行比较,分析每种算法的优缺点,从而为研究人员使用这些方法提供指导。

InsPecT的千核并行及优化

蛋白质翻译后修饰(PTMs)在复杂的生命过程中起到极其重要的调控作用,对蛋白质翻译后修饰的研究是对蛋白质结构及其功能分析的深入,也是当前蛋白质组学的重要方向。InsPecT软件由于具备盲搜索功能,在蛋白质翻译后修饰鉴定领域备受关注,但极高的计算复杂度是阻碍其广泛应用的主要障碍。本文对InsPecT软件进行并行化,并在千核环境下进行测试;此外,还在负载平衡方面和GPU加速方面进行优化。结果显示,并行效率突出,加速效果显著。

蛋白质序列及其翻译后修饰鉴定的盲搜索算法评价

蛋白质翻译后修饰鉴定是计算蛋白质科学的重要研究方向,研发速度快和精度高的鉴定算法及软件,是该方向的一个主要问题。本文回顾了蛋白质翻译后修饰鉴定的各类算法,并主要对蛋白质序列及其翻译后修饰鉴定的盲搜索算法和软件进行研究。通过对具有代表性的两个盲搜索软件InsPecT和SIMS,以及限定性搜索软件pFind的对比分析,对盲搜索算法在蛋白质序列及其翻译后修饰方面的瓶颈。