基于Bayes推断的基因芯片探针特异性估计模型

序列相似性计算是生物信息处理中的基本问题。针对基因芯片设计中的特异性评价问题,基于Bayes推断,建立了DNA序列快速估计算法,该算法不需要序列联配(alignment-free),性能好于广泛应用的相似性计算工具,可以大幅提高基因芯片设计性能。     

Power Adjusting Algorithm: A New Cross-Layer Power Saving Mechanism for Mobile Ad-Hoc Networks

Power saving is one of the key issues in Mobile Ad-Hoc Networks(MANETs).It can be realized in Medium Access Control(MAC) layer and network layer.However,previous attentions were mainly paid to MAC layer or network layer with the aim of improving the channel utilization by adopting variable-range transmission power control.In this paper we focus on the power saving in both MAC layer and network layer,and propose a Power Adjusting Algorithm(PAA).In the presence of host’s mobility,PAA is designed to conserve energy by adjusting the transmission power to maintain the route’s connectivity and restarting the route discovery periodically to find a new route with better energy efficiency dynamically.After analyzing the operations of PAA,we find that the length of route discovery restarting period is a critical argument which will affect power saving,and an energy consumption model is abstracted to find the optimal value of the restarting period by analyzing the energy consumption of this algorithm.PAA can handle the mobility of MANET by adjusting the transmission power and in the meantime save energy by restarting route discovery periodically to balance the energy consumption on route discovery and packet delivering.Simulation results show that,PAA saves nearly 40% energy compared with Dynamic Source Routing protocol when the maximum speed of mobile hosts is larger than 8m/s.     

一个大规模股市图交互式可视化分析系统

随着物联网、移动互联网、云计算以及各种数据自动采集技术的迅猛发展,许多领域迅速积累了大量具有图结构的可用数据。其中一个重要的图应用是股市图。如何分析股市图达到合理充分的投资决策支持一直是一个重要的课题。其中极大团(Maximal Clique)分析是分析股市图的一个重要方法。股市图的规模庞大,传统的极大团枚举算法仅仅罗列图中所有的极大团。但一个图中可以有指数级数量的极大团,而一支股票对应的点可以参与到任意多的极大团中。因此,传统的极大团枚举算法不能直接有效支持股市图分析。本文提出一个支持快速选择、自动分组及导航浏览三种股市图交互式可视化操作的大规模股市图分析系统。根据用户感兴趣的股市图节点,这三种股市图交互式可视化操作从股市图中快速枚举出与这些特定股票相关的极大团、查看这些特定股票之间的组合关系以及显示与这些特定股票相关的其他股票,是有效支持股市图分析的必要手段。同时基于对某些特定顶点或边相关的极大团枚举的需求,本文提出了从图中枚举出与特定顶点或边相关的极大团算法。我们使用真实数据验证了本文提出的算法的优越性。     

基于并行群体模拟退火算法的蛋白质折叠研究

蛋白质折叠研究对于揭示蛋白结构和功能关系,进而了解相关疾病的致病机理意义重大。蛋白质折叠已被证明是 NP-完全问题。本文针对蛋白质折叠研究中的能量最小化问题,提出了一种新的并行群体模拟退火算法（Parallel Group Simulated Annealing,PGSA）及其改进型算法（PGSA_1/K)。该算法使用了降温因子加速收敛精度,并采用 MPI 消息传递并行编程技术加快蛋白质结构空间搜索以及能量最小化寻找速度。以 Met_Enkephalin 蛋白为对象的计算机模拟仿真结果表明,我们提出的算法及其改进型有很好的扩展性,可以高效搜索蛋白结构空间,从而找到相关蛋白的最小能量结构。     

基于De Bruijn图的De Novo序列组装软件性能分析

随着新一代测序技术的发展,一些新的全基因组组装算法应运而生,特别是针对第三代高通量测序仪产生的海量短序列的组装软件被不断开发出来,这些组装软件渐渐走向市场。但是,由于这些组装软件的适用性和其性能的差别,选择一款性能优良的组装工具或者开发并行高吞吐的组装工具成为了当前面临的一大难题。本文选取基于 De Bruijn 图算法开发的 4 款 De Novo 组装的软件（Velvet、SOAPdenovo、IDBA、ABySS）对 4 种物种的基因组的模拟数据进行测试,并从软件的算法、组装性能和组装质量 3 个方面分析这 4 个软件的性能,同时根据其算法特点推断影响这些软件性能的关键因素,并给出软件的使用建议以及开发并行序列组装工具来组装超大规模的基因数据应该注意的问题。     

面向多用户的集群资源部署策略

集群系统中面向多用户的资源部署策略优先考虑的是资源能够在不同用户之间进行公平分配,同时实现用户之间的资源共享。为了充分利用集群资源,用户以一定的原则通常是采用权重比的方式共用集群资源。该策略并不关心每个用户所获取的资源总量,只关心用户所获取的资源比例是否总是符合原则,这样可以保证空闲资源总是能够被充分利用。该策略包括资源的定额分配和自主申请两部分,以满足用户的需求。同时提出了采用用户占用资源量与占用时间共同作为公平分配依据的策略,以适应更加复杂的情况。     

基于粗集边界域的快速约简算法

属性约简是粗糙集研究的核心内容之一。已有的大多数属性约简算法都是采用基于正域的贪心算法求决策表的代数约简。事实上,对于不一致决策表,代数约简改变了决策类族原有的Pawlak拓扑结构,造成决策类的不确定性扩大。为此,提出了一种新的基于粗集边界域的约简模型,它能够保持决策类族原有的Pawlak拓扑结构。依据新模型,提出了一种高效率的基于粗集边界域的属性约简算法。理论分析和实验表明,所提算法是有效可行的。     

高性能计算的智慧城市机遇与挑战

智慧城市、智慧地球是全球信息化浪潮的新发展阶段。作为支撑智慧城市深入发展和广泛应用的核心技术,高性能计算也面临着挑战和机遇。本文在分析智慧城市需求的基础上,把这些对高性能计算的挑战概括为大数计算、实时计算、效能计算和社会计算等四个方面,并简要介绍了中国科学院深圳先进技术研究院在这些方向上的布局及取得的进展。     

使用分布式De Bruijn图遍历基因拼接并行构建和化简

目前基因拼接软件中应用最广泛的技术是基于De Bruijn图的基因拼接算法,需要对长达数十亿BP长度的基因组测序数据进行处理.针对海量的基因测序数据,快速、高效和可扩展的基因拼接算法非常重要.虽然已出现一些并行拼接算法（如YAGA）开始研究这些问题,但是拼接过程中时间、空间消耗较大的构图和单链化简这两大步骤在海量数据的挑战下仍然是最主要的计算瓶颈.这是因为现有工作在处理这几个步骤时通常使用了并行的表排序（list ranking）,而该方法需要多次对De Bruijn图的海量顶点信息进行分布式的排序,产生了大量的计算节点间的通信.单链化简可由1次De Bruijn 图深度优先遍历完成而不再需要表排序,于是提出一种基于分布式海量图遍历方法对单链化简进行优化,极大地减少了处理器间的通信和计算节点之间的数据移动,因而取得较好的扩展性,其算法复杂度为O（g/p）,通信复杂度为O（g）,这里g为参考序列的长度,p为处理器的核数.当对E.coli和Yeast数据集进行测试,处理器的核数从8个增加到512个时,算法可以得到13倍和10倍的加速比;当对C.elegans和人类1号染色体（chr1）数据集进行测试,处理器的核数从32个增加到512个时,算法可以得到7倍和10倍的加速比.