On Nakhleh's Metric for Reduced Phylogenetic Networks

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.     

Comparison of Tree-Child Phylogenetic Networks

Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of nontreelike evolutionary events, like recombination, hybridization, or lateral gene transfer. While much progress has been made to find practical algorithms for reconstructing a phylogenetic network from a set of sequences, all attempts to endorse a class of phylogenetic networks (strictly extending the class of phylogenetic trees) with a well-founded distance measure have, to the best of our knowledge and with the only exception of the bipartition distance on regular networks, failed so far. In this paper, we present and study a new meaningful class of phylogenetic networks, called tree-child phylogenetic networks, and we provide an injective representation of these networks as multisets of vectors of natural numbers, their path multiplicity vectors. We then use this representation to define a distance on this class that extends the well-known Robinson-Foulds distance for phylogenetic trees and to give an alignment method for pairs of networks in this class. Simple polynomial algorithms for reconstructing a tree-child phylogenetic network from its path multiplicity vectors, for computing the distance between two tree-child phylogenetic networks and for aligning a pair of tree-child phylogenetic networks, are provided. They have been implemented as a Perl package and a Java applet, which can be found at http://bioinfo.uib.es/~recerca/phylonetworks/mudistance/.     

Quarnet Inference Rules for Level-1 Networks

An important problem in phylogenetics is the construction of phylogenetic trees. One way to approach this problem, known as the supertree method, involves inferring a phylogenetic tree with leaves consisting of a set X of species from a collection of trees, each having leaf-set some subset of X. In the 1980s, Colonius and Schulze gave certain inference rules for deciding when a collection of 4-leaved trees, one for each 4-element subset of X, can be simultaneously displayed by a single supertree with leaf-set X. Recently, it has become of interest to extend this and related results to phylogenetic networks. These are a generalization of phylogenetic trees which can be used to represent reticulate evolution (where species can come together to form a new species). It has recently been shown that a certain type of phylogenetic network, called a (unrooted) level-1 network, can essentially be constructed from 4-leaved trees. However, the problem of providing appropriate inference rules for such networks remains unresolved. Here, we show that by considering 4-leaved networks, called quarnets, as opposed to 4-leaved trees, it is possible to provide such rules. In particular, we show that these rules can be used to characterize when a collection of quarnets, one for each 4-element subset of X, can all be simultaneously displayed by a level-1 network with leaf-set X. The rules are an intriguing mixture of tree inference rules, and an inference rule for building up a cyclic ordering of X from orderings on subsets of X of size 4. This opens up several new directions of research for inferring phylogenetic networks from smaller ones, which could yield new algorithms for solving the supernetwork problem in phylogenetics.     

Metrics for Phylogenetic Networks II: Nodal and Triplets Metrics

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.     

Study of biological networks using graph theory

As an effective modeling, analysis and computational tool, graph theory is widely used in biological mathematics to deal with various biology problems. In the field of microbiology, graph can express the molecular structure, where cell, gene or protein can be denoted as a vertex, and the connect element can be regarded as an edge. In this way, the biological activity characteristic can be measured via topological index computing in the corresponding graphs. In our article, we mainly study the biology features of biological networks in terms of eccentric topological indices computation. By means of graph structure analysis and distance calculating, the exact expression of several important eccentric related indices of hypertree network and X-tree are determined. The conclusions we get in this paper illustrate that the bioengineering has the promising application prospects.     

Statistics for Microsatellite Variation Based on Coalescence

The stepwise mutation model, which was at one time chiefly of interest in studying the evolution of protein charge-states, has recently undergone a resurgence of interest with the new popularity of microsatellites as phylogenetic markers. In this paper we describe a method which makes it possible to transfer many population genetics results from the standard infinite sites model to the stepwise mutation model. We study in detail the properties of pairwise differences in microsatellite repeat number between randomly chosen alleles. We show that the problem of finding the expected squared distance between two individuals and finding the variance of the squared distance can be reduced for a wide range of population models to finding the mean and mean square coalescence times. In many cases the distributions of coalescence times have already been studied for infinite site problems. In this study we show how to calculate these quantities for several population models. We also calculate the variance in mean squared pairwise distance (an estimator of mutation rate × population size) for samples of arbitrary size and show that this variance does not approach zero as the sample size increases. We can also use our method to study alleles at linked microsatellite loci. We suggest a metric which quantifies the level of association between loci—effectively a measure of linkage disequilibrium. It is shown that there can be linkage disequilibrium between partially linked loci at mutation–drift equilibrium.     

Information Filtering on Coupled Social Networks

