In this study, we tackle the challenge of reconstructing the evolutionary history of a group of species, a crucial problem in bioinformatics. Phylogenetic trees visually represent relationships among organisms. While the Neighbor-Joining method (NJ) is effective, it faces limitations with larger datasets, whereas the Unweighted Pair Group Method with Arithmetic Mean (UPGMA) is more efficient for such sets. However, the quality of the UPGMA tree may be compromised due to its assumptions about uniform evolutionary rates. In this work, we introduce a parallel implementation strategy using multi-threaded computing. This approach combines accuracy comparable to Neighbor-Joining with the time efficiency of UPGMA. Experimental tests on synthetic datasets ranging from 1k to 32k OTUs show good performance, accuracy, and scalability of the proposed solution when compared to Biotite, a popular tool employing a parallel approach for UPGMA and NJ. For large dataset (16k-32k) we achieved speedup up to 6 using a 24-core CPU. Morover, with appropriated setup our implementation is up to 447 times faster than NJ and up to 133 times faster than UPGMA with satisfactory quality.

The processes of stability and synchronization in networks of interacting dynamical entities perform very relevant roles in many biological contexts, and specially in gene regulatory networks. Coupled Boolean Networks (CBN) present a wide spectrum of potential applications, mainly in Systems Biology. Despite its importance, there are relatively few studies focused on stability involving a specific class of models. Attractor fields of CBNs consist in a constrained class of globally stable states of the system, in which the dynamics of each interacting entity remains “locally confined” in the same local attractor. The main goal of this paper is to present a computationally efficient method that, given a CBN as input, identify all its attractor fields. Experimental results show that our method is capable of recovering all attractor fields in a feasible time (in the order of minutes or at most a couple of hours in a single desktop), even for CBNs containing several thousands of attractor fields, suggesting that the proposed method is suitable to capture the dynamics structure of large scale CBNs.

Sequence alignment supports numerous tasks in bioinformatics, natural language processing, pattern recognition, social sciences, and other fields. While the alignment of two sequences may be performed swiftly in many applications, the simultaneous alignment of multiple sequences proved to be naturally more intricate. Although most multiple sequence alignment (MSA) formulations are NP-hard, several approaches have been developed, as they can outperform pairwise alignment methods or are necessary for some applications. Taking into account not only similarities but also the lengths of the compared sequences (i.e. normalization) can provide better alignment results than both unnormalized or post-normalized approaches. While some normalized methods have been developed for pairwise sequence alignment, none have been proposed for MSA. This work is a first effort towards the development of normalized methods for MSA. We discuss multiple aspects of normalized multiple sequence alignment (NMSA). We define three new criteria for computing normalized scores when aligning multiple sequences, showing the NP-hardness and exact algorithms for solving the NMSA using those criteria. In addition, we provide approximation algorithms for MSA and NMSA for some classes of scoring matrices.

Boolean networks are discrete-time dynamic systems that have been used as a model for a wide range of applications in different areas, especially in Systems Biology. The analysis of Boolean networks includes the search for attractors, which may represent important biological conditions such as gene expression patterns in models of gene regulatory networks, among others. Attractors can be found through exploring the network paths by achieving the solution to the SAT problem, which is known to be NP-complete. In this paper, we propose an approach to find all attractors by first transforming the corresponding instance of the SAT problem to a Hitting Set instance in linear time through a new direct linear reduction. Finally, the instance of the Hitting Set problem is solved by applying a fast parallel algorithm implemented in GPU. As a proof of principle, we tested the method for Boolean networks with 3 and 4 variables, returning the result in about 3 seconds and 9 hours respectively. However, for larger networks the execution time grows substantially due to the algorithm used in the Hitting Set problem solver. But the result achieved for networks with 3 and 4 variables encourages improvements in the method for dealing with large-scale Boolean networks, specially by incorporating some parameter restrictions based on prior information about the state diagram transition graphs structure and optimizing the method by means of dynamic programming and parallelism.

Summary We present a hybrid exact algorithm for the Minimal Hitting Set (MHS) Enumeration Problem for highly heterogeneous CPU‐GPU‐MIC platforms. With several techniques that permit an efficient exploitation of each architecture, low communication cost, and effective load balancing, we were able to enumerate MHSs for large instances in reasonable time, achieving good performance and scalability. We obtained speedups of up to 25.32 in comparison with using two six‐core CPUs and we also enumerated MHSs for instances with tens of thousands of variables in less than 5 hours. We also evaluated our algorithm with a real‐world driven dataset, and with a large CPU‐GPU cluster, we unprecedentedly enumerated in parallel large minimal hitting sets of this dataset in less than 8 hours. These results reinforce the statement that heterogeneous clusters of CPUs, GPUs, and MICs can be used efficiently for high‐performance computing.

Multiple sequence alignment (MSA) is critical in several areas of science, especially in bioinformatics. Expressive advances have been developed in MSA and many methods, algorithms and tools have been proposed for it. Since the MSA is an NP-hard problem, efforts have led to the emergence of heuristics to solve it. More recently, heuristics based on progressive alignment have highlighted due to the quality of the alignment and relatively good performance. Despite significant advances, MSA remains a time-consuming task and parallel solutions have been investigated. We propose a novel algorithm for solving MSA based on progressive alignment using cluster of GPUs. Our experimental results showed encouraging speedups for instances containing sequences ranging in length between 60 and 10k.

