A protein-protein interaction network aligner study in the multi-objective domain.

BACKGROUND AND OBJECTIVE: The protein-protein interaction (PPI) network alignment has proven to be an efficient technique in the diagnosis and prevention of certain diseases. However, the difficulty in maximizing, at the same time, the two qualities that measure the goodness of alignments (topological and biological quality) has led aligners to produce very different alignments. Thus making a comparative study among alignments of such different qualities a big challenge. Multi-objective optimization is a computer method, which is very powerful in this kind of contexts because both conflicting qualities are considered together. Analysing the alignments of each PPI network aligner with multi-objective methodologies allows you to visualize a bigger picture of the alignments and their qualities, obtaining very interesting conclusions. This paper proposes a comprehensive PPI network aligner study in the multi-objective domain. METHODS: Alignments from each aligner and all aligners together were studied and compared to each other via Pareto dominance methodologies. The best alignments produced by each aligner and all aligners together for five different alignment scenarios were displayed in Pareto front graphs. Later, the aligners were ranked according to the topological, biological, and combined quality of their alignments. Finally, the aligners were also ranked based on their average runtimes. RESULTS: Regarding aligners constructing the best overall alignments, we found that SAlign, BEAMS, SANA, and HubAlign are the best options. Additionally, the alignments of best topological quality are produced by: SANA, SAlign, and HubAlign aligners. On the contrary, the aligners returning the alignments of best biological quality are: BEAMS, TAME, and WAVE. However, if there are time constraints, it is recommended to select SAlign to obtain high topological quality alignments and PISwap or SAlign aligners for high biological quality alignments. CONCLUSIONS: The use of the SANA aligner is recommended for obtaining the best alignments of topological quality, BEAMS for alignments of the best biological quality, and SAlign for alignments of the best combined topological and biological quality. Simultaneously, SANA and BEAMS have above-average runtimes. Therefore, it is suggested, if necessary due to time restrictions, to choose other, faster aligners like SAlign or PISwap whose alignments are also of high quality.

Iterative Level-0: A new and fast algorithm to traverse mating networks calculating the inbreeding and relationship coefficients.

