BACKGROUND: MetaDAG is a web-based tool developed to address challenges posed by big data from omics technologies, particularly in metabolic network reconstruction and analysis. The tool is capable of constructing metabolic networks for specific organisms, sets of organisms, reactions, enzymes, or KEGG Orthology (KO) identifiers. By retrieving data from the KEGG database, MetaDAG helps users visualize and analyze complex metabolic interactions efficiently. RESULTS: MetaDAG computes two models: a reaction graph and a metabolic directed acyclic graph (m-DAG). The reaction graph represents reactions as nodes and metabolite flow between them as edges. The m-DAG simplifies the reaction graph by collapsing strongly connected components, significantly reducing the number of nodes while maintaining connectivity. MetaDAG can generate metabolic networks from various inputs, including KEGG organisms or custom data (e.g., reactions, enzymes, KOs). The tool displays these models on an interactive web page and provides downloadable files, including network visualizations. MetaDAG was tested using two datasets. In an eukaryotic analysis, it successfully classified organisms from the KEGG database at the kingdom and phylum levels. In a microbiome study, MetaDAG accurately distinguished between Western and Korean diets and categorized individuals by weight loss outcomes based on dietary interventions. CONCLUSION: MetaDAG offers an effective and versatile solution for metabolic network reconstruction from diverse data sources, enabling large-scale biological comparisons. Its ability to generate synthetic metabolisms and its broad application, from taxonomy classification to diet analysis, make it a valuable tool for biological research. MetaDAG is available online, with user support provided via a comprehensive guide. MetaDAG: https://bioinfo.uib.es/metadag/ User guide: https://biocom-uib.github.io/MetaDag/.

MOTIVATION: Two key steps in the analysis of uncultured viruses recovered from metagenomes are the taxonomic classification of the viral sequences and the identification of putative host(s). Both steps rely mainly on the assignment of viral proteins to orthologs in cultivated viruses. Viral Protein Families (VPFs) can be used for the robust identification of new viral sequences in large metagenomics datasets. Despite the importance of VPF information for viral discovery, VPFs have not yet been explored for determining viral taxonomy and host targets. RESULTS: In this work, we classified the set of VPFs from the IMG/VR database and developed VPF-Class. VPF-Class is a tool that automates the taxonomic classification and host prediction of viral contigs based on the assignment of their proteins to a set of classified VPFs. Applying VPF-Class on 731K uncultivated virus contigs from the IMG/VR database, we were able to classify 363K contigs at the genus level and predict the host of over 461K contigs. In the RefSeq database, VPF-class reported an accuracy of nearly 100% to classify dsDNA, ssDNA and retroviruses, at the genus level, considering a membership ratio and a confidence score of 0.2. The accuracy in host prediction was 86.4%, also at the genus level, considering a membership ratio of 0.3 and a confidence score of 0.5. And, in the prophages dataset, the accuracy in host prediction was 86% considering a membership ratio of 0.6 and a confidence score of 0.8. Moreover, from the Global Ocean Virome dataset, over 817K viral contigs out of 1 million were classified. AVAILABILITY AND IMPLEMENTATION: The implementation of VPF-Class can be downloaded from https://github.com/biocom-uib/vpf-tools. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: All molecular functions and biological processes are carried out by groups of proteins that interact with each other. Metaproteomic data continuously generates new proteins whose molecular functions and relations must be discovered. A widely accepted structure to model functional relations between proteins are protein-protein interaction networks (PPIN), and their analysis and alignment has become a key ingredient in the study and prediction of protein-protein interactions, protein function, and evolutionary conserved assembly pathways of protein complexes. Several PPIN aligners have been proposed, but attaining the right balance between network topology and biological information is one of the most difficult and key points in the design of any PPIN alignment algorithm. RESULTS: Motivated by the challenge of well-balanced and efficient algorithms, we have designed and implemented AligNet, a parameter-free pairwise PPIN alignment algorithm aimed at bridging the gap between topologically efficient and biologically meaningful matchings. A comparison of the results obtained with AligNet and with the best aligners shows that AligNet achieves indeed a good balance between topological and biological matching. CONCLUSION: In this paper we present AligNet, a new pairwise global PPIN aligner that produces biologically meaningful alignments, by achieving a good balance between structural matching and protein function conservation, and more efficient computations than state-of-the-art tools.

BACKGROUND: The alignment of protein-protein interaction networks was recently formulated as an integer quadratic programming problem, along with a linearization that can be solved by integer linear programming software tools. However, the resulting integer linear program has a huge number of variables and constraints, rendering it of no practical use. RESULTS: We present a compact integer linear programming reformulation of the protein-protein interaction network alignment problem, which can be solved using state-of-the-art mathematical modeling and integer linear programming software tools, along with empirical results showing that small biological networks, such as virus-host protein-protein interaction networks, can be aligned in a reasonable amount of time on a personal computer and the resulting alignments are structurally coherent and biologically meaningful. CONCLUSIONS: The implementation of the integer linear programming reformulation using current mathematical modeling and integer linear programming software tools provided biologically meaningful alignments of virus-host protein-protein interaction networks.

In general, a phylogenetic network is a graphical representation of an evolutionary history that involves reticulate events like recombinations, hybridizations, or lateral gene transfers. Tree-child reticulate networks (TC networks) are a special class of phylogenetic networks that allow to represent evolutionary histories where, despite the existence of such reticulate events, every ancestral species has some descendant through mutations. In this paper we establish two equivalent characterizations of the families of clusters of TC networks. These characterizations yield a simple, polynomial-time algorithm that decides whether a given family of clusters on a set of taxa is the family of clusters of some TC network or not, and, when the answer is positive, outputs a TC network that is a minimal reticulate network representing this family of clusters. This algorithm is based on the notion of cluster network introduced by Huson and Rupp, and it has been implemented in a Python package and a companion web tool, which are freely available on the web.

