Research on parallel computing has promoted significant advances in the solution of different real-world problems. One of the main application domains that have benefited from the exploitation of parallelism is bioinformatics. However, bioinformatics tools are often constrained by the use of low-level platform-specific programming models. This issue limits the spectrum of hardware that can be used to accelerate time-consuming biological workloads, while also affecting programming productivity and code maintenance. To address such limitations, this work investigates high-level multi-platform approaches to parallelize, as a case study, an important task in evolutionary bioinformatics: the evaluation of phylogenetic quality. Particularly, we define parallel designs of the parsimony scoring function for CPU and GPU devices, using three high-level application programming interfaces with multi-platform support: OpenMP, OpenACC, and SYCL. Different optimizations and algorithmic strategies are defined to boost execution according to the characteristics of the tackled parallel tasks. An in-depth experimental evaluation on real-world data reveals the main strengths and areas of improvement for each high-level multi-platform approach, in comparison to lower-level platform-specific alternatives. In addition, the study of single-source performance portability suggests that CPU designs behave better than GPU ones, yet device-oriented optimizations are still needed to pursue a precise exploitation of computational resources.

Gene networks have gained considerable relevance in cancer research, enabling the representation of complex biological relationships that provide insights into the mechanisms driving tumor development and progression. The increasing availability of biological data facilitates the construction of clinically relevant gene networks by integrating multiple information sources. Specifically, we consider mutation data, patient survival data, and protein-protein interaction data to identify networks whose genes are recurrently mutated, significantly involved in patient survival, and functionally associated. To this end, we apply multi-objective optimization to simultaneously maximize survival impact, functional association, and mutation coverage. Herein, we introduce MOTEA-GENSU (Multi-Objective Two-archive Evolutionary Algorithm to discover GEne Networks involved in SUrvival), a novel method that employs two collaborative archives and intelligent evolutionary operators to guide the generation of high-quality gene networks. Evaluation across 27 real biological scenarios covering diverse cancer types shows that MOTEA-GENSU outperforms existing methods, achieving superior results in 92.6% of comparisons, with improvements of up to 315.8% over the best-performing competing approach, and consistently surpassing all state-of-the-art methods on average within each evaluated dataset. Biological analysis of the identified networks validates their functional coherence and significant impact on cancer patient survival, revealing clinically relevant networks composed of genes with demonstrated prognostic value.

• Multi-objective algorithm based on decomposition for the tagSNP selection problem • Implementation of five new problem-aware operators to explore the search space • Comparative study of the proposed method with six different alternative approaches • Experimentation with five highly relevant datasets from 1000 Genomes Project (1KGP) • Competitive approach in terms of runtime and results quality after the comparisons Nowadays multiple bioinformatics issues can be solved by using evolutionary computation due to its potential to address complex optimization problems. TagSNP selection lies within this class of challenging problems, since genotyping all the Single Nucleotide Polymorphisms (SNPs) for haplotype identification is economically costly and time-consuming. If a reduced number of tagSNPs is chosen instead, the classification of haplotypes will accordingly show a worsening. As a result, tagSNP selection can be considered as a multi-objective optimization problem, in which the aim is to optimize haplotype dissimilarity while minimizing the number of selected tagSNPs. We propose and detail an approach based on the Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) for accurately selecting tagSNPs attending to these two objectives. The proposed method includes novel problem-aware operators for the initialization, crossover, and mutation to boost optimization capabilities. The proposal is experimentally compared with six approaches from the literature on five real datasets, using in the evaluation three quality metrics and their corresponding statistical analyses. The attained results denote that our algorithm provides statistically-significant improvements over previous methods with competitive runtimes, thus highlighting the relevance of the proposed multi-objective approach.

