基于Spark的基因短序列比对模型

针对生物信息分析中基因短序列比对任务计算耗时长的问题,采用Spark平台、RDD数据集以及分布式文件系统HDFS设计了一种分布式计算模型。采用分而治之的策略将庞大的计算任务分割为多个互不重叠的小任务在分布式集群上并行执行。通过基于位置偏移量等分的数据分区算法实现数据的分发;通过将基因短序列封装入RDD数据集的方法实现了短序列的逐条处理;通过将基因比对算法传入RDD的Map函数的方法实现了基因序列的比对。计算模型的实现使得串行比对算法在分布式集群上可扩展,并显著降低了计算耗时,计算结果可与后续的生物信息分析工作相兼容。实验结果证明计算模型具有较好的稳定性和可扩展性,在Spark集群上取得了优秀的加速比。     

一种基于极值思想的多序列联配求精算法

多序列联配（MSA）是一个NP问题，为了取得一个好的联配结果，常用渐进和迭代两种方法，但渐进方法不能调整早期的错误，迭代方法面临怎样跳出局部最优的问题。该文提出了一种新的求精方法，该方法基于极值遗传算法和挖掘策略。极值遗传算法基于极值组合元素，能够减少搜索空间。易于找到全局最优解。算法实现过程中，首先用挖掘算法挖掘出已知联配中的不良序列块，然后所有的不良序列块用极值遗传算法重新联配。当初始的序列是用渐进算法联配时，新的求精方法能调整早期的一些错误，充分结合渐进和迭代算法的优点。最后算法用来自于数据库BAliBASE中数据进行了验证。     

基于忆阻器的PIM结构实现深度卷积神经网络近似计算

忆阻器(memristor)能够将存储和计算的特性融合,可用于构建存储计算一体化的PIM(processing-in-memory)结构.但是,由于计算阵列以及结构映射方法的限制,基于忆阻器阵列的深度神经网络计算需要频繁的AD/DA转换以及大量的中间存储,导致了显著的能量和面积开销.提出了一种新型的基于忆阻器的深度卷积神经网络近似计算PIM结构,利用模拟忆阻器大大增加数据密度,并将卷积过程分解到不同形式的忆阻器阵列中分别计算,增加了数据并行性,减少了数据转换次数并消除了中间存储,从而实现了加速和节能.针对该结构中可能存在的精度损失,给出了相应的优化策略.对不同规模和深度的神经网络计算进行仿真实验评估,结果表明,在相同计算精度下,该结构可以最多降低90%以上的能耗,同时计算性能提升约90%.     

一种新的迭代渐进多序列比对算法

该文提出一种新的迭代渐进多序列比对算法IPMSA。该算法先用渐进方法进行多序列比对,然后通过迭代策略,利用上一轮多序列比对结果修正指导树,产生新一轮比对。重复这一过程,直到指导树不再发生变化或满足事先设定的迭代次数为止。以比对数据库BAliBASE中多蛋白质家族1idy为例,对IPMSA算法和ClustalW算法进行的比较研究表明,该算法能更有效地比对分歧较大的序列,并改进其系统发育树。     

生物序列搜索算法hmmsearch的加速技术

在FPGA平台实现细粒度并行的hmmsearch加速技术。采用数据预取、滑动窗口和数据传递等策略实现子处理单元的数据重用。在计算矩阵块内部实现流水线计算。加速器性能为3.59 GCUPS,与CPU相比,可获得接近235倍的加速效果。与目前FPGA上同性质最快的加速器相比,单PE可获得34%的性能提升。     

进化算法在DNA序列比对中的应用

在对序列比对结果进行分析的过程中，提出了基于生物进化思想的序列比对算法。该算法的出发点是在待比对序列中的不同位置插入空位，通过设计合理的遗传算子，在不断的进化过程中，使序列间具有最大的相似性。由于该算法的主要操作是比较、计数和移位，使得硬件实现具有可行性、简易性。测试结果表明了该算法的有效性。     

一种快速渐进式卷积神经网络结构搜索算法

手动设计卷积神经网络结构对专业性要求高、难度大。基于梯度可微的搜索快速高效,但这类方法存在深度鸿沟和稳定性较差的问题。提出一种结合渐进式搜索和贪心指标的快速渐进式结构搜索算法(FPNAS),通过渐进式扩展搜索阶段的结构,使得搜索阶段的网络结构逐渐接近评估阶段,避免深度鸿沟造成的影响。同时,通过运用贪心指标作为选边准则,增加搜索评估的相关性并提高搜索的稳定性。针对网络结构搜索算法消耗计算资源多的问题,提出渐进式划分数据集方法,通过分阶段不同比例的数据集划分来减少结构搜索的计算资源消耗。以准确率和搜索时间作为评价指标,将FPNAS与渐进式可微结构搜索算法和贪心搜索算法进行对比,实验结果表明,FPNAS搜索出的网络结构稳定性得到改进,搜索时间分别缩短0.19和0.14个GPU Days,在CIFAR-10数据集上精度最高达到97.7%。     

