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.

An important problem in Computational Biology is to determine genetic markers, substrings of a set of sequences that do not occur on sequences of other sets. Applications for this problem include finding small specific regions for primer design and to find specific organisms or sequences in metagenomes. Genetic markers can be addressed by the Specific Substring Problem - SSP which consists of finding all minimal substrings in a given set of sequences with at least k differences among all the substrings in another sequence set. Since this problem spend quadratic time when Hamming distance is considered and we have, in general, a large volume of data to be processed, this solution becomes impractical. With this in mind, the main focus of this work is to propose and investigate the use of heuristic and parallel approaches for the SSP whose effectiveness were verified with artificial and real data experiments.

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.

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.

BACKGROUND: During evolution, genomes are modified by large scale structural events, such as rearrangements, deletions or insertions of large blocks of DNA. Of particular interest, in order to better understand how this type of genomic evolution happens, is the reconstruction of ancestral genomes, given a phylogenetic tree with extant genomes at its leaves. One way of solving this problem is to assume a rearrangement model, such as Double Cut and Join (DCJ), and find a set of ancestral genomes that minimizes the number of events on the input tree. Since this problem is NP-hard for most rearrangement models, exact solutions are practical only for small instances, and heuristics have to be used for larger datasets. This type of approach can be called event-based. Another common approach is based on finding conserved structures between the input genomes, such as adjacencies between genes, possibly also assigning weights that indicate a measure of confidence or probability that this particular structure is present on each ancestral genome, and then finding a set of non conflicting adjacencies that optimize some given function, usually trying to maximize total weight and minimizing character changes in the tree. We call this type of methods homology-based. RESULTS: In previous work, we proposed an ancestral reconstruction method that combines homology- and event-based ideas, using the concept of intermediate genomes, that arise in DCJ rearrangement scenarios. This method showed better rate of correctly reconstructed adjacencies than other methods, while also being faster, since the use of intermediate genomes greatly reduces the search space. Here, we generalize the intermediate genome concept to genomes with unequal gene content, extending our method to account for gene insertions and deletions of any length. In many of the simulated datasets, our proposed method had better results than MLGO and MGRA, two state-of-the-art algorithms for ancestral reconstruction with unequal gene content, while running much faster, making it more scalable to larger datasets. CONCLUSION: Studing ancestral reconstruction problems under a new light, using the concept of intermediate genomes, allows the design of very fast algorithms by greatly reducing the solution search space, while also giving very good results. The algorithms introduced in this paper were implemented in an open-source software called RINGO (ancestral Reconstruction with INtermediate GenOmes), available at https://github.com/pedrofeijao/RINGO .

The study of motifs plays a central role in recognition of relations among components in biological networks such that gene regulation, protein interaction, and metabolic networks. Since these relations are not well-known, motifs inference appears as a way for understanding the principles involved in the relationship between cellular components. On the other hand, motifs search is a basic step for constructing models which represent biological behavior and explain functional and/or structural effects in biological networks. In this work we address the problem of infer all relevant motifs in a biological network. We also provide a solution for searching colorful motifs which can be topological-free or have an acyclic topology. We developed a tool for searching and inferring motifs, named SIMBio, and we implemented sequential and parallel versions. When comparing performance, our experiments have showed that SIMBio is faster than MOTUS for inferring motifs, even in the sequential version. We also compared it to Torque, and SIMBio has found more occurrences of motifs under the same experiments.

In this work, we address the topological colored motif search problem in metabolic networks. This problem is a concern in biology, which seeks to describe the functions and the evolution of metabolism. Recently, several variations of this problem have been studied. Here, we present some hardness results for finding motifs. Furthermore, we describe the first polynomial algorithm for the case in which the motif is a colorful tree. We also detail a data structure that allows finding all of these types of motifs in a metabolic network.