Identifying cancer driver pathways is essential in cancer research. This problem is well-suited to multi-objective optimization, as cancer driver pathways consist of frequently mutated genes that cover a significant proportion of patients and exhibit high correlation due to their coordinated functionality. Therefore, this problem involves two competing objectives to maximize: patient coverage and gene network correlation. To optimize these objectives simultaneously, we propose a Multi-objective Artificial Bee Colony approach for Identifying cancer driver Pathways (MABCIP). Our approach leverages the strengths of the Artificial Bee Colony algorithm in combining exploitation (via employed and onlooker bees) and exploration (through scout bees). MABCIP incorporates problem-aware initialization and mutation operators which substantially enhance its performance. Specifically, MABCIP achieves noteworthy improvements in hypervolume and attains 100% set coverage in most cases over the version with standard operators. We thoroughly evaluate MABCIP against state-of-the-art methods using real cancer datasets comprehending 45 experimental scenarios. MABCIP consistently outperforms existing methods, attaining the best results in 44 out of 45 experimental scenarios and showing remarkable performance in complex instances. Notably, MABCIP obtains results up to 7.1 times better than those of the best-performing state-of-the-art method. Moreover, MABCIP identifies pathways involved in the development of targeted therapies, highlighting its potential for identifying clinically relevant mechanisms.

• First multi-objective swarm-intelligence algorithm for solving document clustering • 3 objectives are adopted to handle clustering tasks: compactness, separation, and DBI • Problem-aware search operators are developed and integrated into the approach • The proposal is evaluated using 3 clustering metrics, comparing with other 15 methods • Mean improvements of 16.18% in F1C, 86.81% in ARI, and 21.53% in NMI are accomplished The explosive growth of uncategorized web documents requires effective methods for their organization. Clustering techniques address this challenge by automatically grouping similar documents, making large amounts of unstructured data more manageable. In recent times, multi-objective optimization approaches have become an effective way to solve the document clustering problem. However, in the scientific literature, there is a lack of studies that address this task by using swarm-intelligence algorithms from this optimization viewpoint. For this reason, a multi-objective swarm-intelligence algorithm for document clustering (MOSIDOC) has been designed, developed, and applied in this work. MOSIDOC is based on the idea of combining swarm-intelligence mechanisms from artificial bee colony with problem-aware operators to attain an accurate processing of the search space. The criteria of compactness, separation, and Davies-Bouldin index have been formulated as the objective functions to be optimized. The experimentation has been carried out on ODP-239, one of the most widely-used datasets for testing document clustering methods. To comprehensively evaluate the proposed approach, the evaluation metrics of cluster-level F1 measure, Adjusted Rand Index, and Normalized Mutual Information have been applied. The obtained results denote that MOSIDOC leads to average percentage improvements up to 86.81%, in comparison to other fifteen competing methods.

Epistasis detection is a bioinformatics application that searches for associations between sets of single nucleotide polymorphisms (SNPs) and a given trait of a population. Epistasis detection is a computationally complex problem, especially when tackling interaction orders above two. This paper presents a pioneering approach for performing third-order epistasis searches that has been devised around the bulk-synchronous parallel (BSP) model of execution, which is used in processor designs that target artificial intelligence (AI) workloads, such as Graphcore’s Intelligence Processing Unit (IPU). We propose a parallelization approach and a set of optimizations to efficiently exploit the computation and communication resources of these novel AI processors to perform precise bioinformatics searches. The proposed approach achieves a performance of 3.9 Tera SNP combinations evaluated per second, scaled to sample size, on an IPU-M2000 AI accelerator, while close to a linear speedup (up to 15.01×) is achieved with 16 IPU-M2000 accelerators.

The improved accessibility of gene sequencing technologies has led to creation of huge datasets, i.e. patient records related to certain human diseases (phenotypes). Hence, deriving fast and accurate algorithms for efficiently processing these datasets is a paramount concern to enable some key healthcare scenarios, such as personalizing treatments, explaining the occurrence of and/or susceptibility to complex conditions and reducing the spread of infectious diseases. This is especially true for high-order epistasis detection, one of the most computationally challenging problems in bioinformatics, where associations between a given phenotype and single nucleotide polymorphisms (SNPs) of a population can often only be uncovered through evaluation of a large number of SNP combinations. To tackle this challenge, we propose a novel fourth-order epistasis detection algorithm that leverages tensor processing capabilities of two distinct accelerator architectures by efficiently mapping core computations related to processing quads of SNPs to binary tensor-accelerated matrix operations. Experimental results show that the proposed approach delivers very high performance even in single-GPU environments, e.g., 27.8 and 90.9 tera quads of SNPs per second, scaled to the sample size, were processed on Titan RTX (Turing) and A100 (Ampere) PCIe GPUs, respectively. Being the first approach that exploits tensor cores for accelerating searches with interaction order above three, the proposed method achieved a performance of up to 835.4 tera quads of SNPs per second on the 8-GPU HGX A100 server, which represents performance two or more orders of magnitude higher than that of related art.

