基于串行FastLSA的并行算法

提出了一种基于串行Fast LSA算法的两个序列比对的并行算法。主要是对海量级的序列比对,目的是减少串行Fast LSA算法的时间和空间的复杂度。实验结果表明该算法完全可以并行化,而且空间复杂度降到线性空间。     

GPU加速的生物序列比对

为了精确高效地进行生物序列比对,提出一种GPU加速的Smith-Waterman算法.该算法使用菱形数据布局以更充分地利用GPU的并行处理能力;使用查询串分批处理技术来支持上百兆规模的序列比对;同时引入树形算法,以优化最大匹配值的计算.将该算法在一块NVIDIA GeForce GTX285显卡上实现,并使用多组不同规模的生物序列进行了比对实验.实验结果表明,与CPU上的串行算法相比,采用文中算法最高可获得120倍以上的性能提升.     

多序列比对软件T-Coffee的并行化设计与实现

T-Coffee是广泛用于核酸或氨基酸的多序列比对工具.它通过生成基本信息库,扩展库,生成指导树,渐近式比对四个阶段来完成多序列的比对.分析了T-Coffee串行算法及其复杂度,并提出了基于SMP机的并行化版本.目标是使其充分并行化,实验结果表明它明显的提高了性能,并得到了很好的相对加速比.     

带变异算子粒子群算法在多序列比对中的应用

多序列比对(Multiple Sequence Alignment)是进行生物序列分析的最基本任务之一。在对已有的多序列比对算法进行对比分析的基础上,提出了一种新的多序列比对优化算法—带变异算子粒子群多序列比对算法。带变异算子的粒子群算法提高了原有算法跳出局部收敛的能力,将其应用于多序列比对问题中,提高了已有的基于粒子群算法的多序列比对方法的性能,拓展了粒子群算法在多序列比对研究领域中的应用。实验证明,带变异算子粒子群多序列比对算法是有效、可行的。     

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

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

多序列比对问题的粒子群优化算法求解

文章提出了一新的算法,利用粒子群优化算法求解多序列比对的问题,这是粒子群优化算法在生物信息学方面的一个新的应用。文章从粒子群算法的原理和多序列比对问题模型入手,来提出怎样改造粒子群优化算法使其可以解决多序列比对问题,最后给出利用粒子群优化算法求解多序列比对的算法,及其测试结果。     

基于改进的蚁群算法的多序列比对

该文将蚁群算法进行了改进,将其应用于多序列比对,只根据信息素的强度对序列比对进行信息素强度的局部和全局动态更新,在避免了多序列比对容易陷入局部最优解的前提下,提高了收敛速度。同时,本算法应用在多序列比对中的最大优势是减少了传统算法在多序列比对问题中的生成系统树的步骤,减少了多序列比对过程的复杂度,在没有降低比对结果精确度的同时,提高了比对效率。     

基于迭代渐进多序列比对算法研究

提出一种新的迭代渐进多序列比对算法IPMSA。采用公共多序列比对数据库BAIiBASE中142组蛋白质序列作为比对测试数据,并与ClustalW进行比较。比对结果的统计分析表明,IPMSA算法的比对准确率高于ClustalW。     

基于渐进蚁群算法的DNA多序列比对

DNA多序列比对是生物信息学中的最重要的任务之一。本文针对多序列比对的特点,提出一种渐进蚁群算法,即将渐进比对算法和蚁群算法相结合。在渐进蚁群算法中,既能克服蚁群算法易于陷入局部最优解、收敛速度慢的特点,又能充分发挥渐进比对算法的优点。     

多序列星比对算法的改进及其在Spark中的并行化研究

多序列星比对算法在确定中心序列时需要计算任意两个输入序列的距离及分数,其较高的时间复杂度 耗费了大量时间,因此提出了通过综合计算每个序列产生的k-mers及各个k-mer在各序列中出现的次数来确定k-mers的拼接选择,由k-mers进行拼接从而 得到中心序列。进而,在双序列比对过程中采用搜索两个序列最大相似子串的思想,改进的星比对算法的精度在一定程度上得到了明显提升。接着, 将改进的星比对算法在Spark中进行并行化设计与实现。采用Spark的Yarn-Client运行模式,对正常人线粒体的多组数据进行实验,分析了算法性能上的不足及改进方向。     

A parallel algorithm for computing Fourier transforms on the stargraph

The n-star graph, denoted by S_n, is one of the graph networks that have been recently proposed as attractive alternatives to the n-cube topology for interconnecting processors in parallel computers. We present a parallel algorithm for the computation of the Fourier transform on the star graph. The algorithm requires O(n² ) multiply-add steps for an input sequence of n! elements, and is hence cost-optimal with respect to the sequential algorithm on which it is based. This is believed to be the first algorithm, and the only one to date, for the computation of the Fourier transform on the star graph     

Matrix decomposition on the star graph

We present and evaluate, for the first time, a parallel algorithm for solving the LU decomposition problem on the star graph. The proposed parallel algorithm is of O(N³/n!) computation complexity and uses O(Nn) communication time to decompose a matrix of order N on a star graph of dimension n, where N⩾(n-1)!. The incurred communication time is better than the best known results for the hypercube, O(Nlogn!), and the mesh, O(N√n!), each with approximately n! nodes. The proposed parallel algorithm takes advantage of the attractive topological qualities of the star graph in order to reduce the communication time involved in tasks such as pivoting, row/column interchanges, and pivot row and multipliers column broadcasts     

基于隐马尔可夫模型和免疫粒子群优化的多序列比对算法