一种多序列比对分治算法DCA-ClustalW

多序列比对是生物信息学研究中最基本的一项内容,多序列比对的精确算法是一个NP-hard问题,一般研究者都侧重于设计多序列比对近似算法,最有代表性的近似算法是ClustalW;分而治之是一种重要的算法设计思想,它将复杂问题分割成更简单的子问题来解决,能有效提高算法效率。本文设计了一个DCA-ClustalW算法,对多序列比对问题,同时考虑从纵向和横向两个方面将复杂问题分割成简单易解的子问题,在BaliBase基准数据集上测试表明,该算法是可行的。     

一种多搜索策略的多生物序列比对自适应遗传算法

多生物序列比对是用来计算生物序列间相似性的重要工具，本文在引入熵来度量种群多样性的基础上，提出了一种多搜索策略的自适应遗传算法，其交叉和变异概率随着熵的变化进行自动调整，并且综合考虑了利用动态规划算法来设计遗传操作算子．实验结果表明，这个算法具有较强的全局搜索能力和局部搜索能力，并且能有效的克服未成熟收敛问题．     

一种求解布尔不可满足子式的局部搜索算法

解释布尔公式不可满足的原因在众多领域都具有非常重要的理论与应用价值,而不可满足子式能够为公式不可满足的原因提供精确的解释,帮助应用领域的自动化工具迅速定位错误,诊断问题失败的本质缘由。近年来涌现了许多基于SAT求解器DPLL回溯搜索过程的完全算法,但关于不完全方法提取不可满足子式的研究相对较少。因此,本文提出一种采用启发式局部搜索过程从公式的不可满足性证明中求解布尔不可满足子式的算法。该算法根据公式的消解规则通过局部搜索过程直接构造证明不可满足性的消解序列,并融合了布尔推理技术以提高搜索效率;而后通过一个递归过程遍历证明序列从而得到不可满足子式。通过实验与贪心遗传算法进行对比,结果表明本文提出的算法优于贪心遗传算法。     

基于网格的生物序列比对与分析系统

提出了一个基于网格的生物基因序列比对与分析平台BioSA,详细描述了BioSA系统的各个组成模块,通过各个模块的分工与合作,BioSA系统可以给计算密集型基因序列比对提供一个统一与可扩展的计算环境.使用网格平台中的Web Services技术、消息通知机制,序列比较分析与查询匹配也可以实现.BioSA不仅支持系统定义的序列比对和分析,而且支持用户定义的、远程的序列分析.通过对实际序列比对的案例实现,验证了BioSA系统的正确性与高效性.     

一种用于加速神经视觉识别的硬件架构

深度学习的广泛应用带来了视觉分析中许多类似人类认知任务的实现。HMAX 是基于视觉皮层的生物启发模型,已在多类物体识别中被证明优于标准计算机视觉方法。但是,由于神经形态算法的高复杂性,在边缘设备上实现 HMAX 模型仍然面临巨大挑战。已有研究表明,HMAX 的 S2 阶段是运行最耗时的阶段。该文提出了一种基于脉动阵列的新架构来加速 HAMX 模型的 S2 阶段。仿真结果表明,与基准模型相比,HMAX 模型最耗时的 S2 阶段执行时间平均减少了 14.65％、内存所需的带宽减少了 3.34 倍。     

深度神经架构搜索综述

深度学习在图像、语音、文本等多种模态的数据任务上取得了优异的效果.然而,针对特定任务,人工设计网络需要花费大量的时间,并且需要设计者具有一定水平的专业知识和设计经验.面对如今日趋复杂的网络架构,仅依靠人工进行设计变得越来越复杂.基于此,借助算法自动地对神经网络进行架构的搜索成为了研究热点.神经架构搜索的方法涉及3个方面：搜索空间、搜索策略、性能评估策略.通过搜索策略在搜索空间中选择一个网络架构,借助性能评估策略对该网络架构进行评估,并将结果反馈给搜索策略指导搜索策略选择更好的网络架构,通过不断迭代得到最优的网络架构.为了更好地为读者提供一个快速了解神经网络架构搜索方法的导航地图,从搜索空间、搜索策略和性能评估策略3个方面对现有典型的神经架构搜索方法进行了梳理,总结讨论了近年来常见的架构搜索方法,并分析了各种方法的优势和不足.     