Developments in Genome-Wide Association Studies have led to the increasing notion that future healthcare techniques will be personalized to the patient, by relying on genetic tests to determine the risk of developing a disease. To this end, the detection of gene interactions that cause complex diseases constitutes an important application. Similarly to many applications in this field, extensive data sets containing genetic information for a series of patients are used (such as Single-Nucleotide Polymorphisms), leading to high computational complexity and memory utilization, thus constituting a major challenge when targeting high-performance execution in modern computing systems. To close this gap, this work proposes several novel approaches for the detection of three-way gene interactions in modern CPUs and GPUs, making use of different optimizations to fully exploit the target architectures. Crucial insights from the Cache-Aware Roofline Model are used to ensure the suitability of the applications to the computing devices. An extensive study of the architectural features of 13 CPU and GPU devices from all main vendors is also presented, allowing to understand the features relevant to obtain high-performance in this bioinformatics domain. To the best of our knowledge, this study is the first to perform such evaluation for epistasis detection. The proposed approaches are able to surpass the performance of state-of-the-art works in the tested platforms, achieving an average speedup of 3.9× (7.3× on CPUs and 2.8× on GPUs) and maximum speedup of 10.6× on Intel UHD P630 GPU.

Optimization problems are becoming increasingly difficult challenges as a result of the definition of more realistic formulations and the availability of larger input data. Fortunately, the computing capabilities of state-of-the-art heterogeneous systems represent an opportunity to deal with the main complexity factors of these problems. These platforms open the door to the definition of robust metaheuristic solvers, in which parallel computations of different nature can be efficiently mapped to the most suitable architectures and hardware resources. This work investigates the combination of multi-level parallelism and heterogeneous computing to address an important multiobjective problem in bioinformatics: phylogenetics. A parallel metaheuristic approach, based on the joint exploitation of parallel tasks at the algorithm, iteration, and solution levels, is proposed to tackle computationally intensive inferences on CPU+GPU systems. Different heterogeneous design alternatives are also discussed, in accordance with the way the interactions between CPU and GPU are handled. The experimental evaluation of the proposal on real-world biological datasets points out the benefits of using multi-level, heterogeneous strategies, reporting accelerations up to 396× over the baseline metaheuristic as well as significant energy savings with regard to other parallel approaches, without impacting multiobjective solution quality.

Inter-algorithm cooperative approaches are increasingly gaining interest as a way to boost the search capabilities of evolutionary algorithms (EAs). However, the growing complexity of real-world optimization problems demands new cooperative designs that implement performance-driven strategies to improve the solution quality. This article explores multiobjective cooperation to address an important problem in bioinformatics: the reconstruction of phylogenetic histories from amino acid data. The proposed method is built using representative algorithms from the three main multiobjective design trends: 1) nondominated sorting genetic algorithm II; 2) indicator-based evolutionary algorithm; and 3) multiobjective evolutionary algorithm based on decomposition. The cooperation is supervised by an Elite island component that, along with managing migrations, retrieves multitrend performance feedback from each approach to run additional instantiations of the most satisfying algorithm in each stage of the execution. Experimentation on five real-world problem instances shows the benefits of the proposal to handle complex optimization tasks, in comparison to stand-alone algorithms, standard island models, and other state-of-the-art methods.

Abstract One of the main challenges in synthetic biology lies in maximizing the expression levels of a protein by encoding it with multiple copies of the same gene. This task is often conducted under conflicting evaluation criteria, which motivates the formulation of protein encoding as a multi-objective optimization problem. Recent research reported significant results when adapting the artificial bee colony algorithm to address this problem. However, the length of proteins and the number of copies have a noticeable impact in the computational costs required to attain satisfying solutions. This work is aimed at proposing parallel bioinspired designs to tackle protein encoding in multiprocessor systems, considering different thread orchestration schemes to accelerate the optimization process while preserving the quality of results. Comparisons of solution quality with other approaches under three multi-objective quality metrics show that the proposed parallel method reaches significant quality in the encoded proteins. In addition, experimentation on six real-world proteins gives account of the benefits of applying asynchronous shared-memory schemes, attaining efficiencies of 92.11% in the most difficult stages of the algorithm and mean speedups of 33.28x on a 64-core server-grade system.