In population medical genetics, the study of autosomal recessive disorders in highly endogamous populations is a major topic where calculating the inbreeding and relationship coefficients on mating networks is crucial. However, a challenge arises when dealing with large and complex mating networks, making their traversal difficult during the calculation process. For this calculation, we propose using Iterative Level-0 (IL0) as a new and faster algorithm that traverses mating networks more efficiently. The purpose of this work is to explain in detail the IL0 algorithm and prove its superiority by comparing it with two algorithms based on the best-known algorithms in the area: Depth First Search (DFS) and Breadth First Search (BFS). A Cytoscape application has been developed to calculate the inbreeding and relationship coefficients of individuals composing any mating network. In this application, the IL0 proposal together with DFS-based and BFS-based algorithms have been implemented. Any user can access this freely available Cytoscape application (https://apps.cytoscape.org/apps/inbreeding) that allows the comparison between the IL0 proposal and the best-known algorithms (based on DFS and BFS). In addition, a diverse set of mating networks has been collected in terms of complexity (number of edges) and species (humans, primates, and dogs) for the experiments. The runtime obtained by the IL0, DFS-based, and BFS-based algorithms when calculating the inbreeding and relationship coefficients proved the improvement of IL0. In fact, a speedup study reflected that the IL0 algorithm is 7.60 to 127.50 times faster than DFS-based and BFS-based algorithms. Moreover, a scalability study found that the growth of the IL0 runtime has a linear dependence on the number of edges of the mating network, while the DFS-based and BFS-based runtimes have a quadratic dependence. Therefore, the IL0 algorithm can solve the problem of calculating the inbreeding and relationship coefficients many times faster (up to 127.50) than the two algorithms based on the famous DFS and BFS. Furthermore, our results demonstrate that IL0 scales much better as the complexity of mating networks increases.

Automatic Update Summarization by a Multiobjective Number-One-Selection Genetic Approach.

Currently, the explosive growth of the information available on the Internet makes automatic text summarization systems increasingly important. A particularly relevant challenge is the update summarization task. Update summarization differs from traditional summarization in its dynamic nature. While traditional summarization is static, that is, the document collections about a specific topic remain unchanged, update summarization addresses dynamic document collections based on a specific topic. Therefore, update summarization consists of summarizing the new document collection under the assumption that the user has already read a previous summarization and only the new information is interesting. The multiobjective number-one-selection genetic algorithm (MONOGA) has been designed and implemented to address this problem. The proposed algorithm produces a summary that is relevant to the user's given query, and it also contains updates information. Experiments were conducted on Text Analysis Conference (TAC) datasets, and Recall-Oriented Understudy for Gisting Evaluation (ROUGE) metrics were considered to assess the model performance. The results obtained by the proposed approach outperform those from the existing approaches in the scientific literature, obtaining average percentage improvements between 12.74% and 55.03% in the ROUGE scores.

PhageCocktail: An R package to design phage cocktails from experimental phage-bacteria infection networks.

BACKGROUND AND OBJECTIVE: Phage therapy is a resurgent strategy used in medicine and the food industry to lyse bacteria that cause damage to health or spoil a food product. Frequently, phage-bacteria infection networks have a large size, making it impossible to manually study all possible phage cocktails. Thus, this article presents an R package called PhageCocktail to automatically design efficient phage cocktails from phage-bacteria infection networks. METHODS: This R package includes four different methods for designing phage cocktails: ExhaustiveSearch, ExhaustivePhi, ClusteringSearch, and ClusteringPhi. These four methods are explained in detail and are evaluated using 13 empirical phage-bacteria infection networks. More specifically, runtime and expected success (fraction of lysed bacteria) are analyzed. RESULTS: The four methods have variations in terms of runtime and quality of the results. ExhaustiveSearch always provides the best possible phage cocktail, but its runtime could be long. ExhaustivePhi only focuses on one cocktail size, the one estimated as the best; thus, its runtime is less than ExhaustiveSearch, but it can produce cocktails with more phages than necessary. ClusteringSearch and ClusteringPhi are very fast (generally, less than one millisecond), providing always immediate results due to clustering techniques, but their accuracies can be lower, yielding cocktails with lower expected successes. CONCLUSIONS: The larger the phage-bacteria infection network is, the more complex its analysis is. Thus, this tool eases this task for scientists and other users while designing phage cocktails of good quality. This R package includes four different methods; therefore, users may choose among them, considering their preferences in speed and accuracy of results.

Systematic analysis of putative phage-phage interactions on minimum-sized phage cocktails.

The application of bacteriophages as antibacterial agents has many benefits in the "post-antibiotic age". To increase the number of successfully targeted bacterial strains, phage cocktails, instead of a single phage, are commonly formulated. Nevertheless, there is currently no consensus pipeline for phage cocktail development. Thus, although large cocktails increase the spectrum of activity, they could produce side effects such as the mobilization of virulence or antibiotic resistance genes. On the other hand, coinfection (simultaneous infection of one host cell by several phages) might reduce the potential for bacteria to evolve phage resistance, but some antagonistic interactions amongst phages might be detrimental for the outcome of phage cocktail application. With this in mind, we introduce here a new method, which considers the host range and each individual phage-host interaction, to design the phage mixtures that best suppress the target bacteria while minimizing the number of phages to restrict manufacturing costs. Additionally, putative phage-phage interactions in cocktails and phage-bacteria networks are compared as the understanding of the complex interactions amongst bacteriophages could be critical in the development of realistic phage therapy models in the future.

Computational design of phage cocktails based on phage-bacteria infection networks.

The misuse and overuse of antibiotics have boosted the proliferation of multidrug-resistant (MDR) bacteria, which are considered a major public health issue in the twenty-first century. Phage therapy may be a promising way in the treatment of infections caused by MDR pathogens, without the side effects of the current available antimicrobials. Phage therapy is based on phage cocktails, that is, combinations of phages able to lyse the target bacteria. In this work, we present and explain in detail two innovative computational methods to design phage cocktails taking into account a given phage-bacteria infection network. One of the methods (Exhaustive Search) always generates the best possible phage cocktail, while the other method (Network Metrics) always keeps a very reduced runtime (a few milliseconds). Both methods have been included in a Cytoscape application that is available for any user. A complete experimental study has been performed, evaluating and comparing the biological quality, runtime, and the impact when additional phages are included in the cocktail.

Inter-Algorithm Multiobjective Cooperation for Phylogenetic Reconstruction on Amino Acid Data.

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.

A stage-based approach to allocating water quality monitoring stations based on the WorldQual model: The Jubba River as a case study.

Ensuring adequate freshwater quality is an important aspect of integrated environmental management and sustainable development. One contribution towards this end is to monitor the water quality of river basins. An important issue in constructing a water quality monitoring network is how to allocate the stations. This is usually done by using in situ measurements of pollutants together with other information. A stage-based optimization approach has been developed to find the optimal sites to allocate the monitoring stations. The proposed approach constructs a network in a sequence of stages without the need for in situ pollution measurements. Instead, it uses pollutant estimates from the WorldQual model together with other social and hydrological criteria. The approach is computationally efficient and provides an ordered list of stations that can be used to initialize or augment a water quality network. This is especially relevant for consideration by developing countries since, with this approach, they can get an overview of their river basins, and then prioritize the initial distributions of the networks. The approach was applied successfully to the 741,751 km2 of the Jubba River basin, but it is applicable to river basins of any size.

A Parallel Multiobjective Metaheuristic for Multiple Sequence Alignment.

The alignment among three or more nucleotides/amino acids sequences at the same time is known as multiple sequence alignment (MSA), a nondeterministic polynomial time (NP)-hard optimization problem. The time complexity of finding an optimal alignment raises exponentially when the number of sequences to align increases. In this work, we deal with a multiobjective version of the MSA problem wherein the goal is to simultaneously optimize the accuracy and conservation of the alignment. A parallel version of the hybrid multiobjective memetic metaheuristics for MSA is proposed. To evaluate the parallel performance of our proposal, we have selected a pull of data sets with different number of sequences (up to 1000 sequences) and study its parallel performance against other well-known parallel metaheuristics published in the literature, such as MSAProbs, tree-based consistency objective function for alignment evaluation (T-Coffee), Clustal [Formula: see text], and multiple alignment using fast Fourier transform (MAFFT). The comparative study reveals that our parallel aligner obtains better results than MSAProbs, T-Coffee, Clustal [Formula: see text], and MAFFT. In addition, the parallel version is around 25 times faster than the sequential version with 32 cores, obtaining an efficiency around 80%.

A Characteristic-Based Framework for Multiple Sequence Aligners.

The multiple sequence alignment is a well-known bioinformatics problem that consists in the alignment of three or more biological sequences (protein or nucleic acid). In the literature, a number of tools have been proposed for dealing with this biological sequence alignment problem, such as progressive methods, consistency-based methods, or iterative methods; among others. These aligners often use a default parameter configuration for all the input sequences to align. However, the default configuration is not always the best choice, the alignment accuracy of the tool may be highly boosted if specific parameter configurations are used, depending on the biological characteristics of the input sequences. In this paper, we propose a characteristic-based framework for multiple sequence aligners. The idea of the framework is, given an input set of unaligned sequences, extract its characteristics and run the aligner with the best parameter configuration found for another set of unaligned sequences with similar characteristics. In order to test the framework, we have used the well-known multiple sequence comparison by log-expectation (MUSCLE) v3.8 aligner with different benchmarks, such as benchmark alignments database v3.0, protein reference alignment benchmark v4.0, and sequence alignment benchmark v1.65. The results shown that the alignment accuracy and conservation of MUSCLE might be greatly improved with the proposed framework, specially in those scenarios with a low percentage of identity. The characteristic-based framework for multiple sequence aligners is freely available for downloading at http://arco.unex.es/arl/fwk-msa/cbf-msa.zip.

Reducing Alignment Time Complexity of Ultra-Large Sets of Sequences.

The alignment of three or more protein or nucleotide sequences is known as Multiple Sequence Alignment problem. The complexity of this problem increases exponentially with the number of sequences; therefore, many of the current approaches published in the literature suffer a computational overhead when thousands of sequences are required to be aligned. We introduce a new approach for dealing with ultra-large sets of sequences. A two-level clustering method is considered. The first level clusters the input sequences by using their biological composition, that is, the number of positive, negative, polar, special, and hydrophobic amino acids. In the second level, each cluster is divided into different clusters according to their similarity. Then, each cluster is aligned by using any method/aligner. After aligning the centroid sequences of each second-level cluster, we extrapolate the new gaps to each cluster of sequences to obtain the final alignment. We present a study on biological data with up to ∼100,000 sequences, showing that the proposed approach is able to obtain accurate alignments in a reduced amount of time; for example, in >10,000 sequences datasets, it is able to reduce up to ∼45 times the required runtime of the well-known Kalign.

Finding Patterns in Protein Sequences by Using a Hybrid Multiobjective Teaching Learning Based Optimization Algorithm.

Proteins are molecules that form the mass of living beings. These proteins exist in dissociated forms like amino-acids and carry out various biological functions, in fact, almost all body reactions occur with the participation of proteins. This is one of the reasons why the analysis of proteins has become a major issue in biology. In a more concrete way, the identification of conserved patterns in a set of related protein sequences can provide relevant biological information about these protein functions. In this paper, we present a novel algorithm based on teaching learning based optimization (TLBO) combined with a local search function specialized to predict common patterns in sets of protein sequences. This population-based evolutionary algorithm defines a group of individuals (solutions) that enhance their knowledge (quality) by means of different learning stages. Thus, if we correctly adapt it to the biological context of the mentioned problem, we can get an acceptable set of quality solutions. To evaluate the performance of the proposed technique, we have used six instances composed of different related protein sequences obtained from the PROSITE database. As we will see, the designed approach makes good predictions and improves the quality of the solutions found by other well-known biological tools.

Gene variants and haplotypes modifying transcription factor binding sites in the human cyclooxygenase 1 and 2 (PTGS1 and PTGS2) genes.

Cyclooxygenases (prostaglandin-endoperoxide synthases, (EC 1.14.99.1) 1 and 2 (COX-1 and COX-2)) are key enzymes with a highly functional and pharmacological relevance. Genetic variations in the corresponding genes PTGS1 and PTGS2 are related to diverse human disorders and adverse drug reactions. Although COX-2 is highly inducible, most genetic association studies have focused on coding region gene variants. The aim of this study is to analyze the genetic variants modifying transcription factor binding sites in human PTGS genes based on the combined use of bioinformatics with 1,000 genomes data and replication by next generation sequencing. Updated information on gene sequences and variants was obtained from the 1,000 genomes website and from a replication sequencing study. Of the 570 upstream PTGS1 gene variants, 43 altered binding sites, either by disrupting existing sequences or by creating new binding sites. The most relevant are the SNP rs72769722, which creates a new binding site for NFKB, and the SNPs rs73559017 and rs76403914, both disrupting binding sites for CDX1. Of the 682 upstream PTGS2 gene variants, 31 altered binding sites, the most relevant being rs689466 and rs20417, which disrupt binding sequences for MYB and E2F, respectively; rs689462 which creates a new binding site for POU3F2; and a haplotype combining the SNPs rs34984585+rs10911904, which creates a new binding site for SRY. This study provides a detailed catalog of variant and invariant transcription factor binding sites for PTGS genes and related haplotypes. This information can be useful to identify potential genetic targets for studies related to COX enzymes.

DNA strand generation for DNA computing by using a multi-objective differential evolution algorithm.

In this paper, we use an adapted multi-objective version of the differential evolution (DE) metaheuristics for the design and generation of reliable DNA libraries that can be used for computation. DNA sequence design is a very relevant task in many recent research fields, e.g. nanotechnology or DNA computing. Specifically, DNA computing is a new computational model which uses DNA molecules as information storage and their possible biological interactions as processing operators. Therefore, the possible reactions and interactions among molecules must be strictly controlled to prevent incorrect computations. The design of reliable DNA libraries for bio-molecular computing is an NP-hard combinatorial problem which involves many heterogeneous and conflicting design criteria. For this reason, we modelled DNA sequence design as a multiobjective optimization problem and we solved it by using an adapted multi-objective version of DE metaheuristics. Seven different bio-chemical design criteria have been simultaneously considered to obtain high quality DNA sequences which are suitable for molecular computing. Furthermore, we have developed the multiobjective standard fast non-dominated sorting genetic algorithm (NSGA-II) in order to perform a formal comparative study by using multi-objective indicators. Additionally, we have also compared our results with other relevant results published in the literature. We conclude that our proposal is a promising approach which is able to generate reliable real-world DNA sequences that significantly improve other DNA libraries previously published in the literature.

Applying a multiobjective metaheuristic inspired by honey bees to phylogenetic inference.

The development of increasingly popular multiobjective metaheuristics has allowed bioinformaticians to deal with optimization problems in computational biology where multiple objective functions must be taken into account. One of the most relevant research topics that can benefit from these techniques is phylogenetic inference. Throughout the years, different researchers have proposed their own view about the reconstruction of ancestral evolutionary relationships among species. As a result, biologists often report different phylogenetic trees from a same dataset when considering distinct optimality principles. In this work, we detail a multiobjective swarm intelligence approach based on the novel Artificial Bee Colony algorithm for inferring phylogenies. The aim of this paper is to propose a complementary view of phylogenetics according to the maximum parsimony and maximum likelihood criteria, in order to generate a set of phylogenetic trees that represent a compromise between these principles. Experimental results on a variety of nucleotide data sets and statistical studies highlight the relevance of the proposal with regard to other multiobjective algorithms and state-of-the-art biological methods.