In this paper, based on the coupled social networks (CSN), we propose a hybrid algorithm to nonlinearly integrate both social and behavior information of online users. Filtering algorithm, based on the coupled social networks, considers the effects of both social similarity and personalized preference. Experimental results based on two real datasets, Epinions and Friendfeed, show that the hybrid pattern can not only provide more accurate recommendations, but also enlarge the recommendation coverage while adopting global metric. Further empirical analyses demonstrate that the mutual reinforcement and rich-club phenomenon can also be found in coupled social networks where the identical individuals occupy the core position of the online system. This work may shed some light on the in-depth understanding of the structure and function of coupled social networks.     

New Gromov-Inspired Metrics on Phylogenetic Tree Space

We present a new class of metrics for unrooted phylogenetic X-trees inspired by the Gromov–Hausdorff distance for (compact) metric spaces. These metrics can be efficiently computed by linear or quadratic programming. They are robust under NNI operations, too. The local behaviour of the metrics shows that they are different from any previously introduced metrics. The performance of the metrics is briefly analysed on random weighted and unweighted trees as well as random caterpillars.     

Phylogenetic networks based on the molecular clock hypothesis

A classical result in phylogenetic trees is that a binary phylogenetic tree adhering to the molecular clock hypothesis exists if and only if the matrix of distances between taxa is ultrametric. The ultrametric condition is very restrictive. In this paper we study phylogenetic networks that can be constructed assuming the molecular clock hypothesis. We characterize distance matrices that admit such networks for 3 and 4 taxa. We also design two algorithms for constructing networks optimizing the least-squares fit.     

Power-Hop: A Pervasive Observation for Real Complex Networks

Complex networks have been shown to exhibit universal properties, with one of the most consistent patterns being the scale-free degree distribution, but are there regularities obeyed by the r-hop neighborhood in real networks? We answer this question by identifying another power-law pattern that describes the relationship between the fractions of node pairs C(r) within r hops and the hop count r. This scale-free distribution is pervasive and describes a large variety of networks, ranging from social and urban to technological and biological networks. In particular, inspired by the definition of the fractal correlation dimension D₂ on a point-set, we consider the hop-count r to be the underlying distance metric between two vertices of the network, and we examine the scaling of C(r) with r. We find that this relationship follows a power-law in real networks within the range 2 ≤ r ≤ d, where d is the effective diameter of the network, that is, the 90-th percentile distance. We term this relationship as power-hop and the corresponding power-law exponent as power-hop exponent h. We provide theoretical justification for this pattern under successful existing network models, while we analyze a large set of real and synthetic network datasets and we show the pervasiveness of the power-hop.     

Metrics for Phylogenetic Networks I: Generalizations of the Robinson-Foulds Metric

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.     

A metric of biodiversity that integrates abundance,phylogeny, and function

A metric of biodiversity is proposed that combines three of its key components: abundance, phylogeny, and ecological function. This metric is an expansion of the current abundance‐based metric that uses Hill numbers, the effective number of types in a sample if all types had the same mean proportional abundance. I define analogous proportional measures of phylogenetic divergence and functional distinctiveness. Phylogenetic divergence is measured as the sum of the proportional share of each species of a given branch of a phylogeny. Functional distinctiveness can be measured in two ways, as the proportional share of each species of a specified ecological function, or as the relative distance of each species based on functional trait values. Because all three aspects of biodiversity are measured in the same fashion (relative proportions) in similar units (effective numbers of species), an integrated metric can be defined. The combined metric provides understanding of covariation among the components and how management for one component may trade off against others. The metric can be partitioned into components of richness and evenness, and into subsets and variation among subsets, all of which can be related through a simple multiplicative framework. This metric is a complement to, rather than a replacement of, current metrics of phylogenetic and functional diversity. More work is needed to link this new metric to ecological theory, determine its error structure, and devise methods for its effective assessment.     

Modelling phylogenetic relationships using reticulated networks

Makarenkov, V., Legendre, P. & Desdevises, Y. (2004). Modelling phylogenetic relationships using reticulated networks. —  Zoologica Scripta , 33 , 89–96.
Most traditional methods of phylogenetic analysis assume that species evolution can be represented by means of a bifurcating tree model. In many phylogenetic situations, however, some of the evolutionary links between species are due to reticulate evolution. For instance, reticulate models can adequately describe such complicated mechanisms as lateral gene transfer in bacteria or species hybridization. The theoretical concepts of reticulate evolution developed in the 1980s and 1990s need to be supported by appropriate analytical tools and software. In this paper, we present the main features of a new distance-based method for modelling phylogenetic relationships among species by means of reticulated networks (RNs). The method uses the least-squares model to build a RN by gradually improving upon the solution provided by a phylogenetic tree. A computer program facilitating the reconstruction and visualization of reticulate phylogenies is made available to researchers. In the application section, we illustrate the usefulness of the method by studying the evolution of honeybees (genus Apis ). The method for reconstructing RNs has been included in the T-Rex ( Tree and Reticulogram Reconstruction ) package recently developed by the first-named author.     