The manifestation of important genetic diseases is often a consequence of the interactions between Single Nucleotide Polymorphisms (SNPs), also known as epistasis. Detecting epistasis for high-order interactions results in a huge computational complexity, as the number of SNP combinations to be evaluated exponentially grows with the interaction order. To address this challenge, state-of-the-art exhaustive search-based methods for epistasis detection rely on GPUs and FPGAs to provide high-performance solutions tailored for a specific order (second and rarely third-order interactions) and/or specific data-set sizes. In this paper, a novel parameterizable architecture is proposed that enables the deployment of FPGA-based accelerators targeting any order of interactions and any data-set size. By relying on a set of algorithmic and architecture optimizations, the proposed accelerator showed to outperform current FPGA accelerators for second and third-order interactions by as much as 4.6× and 9.5×, respectively. The proposed solution also showed comparable performance to current GPGPU third-order implementations, while consuming up to 8.2× less energy. Finally, the proposed architecture allowed for the implementation of a fourth-order epistasis detection accelerator in an FPGA platform.

The investigation of highly-efficient parallel algorithms targeting modern heterogeneous systems can provide bioinformaticians new mechanisms to find relations between genetics, phenotype and environment. This paper proposes an approach for fourth-order exhaustive, i.e. as precise as possible, epistasis detection targeting modern heterogeneous systems. Being implemented in Data Parallel C++ / SYCL, the proposed approach relies on technologies and tools built around open standards, making it able to target different types of architectures and devices. As a means to show interoperability with hardware from different sources, we have included performance results obtained from execution on different systems. Scaled to the number of samples, the proposed approach achieved a performance per GPU stream core of up to 236, 472 or 487 mega quads of SNPs processed per second, on GPUs with the Gen9.5, Gen12 and Turing architectures. This metric is reported for different implementation variants combining different considered optimizations. The proposed approach is able to target a wide range of CPU and GPU devices, enabling more users to access high-throughput epistasis detection software.

The substitution of nucleotides at specific positions in the genome of a population, known as single-nucleotide polymorphisms (SNPs), has been correlated with a number of important diseases. Complex conditions such as Alzheimer's disease or Crohn's disease are significantly linked to genetics when the impact of multiple SNPs is considered. SNPs often interact in an epistatic manner, where the joint effect of multiple SNPs may not be simply mapped to a linear additive combination of individual effects. Genome-wide association studies considering epistasis are computationally challenging, especially when performing triplet searches is required. Some contemporary computer architectures support fused XOR and population count as the highest throughput operations as part of tensor operations. This article presents a new approach for efficiently repurposing this capability to accelerate 2-way (pairs) and 3-way (triplets) epistasis detection searches. Experimental evaluation targeting the Turing GPU architecture resulted in previously unattainable levels of performance, with the proposal being able to evaluate up to 108.1 and 54.5 tera unique sets of SNPs per second, scaled to the sample size, in 2-way and 3-way searches, respectively.

Genome-wide association studies are performed to correlate a number of diseases and other physical or even psychological conditions (phenotype) with substitutions of nucleotides at specific positions in the human genome, mainly single-nucleotide polymorphisms (SNPs). Some conditions, possibly because of the complexity of the mechanisms that give rise to them, have been identified to be more statistically correlated with genotype when multiple SNPs are jointly taken into account. However, the discovery of new associations between genotype and phenotype is exponentially slowed down by the increase of computational power required when epistasis, i.e., interactions between SNPs, is considered. This paper proposes a novel graphics processing unit (GPU)-based approach for epistasis detection that combines the use of modern tensor cores with native support for processing binarized inputs with algorithmic and target-focused optimizations. Using only a single mid-range Turing-based GPU, the proposed approach is able to evaluate 64.8×1012and 25.4×1012sets of SNPs per second, normalized to the number of patients, when considering 2-way and 3-way epistasis detection, respectively. This proposal is able to surpass the state-of-the-art approach by 6× and 8.2× in terms of the number of pairs and triplets of SNP allelic patient data evaluated per unit of time per GPU.