序列的多重比对是生物序列分析研究中的一个重要内容．基于免疫系统的疫苗接种和受体编辑模型,结合粒子群优化方法提出了一种免疫粒子群优化算法,将该算法用于隐马尔可夫模型的学习过程,进而构建了一种基于隐马尔可夫模型和免疫粒子群优化的多序列比对算法,从BAliBASE比对数据库中选取了一些比对例子进行了模拟计算,并与Baum-Welch算法进行了比较．结果表明,所提出的方法不仅提高了比对的准确程度,而且缩减了比对所花费的时间。     

基于多策略人工蜂群的多序列比对算法

多序列比对是生物信息学中最重要和最具挑战性的任务之一.基于多序列比对是NP 完全组合优化问题,引入Tent 混沌初始化种群策略、不同蜂种的邻域搜索策略和锦标赛选择策略等,提出一种基于多策略人工蜂群的多序列比对算法.该算法应用Tent混沌初始化种群策略以使初始个体多样化并获取较好初始解;针对不同蜂种的特性设计不同的邻域搜索策略以平衡算法的全局探索和局部开发能力.同时引入序列比对的蜜源编码方法以适应多序列比对的离散性.实验结果表明,所提出算法的鲁棒性较强,能获取较好的比对性能和生物特性.     

星象跟踪的实时性改进

针对弹道导弹星象跟踪实时性问题,提出星象跟踪的实时性改进的一种新方法。该方法根据星象跟踪/预测方法与跟踪模式特点,首先,建立了基于统一存储的星表模式库,并采用k-vector作为检索方法,以提高检索速度;其次,为实时生成局域星象信息集合,提出了并行多维检索的方法,以节省提取星像信息的时间;最后,进行算法性能分析。仿真实验结果表明:该算法能够大大地提高星象跟踪的实时性,提高导弹命中精度。     

Solving the team orienteering problem using effective multi-start simulated annealing

The team orienteering problem (TOP) is known as an NP-complete problem. A set of locations is provided and a score is collected from the visit to each location. The objective is to maximize the total score given a fixed time limit for each available tour. Given the computational complexity of this problem, a multi-start simulated annealing (MSA) algorithm which combines a simulated annealing (SA) based meta-heuristic with a multi-start hill climbing strategy is proposed to solve TOP. To verify the developed MSA algorithm, computational experiments are performed on well-known benchmark problems involving numbers of locations ranging between 42 and 102. The experimental results demonstrate that the multi-start hill climbing strategy can significantly improve the performance of the traditional single-start SA. Meanwhile, the proposed MSA algorithm is highly effective compared to the state-of-the-art meta-heuristics on the same benchmark instances. The proposed MSA algorithm obtained 135 best solutions to the 157 benchmark problems, including five new best solutions. In terms of both solution quality and computational expense, this study successfully constructs a high-performance method for solving this challenging problem.     

Multiple biological sequence alignment in heterogeneous multicore clusters with user-selectable task allocation policies

Multiple Sequence Alignment (MSA) is an important problem in Bioinformatics that aims to align more than two sequences in order to emphasize similarity regions. This problem is known to be NP-Hard, so heuristic methods are used to solve it. DIALIGN-TX is an iterative heuristic method for MSA that generates alignments by concatenating ungapped regions with high similarity. Usually, the first phase of MSA algorithms is parallelized by distributing several independent tasks among the nodes. Even though heterogeneous multicore clusters are becoming very common nowadays, very few task allocation policies were proposed for this type of architecture. This paper proposes an MPI/OpenMP master/slave parallel strategy to run DIALIGN-TX in heterogeneous multicore clusters, with several allocation policies. We show that an appropriate choice of the master node has great impact on the overall system performance. Also, the results obtained in a heterogeneous multicore cluster composed of 4 nodes (30 cores), with real sequence sets show that the execution time can be drastically reduced when the appropriate allocation policy is used.     

Large scale multiple sequence alignment with simultaneous phylogeny inference

Multiple sequence alignment (MSA) and phylogenetic tree reconstruction are one of the most important problems in the computational biology. While both these problems are of great practical significance, in most cases they are very computationally demanding. In this paper we propose a new approach to the MSA problem which simultaneously infers an underlying phylogenetic tree. To process large data sets we provide parallel implementation of our method, which is based on the distributed caching of intermediate results. Finally, we show a parallel server designed for grid environments, and we report results of experiments performed with actual biological data, e.g. 1000 ribosomal RNA sequences.     

Order acceptance and scheduling to maximize total net revenue in permutation flowshops with weighted tardiness

The order acceptance and scheduling (OAS) problem is important in make-to-order production systems in which production capacity is limited and order delivery requirements are applied. This study proposes a multi-initiator simulated annealing (MSA) algorithm to maximize the total net revenue for the permutation flowshop scheduling problem with order acceptance and weighted tardiness. To evaluate the performance of the proposed MSA algorithm, computational experiments are performed and compared for a benchmark problem set of test instances with up to 500 orders. Experimental results reveal that the proposed heuristic outperforms the state-of-the-art algorithm and obtains the best solutions in 140 out of 160 benchmark instances.     

Performance analysis of computational approaches to solve Multiple Sequence Alignment

In the biotechnology field, the deployment of the Multiple Sequence Alignment (MSA) problem, which is a high performance computing demanding process, is one of the new challenges to address on the new parallel systems. The aim of this problem is to find similar regions on biological sequences. Furthermore, the goal of MSA applications is to align as much sequences as possible with a level of quality that makes the alignment biologically meaningful. An efficiency study of different MSA implementations, based on T-Coffee (one of the most used MSA aligners), has been performed in order to find new optimizations that may improve the average execution time on multi-core systems. We found that the current parallel implementations have some performance issues, affecting negatively the scalability of the process. Finally, the proposed implementation based on the usage of threads in conjunction with a message-passing library is presented, with the aim to optimize the execution of the MSA problem in multi-core-based clusters.