Galled trees, directed acyclic graphs that model evolutionary histories with isolated hybridization events, have become very popular due to both their biological significance and the existence of polynomial-time algorithms for their reconstruction. In this paper, we establish to which extent several distance measures for the comparison of evolutionary networks are metrics for galled trees, and hence, when they can be safely used to evaluate galled tree reconstruction methods.

The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the first in a series of papers devoted to the analysis and comparison of metrics for tree-child time consistent phylogenetic networks on the same set of taxa. In this paper, we study three metrics that have already been introduced in the literature: the Robinson-Foulds distance, the tripartitions distance and the mu-distance. They generalize to networks the classical Robinson-Foulds or partition distance for phylogenetic trees. We analyze the behavior of these metrics by studying their least and largest values and when they achieve them. As a by-product of this study, we obtain tight bounds on the size of a tree-child time consistent phylogenetic network.

The assessment of phylogenetic network reconstruction methods requires the ability to compare phylogenetic networks. This is the second in a series of papers devoted to the analysis and comparison of metrics for tree-child time consistent phylogenetic networks on the same set of taxa. In this paper, we generalize to phylogenetic networks two metrics that have already been introduced in the literature for phylogenetic trees: the nodal distance and the triplets distance. We prove that they are metrics on any class of tree-child time consistent phylogenetic networks on the same set of taxa, as well as some basic properties for them. To prove these results, we introduce a reduction/expansion procedure that can be used not only to establish properties of tree-child time consistent phylogenetic networks by induction, but also to generate all tree-child time consistent phylogenetic networks with a given number of leaves.

We prove that Nakhleh's metric for reduced phylogenetic networks is also a metric on the classes of tree-child phylogenetic networks, semibinary tree-sibling time consistent phylogenetic networks, and multilabeled phylogenetic trees. We also prove that it separates distinguishable phylogenetic networks. In this way, it becomes the strongest dissimilarity measure for phylogenetic networks available so far. Furthermore, we propose a generalization of that metric that separates arbitrary phylogenetic networks.

MOTIVATION: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a non-extant species to an extant one, and this multiplicity makes the comparison of phylogenetic networks much more difficult than the comparison of phylogenetic trees. In fact, all attempts to define a sound distance measure on the class of all phylogenetic networks have failed so far. Thus, the only practical solutions have been either the use of rough estimates of similarity (based on comparison of the trees embedded in the networks), or narrowing the class of phylogenetic networks to a certain class where such a distance is known and can be efficiently computed. The first approach has the problem that one may identify two networks as equivalent, when they are not; the second one has the drawback that there may not exist algorithms to reconstruct such networks from biological sequences. RESULTS: We present in this article a distance measure on the class of semi-binary tree-sibling time consistent phylogenetic networks, which generalize tree-child time consistent phylogenetic networks, and thus also galled-trees. The practical interest of this distance measure is 2-fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomial-time algorithms for reconstructing networks of this class from DNA sequence data. AVAILABILITY: The Perl package Bio::PhyloNetwork, included in the BioPerl bundle, implements many algorithms on phylogenetic networks, including the computation of the distance presented in this article. SUPPLEMENTARY INFORMATION: Some counterexamples, proofs of the results not included in this article, and some computational experiments are available at Bioinformatics online.

Let Σ be an arbitrary signature and ϒ be a non-empty set of operation symbols within it. A (partial) Σ-algebra is ϒ-total when all its operations in ϒ are total: these are the partly total algebras in the title, and they include total algebras and attributed graphs. In this paper we establish a necessary and sufficient condition on a pair of homomorphisms of ϒ-total Σ-algebras for the existence of a pushout complement of them. This solves the application problem for the double-pushout transformation of these kinds of structure.

Graph transitions represent an extension of the DPO approach to graph transformation for the specification of reactive systems. In this paper, we develop the theory of concurrency for graph transitions. In particular, we prove a local Church–Rosser theorem and define a notion of shift-equivalence that allows us to represent both intra-concurrency (within the specified subsystem) and inter-concurrency (between subsystem and environment). Via an implementation of transitions in terms of DPO transformations with context rules, a second, more restrictive notion of equivalence is defined that captures, in addition, the extra-concurrency (between operations of the environment). As a running example and motivation, we show how the concepts of this paper provide a formal model for distributed information systems.

The algebraic transformation of hypergraphs, under the so-called double-pushout (DPO) approach, was invented more than two decades ago, and thoroughly developed since then. We introduce in this paper a new approach to DPO algebraic transformation of hypergraphs and, more in general, of unary partial algebras, which generalizes the aforementioned “classical” DPO approach to hypergraph transformation. While the classical approach was based on the (usual) homomorphisms of hypergraphs, our new approach is based on the total conformisms, a type of morphisms of hypergraphs imported from the theory of partial algebras, which can be described, roughly speaking, as those mappings between hypergraphs that “reflect” the structure of the target object. In this paper we give both an algebraic and an operational characterization of this new DPO transformation, first for unary partial algebras and then, as a particular case, for hypergraphs. We also study its abstract properties related to parallelism and concurrency through the determination of the HLR conditions it satisfies with respect to several natural classes of morphisms.