The Systems Biology field presents several complex combinatorial problems that can be in part reduced to an instance of the Hitting Set Problem (HSP), which is NP-Hard. These reduced problems often come with a large amount of data that needs to be processed, such as gene expression profiles, resulting in prohibitive computational costs for finding the exact solutions. There are some proposals to obtain exact solutions for HSP, including an approach which uses GPUs. However, such an approach is not scalable for real input sizes (thousands of variables). We propose a novel algorithm for solving HSP instances with thousands of variables by using: (i) clause sorting, which enables the efficient discarding of non-solution candidates, (ii) parallel generation and evaluation of candidate solutions through the use of GPUs, and (iii) support for multiple GPUs. To permit the execution on heterogeneous clusters, we determine the minimum kernel size that does not incur extra overhead and distribute tasks among available GPUs on demand. Our experimental results show that the combination of these techniques results in a speedup of 118.5, when using eight NVIDIA Tesla K20c in comparison with a ten-core Intel Xeon E5-2690 processor. Consequently, our algorithm can enable the usage of exact algorithms for solving the Hitting Set problem and applying it to real world problems.

Gene regulatory networks inference is one of the crucial problems of the Systems Biology field. It is still an open problem, mainly because of its high dimensionality (thousands of genes) with a limited number of samples (dozens), making it difficult to estimate dependencies among genes. Besides the estimation problem, another important hindrance is the inherent computational complexity of GRN inference methods. In this work, we focus on circumventing performance issues of a technique based on signal perturbations to infer gene dependencies. One of its main steps consists in solving the Hitting Set problem (HSP), which is NP-Hard. There are many proposals to obtain approximate or exact solutions to this problem. One of these proposals consists of a Graphical Processing Unit (GPU) based algorithm to obtain exact solutions to the HSP. However, such method is not scalable for real size GRNs. We propose an extension of the HSP algorithm to deal with input sets containing thousands of variables by introducing innovations in the data structures and a sorting scheme to allow efficient discarding of Hitting Set non-solution candidates. We provide an implementation for multi-core CPUs and GPU clusters. Our experimental results show that the usage of the sorting scheme brings speedups of up to 3.5 in the CPU implementation. Moreover, using a single GPU, we could obtain an additional speedup of up to 4.7, in comparison with the multithreaded CPU implementation. Finally, usage of eight GPUs from a GPU cluster brought an additional speedup of up to 6.6. Combining all techniques, speedups above 60 were obtained for the parallel part of the algorithm.

BACKGROUND: Gene regulatory networks (GRN) inference is an important bioinformatics problem in which the gene interactions need to be deduced from gene expression data, such as microarray data. Feature selection methods can be applied to this problem. A feature selection technique is composed by two parts: a search algorithm and a criterion function. Among the search algorithms already proposed, there is the exhaustive search where the best feature subset is returned, although its computational complexity is unfeasible in almost all situations. The objective of this work is the development of a low cost parallel solution based on GPU architectures for exhaustive search with a viable cost-benefit. We use CUDA™, a general purpose parallel programming platform that allows the usage of NVIDIA® GPUs to solve complex problems in an efficient way. RESULTS: We developed a parallel algorithm for GRN inference based on multiple GPU cards and obtained encouraging speedups (order of hundreds), when assuming that each target gene has two multivariate predictors. Also, experiments using single and multiple GPUs were performed, indicating that the speedup grows almost linearly with the number of GPUs. CONCLUSION: In this work, we present a proof of principle, showing that it is possible to parallelize the exhaustive search algorithm in GPUs with encouraging results. Although our focus in this paper is on the GRN inference problem, the exhaustive search technique based on GPU developed here can be applied (with minor adaptations) to other combinatorial problems.

Abstract Large‐scale simulations of parts of the brain using detailed neuronal models to improve our understanding of brain functions are becoming a reality with the usage of supercomputers and large clusters. However, the high acquisition and maintenance cost of these computers, including the physical space, air conditioning, and electrical power, limits the number of simulations of this kind that scientists can perform. Modern commodity graphical cards, based on the CUDA platform, contain graphical processing units (GPUs) composed of hundreds of processors that can simultaneously execute thousands of threads and thus constitute a low‐cost solution for many high‐performance computing applications. In this work, we present a CUDA algorithm that enables the execution, on multiple GPUs, of simulations of large‐scale networks composed of biologically realistic Hodgkin–Huxley neurons. The algorithm represents each neuron as a CUDA thread, which solves the set of coupled differential equations that model each neuron. Communication among neurons located in different GPUs is coordinated by the CPU. We obtained speedups of 40 for the simulation of 200k neurons that received random external input and speedups of 9 for a network with 200k neurons and 20M neuronal connections, in a single computer with two graphic boards with two GPUs each, when compared with a modern quad‐core CPU. Copyright © 2010 John Wiley & Sons, Ltd.

Juxtacrine signaling is intercellular communication, in which the receptor of the signal (typically a protein) as well as the ligand (also typically a protein, responsible for the activation of the receptor) are anchored in the plasma membranes, so that in this type of signaling the activation of the receptor depends on direct contact between the membranes of the cells involved. Juxtacrine signaling is present in many important cellular events of several organisms, especially in the development process. We propose a generic formal model (a modeling framework) for juxtacrine signaling systems that is a class of dynamic discrete systems. It possesses desirable characteristics in a good modeling framework, such as: a) structural similarity with biological models, b) capacity of operating in different scales of time and c) capacity of explicitly treating both the events and molecular elements that occur in the membrane, and those that occur in the intracellular environment and are involved in the juxtacrine signaling process. We implemented this framework and used to develop a new discrete model for the neurogenic network and its participation in neuroblast segregation