Trinets encode tree-child and level-2 phylogenetic networks

Phylogenetic networks generalize evolutionary trees, and are commonly used to represent evolutionary histories of species that undergo reticulate evolutionary processes such as hybridization, recombination and lateral gene transfer. Recently, there has been great interest in trying to develop methods to construct rooted phylogenetic networks from triplets, that is rooted trees on three species. However, although triplets determine or encode rooted phylogenetic trees, they do not in general encode rooted phylogenetic networks, which is a potential issue for any such method. Motivated by this fact, Huber and Moulton recently introduced trinets as a natural extension of rooted triplets to networks. In particular, they showed that $\text{ level-1 }$ phylogenetic networks are encoded by their trinets, and also conjectured that all “recoverable” rooted phylogenetic networks are encoded by their trinets. Here we prove that recoverable binary level-2 networks and binary tree-child networks are also encoded by their trinets. To do this we prove two decomposition theorems based on trinets which hold for all recoverable binary rooted phylogenetic networks. Our results provide some additional evidence in support of the conjecture that trinets encode all recoverable rooted phylogenetic networks, and could also lead to new approaches to construct phylogenetic networks from trinets.     

Host specificity and interaction networks of insects feeding on seeds and fruits in tropical rainforests

In the tropics, antagonistic seed predation networks may have different properties than mutualistic pollination and seed dispersal networks, but the former have been considerably less studied. We tested whether the structure of antagonistic tripartite networks composed of host plants, insects developing within seeds and fruits, and their insect parasitoids could be predicted from plant phylogenetic distance and plant traits. We considered subsets of the networks (‘subnetworks') at three rainforest locations (Panama, Thailand, Papua New Guinea), based on insect families, plant families or plant functional groups. We recorded 3197 interactions and observed a low percentage of realized interactions, especially in Panama, where insect host specificity was higher than in Thailand or New Guinea. Several factors may explain this, including insect faunal composition, incidence of dry fruits, high fruit production and high occurrence of Fabaceae at the Panamanian site. Host specificity was greater among seed-eaters than pulp-eaters and for insects feeding on dry fruits as opposed to insects feeding on fleshy fruits. Plant species richness within plant families did not influence insect host specificity, but site characteristics may be important in this regard. Most subnetworks were extremely specialized, such as those including Tortricidae and Bruchinae in Panama. Plant phylogenetic distance, plant basal area and plant traits (fruit length, number of seeds per fruit) had important effects on several network statistics in regressions weighted by sampling effort. A path analysis revealed a weak direct influence of plant phylogenetic distance on parasitoid richness, indicating limited support for the ‘nasty host hypothesis'. Our study emphasizes the duality between seed dispersal and seed predation networks in the tropics, as key plant species differ and host specificity tends to be low in the former and higher in the latter. This underlines the need to study both types of networks for sound practices of forest regeneration and conservation.     

Neutral space analysis for a Boolean network model of the fission yeast cell cycle network

Background

Interactions between genes and their products give rise to complex circuits known as gene regulatory networks (GRN) that enable cells to process information and respond to external stimuli. Several important processes for life, depend of an accurate and context-specific regulation of gene expression, such as the cell cycle, which can be analyzed through its GRN, where deregulation can lead to cancer in animals or a directed regulation could be applied for biotechnological processes using yeast. An approach to study the robustness of GRN is through the neutral space. In this paper, we explore the neutral space of a Schizosaccharomyces pombe (fission yeast) cell cycle network through an evolution strategy to generate a neutral graph, composed of Boolean regulatory networks that share the same state sequences of the fission yeast cell cycle.

Results

Through simulations it was found that in the generated neutral graph, the functional networks that are not in the wildtype connected component have in general a Hamming distance more than 3 with the wildtype, and more than 10 between the other disconnected functional networks. Significant differences were found between the functional networks in the connected component of the wildtype network and the rest of the network, not only at a topological level, but also at the state space level, where significant differences in the distribution of the basin of attraction for the G₁ fixed point was found for deterministic updating schemes.

Conclusions

In general, functional networks in the wildtype network connected component, can mutate up to no more than 3 times, then they reach a point of no return where the networks leave the connected component of the wildtype. The proposed method to construct a neutral graph is general and can be used to explore the neutral space of other biologically interesting networks, and also formulate new biological hypotheses studying the functional networks in the wildtype network connected component.     

A metric for phylogenetic trees based on matching

Comparing two or more phylogenetic trees is a fundamental task in computational biology. The simplest outcome of such a comparison is a pairwise measure of similarity, dissimilarity, or distance. A large number of such measures have been proposed, but so far all suffer from problems varying from computational cost to lack of robustness; many can be shown to behave unexpectedly under certain plausible inputs. For instance, the widely used Robinson-Foulds distance is poorly distributed and thus affords little discrimination, while also lacking robustness in the face of very small changes--reattaching a single leaf elsewhere in a tree of any size can instantly maximize the distance. In this paper, we introduce a new pairwise distance measure, based on matching, for phylogenetic trees. We prove that our measure induces a metric on the space of trees, show how to compute it in low polynomial time, verify through statistical testing that it is robust, and finally note that it does not exhibit unexpected behavior under the same inputs that cause problems with other measures. We also illustrate its usefulness in clustering trees, demonstrating significant improvements in the quality of hierarchical clustering as compared to the same collections of trees clustered using the Robinson-Foulds distance.     

Performance comparison between k-tuple distance and four model-based distances in phylogenetic tree reconstruction

Phylogenetic tree reconstruction requires construction of a multiple sequence alignment (MSA) from sequences. Computationally, it is difficult to achieve an optimal MSA for many sequences. Moreover, even if an optimal MSA is obtained, it may not be the true MSA that reflects the evolutionary history of the underlying sequences. Therefore, errors can be introduced during MSA construction which in turn affects the subsequent phylogenetic tree construction. In order to circumvent this issue, we extend the application of the k-tuple distance to phylogenetic tree reconstruction. The k-tuple distance between two sequences is the sum of the differences in frequency, over all possible tuples of length k, between the sequences and can be estimated without MSAs. It has been traditionally used to build a fast ‘guide tree’ to assist the construction of MSAs. Using the 1470 simulated sets of sequences generated under different evolutionary scenarios, the neighbor-joining trees and BioNJ trees, we compared the performance of the k-tuple distance with four commonly used distance estimators including Jukes–Cantor, Kimura, F84 and Tamura–Nei. These four distance estimators fall into the category of model-based distance estimators, as each of them takes account of a specific substitution model in order to compute the distance between a pair of already aligned sequences. Results show that trees constructed from the k-tuple distance are more accurate than those from other distances most time; when the divergence between underlying sequences is high, the tree accuracy could be twice or higher using the k-tuple distance than other estimators. Furthermore, as the k-tuple distance voids the need for constructing an MSA, it can save tremendous amount of time for phylogenetic tree reconstructions when the data include a large number of sequences.     

Influence of tree shape and evolutionary time‐scale on phylogenetic diversity metrics

During the last decades, describing, analysing and understanding the phylogenetic structure of species assemblages has been a central theme in both community ecology and macro‐ecology. Among the wide variety of phylogenetic structure metrics, three have been predominant in the literature: Faith's phylogenetic diversity (PD_Faith), which represents the sum of the branch lengths of the phylogenetic tree linking all species of a particular assemblage, the mean pairwise distance between all species in an assemblage (MPD) and the pairwise distance between the closest relatives in an assemblage (MNTD). Comparisons between studies using one or several of these metrics are difficult because there has been no comprehensive evaluation of the phylogenetic properties each metric captures. In particular it is unknown how PD_Faith relates to MDP and MNTD. Consequently, it is possible that apparently opposing patterns in different studies might simply reflect differences in metric properties. Here, we aim to fill this gap by comparing these metrics using simulations and empirical data. We first used simulation experiments to test the influence of community structure and size on the mismatch between metrics whilst varying the shape and size of the phylogenetic tree of the species pool. Second we investigated the mismatch between metrics for two empirical datasets (gut microbes and global carnivoran assemblages). We show that MNTD and PD_Faith provide similar information on phylogenetic structure, and respond similarly to variation in species richness and assemblage structure. However, MPD demonstrate a very different behaviour, and is highly sensitive to deep branching structure. We suggest that by combining complementary metrics that are sensitive to processes operating at different phylogenetic depths (i.e. MPD and MNTD or PD_Faith) we can obtain a better understanding of assemblage structure.     

Properties of the nearest neighbor interchange metric for trees of small size

The crossover or nearest neighbor interchange metric has been proposed for use in numerical taxonomy to obtain a quantitative measure of distance between classifications that are modeled as unrooted binary trees with labeled leaves. This metric seems difficult to compute and its properties are poorly understood. A variant called the closest partition distance measure has also been proposed, but no efficient algorithm for its computation has yet appeared and its relationship to the nearest neighbor interchange metric is incompletely understood. I investigate four conjectures concerning the nearest neighbor interchange and closest partition distance measures and establish their validity for trees with as many as seven labeled vertices. For trees in this size range the two distance measures are identical. If a certain decomposition property holds for the nearest neighbor interchange metric, then the two distance measures are also identical at small distances for trees of any size.