Parallelism has become a recurrent tool to support computational intelligence and, particularly, evolutionary algorithms in the solution of very complex optimization problems, especially in the multiobjective case. However, the selection of parallel evolutionary designs often represents a difficult question due to the multiple variables that must be considered to attain an accurate exploitation of hardware resources, along with their influence in solution quality. This work looks into this issue by conducting a comparative performance analysis of intra-algorithm parallel multiobjective evolutionary algorithms running on shared-memory configurations. We consider different design trends including A) generational approaches based on measurements of solution quality plus diversity, B) generational approaches based on measurements of solution quality exclusively, and C) non-generational approaches. Following these trends, a total of six representative algorithms are applied to tackle a challenging bioinformatics problem as a case study, phylogenetic reconstruction. Experimentation on real-world scenarios point out the main advantages and weaknesses of each design, outlining guidelines for the selection of methods according to the characteristics of the employed hardware, evolutionary properties, and the parallelism exploitation capabilities of the evaluated approaches.

Among the different scientific domains where metaheuristics find applicability, bioinformatics represents a particularly challenging field due to the multiple complexity factors involved in the processing of biological data. In this context, the exploration of protein sequence data is remarkably increasing the temporal demands of such biological problems, thus motivating the interest in investigating new approaches that effectively combine bioinspired metaheuristics and parallelism. This paper addresses the reconstruction of ancestral relationships from amino acid sequences by using a multiobjective approach based on the shuffled frog-leaping optimization technique. Due to the inherent parallel nature of this approach, we define different parallel schemes aimed at exploiting the computing capabilities of modern cluster platforms. The experiments performed in five real datasets give account of the relevance of using parallelism-aware metaheuristic designs, as well as the need to consider both parallel performance and solution quality when tackling such difficult optimization scenarios.

Summary The availability of heterogeneous CPU+GPU systems has opened the door to new opportunities for the development of parallel solutions to tackle complex biological problems. The reconstruction of evolutionary histories among species represents a grand computational challenge, which can be addressed by exploiting this kind of hardware designs. In this research, we study the application of heterogeneous computing with OpenCL to accelerate one of the most well‐known objective functions for inferring phylogenies, the phylogenetic parsimony function. For this purpose, we undertake the design of CPU and GPU kernel implementations of this relevant function, proposing a heterogeneous CPU+GPU multidevice approach that distributes multiple parsimony evaluations among processing devices. Experiments on 6 real nucleotide data sets and comparisons with other parallel implementations give account of the benefits of the proposal in this paper, obtaining significant parallel results by combining CPU and GPU capabilities in accordance with the characteristics of the input data.

The integration of parallel computing techniques into metaheuristics has traditionally represented a promising approach to tackle computationally demanding optimization problems. In the last years, metaheuristics have evolved by including more complex search mechanisms whose parallelization often leads to performance issues under classic parallel schemes. This work investigates the asynchronous non-generational parallelization model, which is aimed at dealing with performance pitfalls by allowing worker threads to behave as asynchronous independent agents. We incorporate asynchronous principles into a recently proposed metaheuristic for multiobjective optimization, the Indicator-Based Multiobjective Bat Algorithm, and apply the resulting approach to solve a real-world problem in the bioinformatics domain: the reconstruction of evolutionary histories. Experiments on multicore multiprocessor systems comprising up to 64 cores reveal the suitability of the model to address the main challenges of the metaheuristic design under study, outperforming other implementations and methods in terms of parallel performance while also achieving significant solution quality.