基于遗传算法的多序列比对算法研究

本文使用遗传算法解决多序列比对问题,并进一步研究了各种遗传算子在比对过程中所起的作用,对算法进行了改进。最后实现了一个多序列比对程序,对实验结果进行分析。     

多核架构下计算凸壳的并行算法

改进了周培德的Z3-2算法,提出一种在多核架构下计算平面点集凸壳的并行算法。用“颜氏距离”来数字化平面上点与有向线段的位置关系,减少了计算次数和时间。进一步将原算法中比较耗时的两个过程分别在O(1)的时间复杂度内进行迭代分解,即当原问题规模大于给定阂值时,将原问题分解为若干个独立的子问题,若所得子问题的规模仍大于给定阂值,则再对子问题进行分解;所有子问题被加入并行任务组进行并行求解以充分利用多核处理器的并行计算资源。给出了算法的正确性说明,实验结果也表明本算法稳定高效。     

面向大学课程时间表的并行多视图搜索算法

针对大学课程时间表问题,提出一种基于改进迭代局部搜索的并行多视图搜索算法进行求解。依据课程时间表问题特性设计包含八种基础邻域的多邻域集,并根据提升速度比制定基邻域选择概率设置规则。在迭代局部搜索过程中,运用多视图学习策略对多个局部搜索步骤进行视图共享,及时调整搜索方向以提升搜索效率。通过并行计算思想对算法优化,提升多视图搜索的收敛速度。实验结果表明,提出的算法求解精度更佳,且具有优异的扩展性和并行效率。     

量子查找算法的发展与前瞻

量子查找算法是一种利用波的特性进行查找的新方法，它以量子位作为描述问题 的基本信息单位，为 NP-完全问题的解决提供了一种有效的途径。量子查找算法的主要特 点 是查找的高度并行性、非结构化查找和巨大的信息存储容量。该文介绍了量子查找的基 本思 想；综述了量子查找的典型实例及其广泛应用；分析了量子查找算法的特点及其与传 统算法 的关系；指出了量子计算目前存在的问题；最后对量子计算的发展前景进行展望。     

桌面网格计算平台在多序列比对算法中的运用

提出了一种多序列比对ClustalW算法并行化处理的新方法ParaClustalW,该方法使用桌面网格计算平台作为高性能编程环境和运行平台.分析了多序列比对算法在桌面网格平台上的任务划分方式、并行化策略和实现技术.ParaClustalW策略考虑到序列的数目与序列的长度等因素,实现任务划分的均衡性.经实验证明,Para...     

梅森素数并行求解算法的流式实现

本文以数论中的Lucas-Lehmer检验法为基础,提出了梅森素数并行求解算法在FT64流处理器上的流式实现,并通过重设流记录的大小对程序进行了优化。评测数据表明,在FT64上运行该应用的时间平均比1．5GHz Itanium2快2．5倍。本文为梅森素数求解问题寻找了一条可行的加速方法,同时证实了流体系结构在高性能计算领域的极大潜力。本文提出的流式算法以及各种优化手段,对于其他科学计算领域中的计算密集型问题在流体系结构上的映射有极大的借鉴意义。     

Neighborhood Search Based Improved Bat Algorithm for Web Service Composition

Web services are provided as reusable software components in the services-oriented architecture. More complicated composite services can be combined from these components to satisfy the user requirements represented as a workflow with specified Quality of Service (QoS) limitations. The workflow consists of tasks where many services can be considered for each task. Searching for optimal services combination and optimizing the overall QoS limitations is a Non-deterministic Polynomial (NP)-hard problem. This work focuses on the Web Service Composition (WSC) problem and proposes a new service composition algorithm based on the micro-bats behavior while hunting the prey. The proposed algorithm determines the optimal combination of the web services to satisfy the complex user needs. It also addresses the Bat Algorithm (BA) shortcomings, such as the tradeoff among exploration and exploitation searching mechanisms, local optima, and convergence rate. The proposed enhancement includes a developed cooperative and adaptive population initialization mechanism. An elitist mechanism is utilized to address the BA convergence rate. The tradeoff between exploration and exploitation is handled through a neighborhood search mechanism. Several benchmark datasets are selected to evaluate the proposed bat algorithm’s performance. The simulation results are estimated using the average fitness value, the standard deviation of the fitness value, and an average of the execution time and compared with four bat-inspired algorithms. It is observed from the simulation results that introduced enhancement obtains significant results.