Summary The field of computational biology encloses a wide range of optimization problems that show non‐deterministic polynomial‐time hard complexities. Nowadays, phylogeneticians are dealing with a growing amount of biological data that must be analyzed to explain the origins of modern species. Evolutionary relationships among organisms are often described by means of tree‐shaped structures known as phylogenetic trees. When inferring phylogenies, two main challenges must be addressed. First, the inference of reliable evolutionary trees on data sets where different optimality principles support conflicting evolutionary hypotheses. Second, the processing of enormous tree searches spaces where traditional sequential strategies cannot be applied. In this sense, phylogenetic inference can benefit from the combination of high performance computing and evolutionary computation to carry out the reconstruction of complex evolutionary histories in reduced execution times. In this paper, we introduce multiobjective phylogenetics, a hybrid OpenMP/MPI approach to parallelize a well‐known multiobjective metaheuristic, the fast non‐dominated sorting genetic algorithm (NSGA‐II). This algorithm has been designed to conduct phylogenetic analyses on multi‐core clusters in accordance with two principles: maximum parsimony and maximum likelihood. The main goal is to combine the benefits of shared‐memory and distributed‐memory programming paradigms to efficiently infer a set of high‐quality Pareto solutions. Experiments on six real nucleotide data sets and comparisons with other hybrid parallel approaches show that multiobjective phylogenetics is able to achieve significant performance in terms of parallel, multiobjective, and biological results. Copyright © 2014 John Wiley & Sons, Ltd.

The development of efficient parallel algorithms based on mixed mode programming represents one of the most popular lines of research in current bioinformatics. By exploiting hardware resources at inter-node/intra-node level, we can address grand computational challenges which involve the optimization of multiple objective functions simultaneously. In this sense, the inference of evolutionary trees represents one of the most difficult NP-hard problems in the field. Tackling such a problem requires efficient parallel designs to take advantage of the characteristics of modern multicore clusters. In this paper, we aim to solve the phylogenetic inference problem by applying MPI/OpenMP schemes to two multiobjective metaheuristics: fast non-dominated sorting genetic algorithm and multiobjective firefly algorithm. In order to assess the performance achieved by these proposals under different system and problem sizes, we have conducted experiments on six real nucleotide data sets according to a statistical methodology. Our parallel and multiobjective metrics point out the relevance of combining hybrid programming and novel bioinspired designs with regard to other parallel and biological approaches from the literature.

Throughout the years, biological processing demands have been addressed by relying on the design of algorithmic approaches for parallel architectures. By taking advantage of multicore processor systems, we can deal with the main sources of complexity which explain the NP-hard nature of multiple problems in computational biology. In this work, we address the inference of phylogenetic topologies by using two multiobjective metaheuristics: Fast Non-Dominated Sorting Genetic Algorithm and Strength Pareto Evolutionary Algorithm 2. The additional complexity introduced by the multiobjective formulation of the problem motivates that parallel designs of these algorithms must be undertaken. For this purpose, OpenMP-based implementations of these two metaheuristics are applied. To evaluate the performance of these approaches, a comparative study has been conducted by performing experimentation on four nucleotide data sets. Our experiments suggest the relevance of these parallel algorithmic designs, improving the phylogenetic results reported by other multiobjective tools in reduced execution times.

Phylogenetic inference is one of the most challenging problems in Computational Biology. As recent research lines aim to introduce multiobjective optimization techniques to resolve incongruences in Phylogenetics, parallel multiobjective metaheuristics can be useful to address the computational complexity required to perform phylogenetic analyses according to multiple criteria simultaneously. In this work, we propose several master-worker hybrid approaches based on MPI and OpenMP to parallelize a multiobjective algorithm inspired by the behaviour of fireflies for inferring phylogenies on multicore cluster architectures. Experiments on four real biological data sets suggest that this algorithm can achieve significant speedup and efficiency values by using a proper hybrid model designed to exploit parallelism at the inference and assessment levels.

A wide variety of optimization problems requires the combination of Bioinspired and Parallel Computing to address the complexity needed to get optimal solutions in reduced times. The multicore era allows the researcher to exploit modern arqitectures to resolve these NP-Hard problems. Inferring phylogenetic trees which describe a hypothesis of the evolution of species is a well-known example of this kind of problems. As the space of possible tree topologies increases exponentially with the number of species, exhaustive searches cannot be applied. Also, additional difficulties arise when we must consider simultaneously multiple optimality measures to resolve the problem. In this paper, we report a performance study on multicore machines of a parallel multiobjective adaptation of the Artificial Bee Colony algorithm for inferring phylogenies according to the maximum parsimony and maximum likelihood criteria. Experimental results reveal that our proposal can improve other approaches based on advanced High Performance Computing techniques on large data sets.