Search

Divide-and-conquer dividing by a half recurrences, of the form $x_n =a\cdot x_{\left\lceil{n}/{2}\right\rceil}+a\cdot x_{\left\lfloor{n}/{2}\right\rfloor}+p(n)$, $n\geq 2$, appear in many areas of applied mathematics, from the analysis of algorithms to the optimization of phylogenetic balance indices. The Master Theorems that solve these equations do not provide the solution's explicit expression, only its big-$\Theta$ order of growth. In this paper we give an explicit expression (in terms of the binary decomposition of $n$) for the solution $x_n$ of a recurrence of this form, with given initial condition $x_1$, when the independent term $p(n)$ is a polynomial in $\lceil{n}/{2}\rceil$ and $\lfloor{n}/{2}\rfloor$., Comment: 50 pages

The Colless index for bifurcating phylogenetic trees, introduced by Colless (1982), is defined as the sum, over all internal nodes $v$ of the tree, of the absolute value of the difference of the sizes of the clades defined by the children of $v$. It is one of the most popular phylogenetic balance indices, because, in addition to measuring the balance of a tree in a very simple and intuitive way, it turns out to be one of the most powerful and discriminating phylogenetic shape indices. But it has some drawbacks. On the one hand, although its minimum value is reached at the so-called maximally balanced trees, it is almost always reached also at trees that are not maximally balanced. On the other hand, its definition as a sum of absolute values of differences makes it difficult to study analytically its distribution under probabilistic models of bifurcating phylogenetic trees. In this paper we show that if we replace in its definition the absolute values of the differences of clade sizes by the squares of these differences, all these drawbacks are overcome and the resulting index is still more powerful and discriminating than the original Colless index., Comment: 31 pages

Measures of tree balance play an important role in the analysis of phylogenetic trees. One of the oldest and most popular indices in this regard is the Colless index for rooted bifurcating trees, introduced by Colless (1982). While many of its statistical properties under different probabilistic models for phylogenetic trees have already been established, little is known about its minimum value and the trees that achieve it. In this manuscript, we fill this gap in the literature. To begin with, we derive both recursive and closed expressions for the minimum Colless index of a tree with $n$ leaves. Surprisingly, these expressions show a connection between the minimum Colless index and the so-called Blancmange curve, a fractal curve. We then fully characterize the tree shapes that achieve this minimum value and we introduce both an algorithm to generate them and a recurrence to count them. After focusing on two extremal classes of trees with minimum Colless index (the maximally balanced trees and the greedy from the bottom trees), we conclude by showing that all trees with minimum Colless index also have minimum Sackin index, another popular balance index., Comment: 61 pages. This paper is the result of merging our previous preprints arXiv:1903.11670 [q-bio.PE] and arXiv:1904.09771 [math.CO] into a single joint manuscript. Several proofs are new

The Colless index is one of the oldest and most widely used balance indices for rooted bifurcating trees. Despite its popularity, its minimum value on the space $\mathcal{T}_n$ of rooted bifurcating trees with $n$ leaves is only known when $n$ is a power of 2. In this paper we fill this gap in the literature, by providing a formula that computes, for each $n$, the minimum Colless index on $\mathcal{T}_n$, and characterizing those trees where this minimum value is reached., Comment: This manuscript has been subsumed by another manuscript, which can be found on arXiv: arXiv:1907.05064

One of the most difficult problems difficult problem in systems biology is to discover protein-protein interactions as well as their associated functions. The analysis and alignment of protein-protein interaction networks (PPIN), which are the standard model to describe protein-protein interactions, has become a key ingredient to obtain functional orthologs as well as evolutionary conserved pathways and protein complexes. Several methods have been proposed to solve the PPIN alignment problem, aimed to match conserved subnetworks or functionally related proteins. However, the right balance between considering network topology and biological information is one of the most difficult and key points in any PPIN alignment algorithm which, unfortunately, remains unsolved. Therefore, in this work, we propose AligNet, a new method and software tool for the pairwise global alignment of PPIN that produces biologically meaningful alignments and more efficient computations than state-of-the-art methods and tools, by achieving a good balance between structural matching and protein function conservation as well as reasonable running times., Comment: 30 pages, 11 figures

The Colless index is one of the most popular and natural balance indices for bifurcating phylogenetic trees, but it makes no sense for multifurcating trees. In this paper we propose a family of Colless-like balance indices $\mathfrak{C}_{D,f}$, which depend on a dissimilarity $D$ and a function $f:\mathbb{N}\to \mathbb{R}_{\geq 0}$, that generalize the Colless index to multifurcating phylogenetic trees. We provide two functions $f$ such that the most balanced phylogenetic trees according to the corresponding indices $\mathfrak{C}_{D,f}$ are exactly the fully symmetric ones. Next, for each one of these two functions $f$ and for three popular dissimilarities $D$ (the variance, the standard deviation, and the mean deviation from the median), we determine the range of values of $\mathfrak{C}_{D,f}$ on the sets of phylogenetic trees with a given number $n$ of leaves. We end the paper by assessing the performance of one of these indices on TreeBASE and using it to show that the trees in this database do not seem to follow either the uniform model for multifurcating trees or the $\alpha$-$\gamma$-model, for any values of $\alpha$ and $\gamma$., Comment: 48 pages; 16 figures; it includes as appendices the two supplementary files mentioned in the main text

The Fair Proportion of a species in a phylogenetic tree is a very simple measure that has been used to assess its value relative to the overall phylogenetic diversity represented by the tree. It has recently been proved by Fuchs and Jin to be equal to the Shapley Value of the coallitional game that sends each subset of species to its rooted Phylogenetic Diversity in the tree. We prove in this paper that this result extends to the natural translations of the Fair Proportion and the rooted Phylogenetic Diversity to rooted phylogenetic networks. We also generalize to rooted phylogenetic networks the expression for the Shapley Value of the unrooted Phylogenetic Diversity game on a phylogenetic tree established by Haake, Kashiwada and Su., Comment: 12 pages

We define a new balance index for rooted phylogenetic trees based on the symmetry of the evolutive history of every set of 4 leaves. This index makes sense for multifurcating trees and it can be computed in time linear in the number of leaves. We determine its maximum and minimum values for arbitrary and bifurcating trees, and we provide exact formulas for its expected value and variance on bifurcating trees under Ford's $\alpha$-model and Aldous' $\beta$-model and on arbitrary trees under the $\alpha$-$\gamma$-model., Comment: 38 pages, 12 figures

We give correct explicit formulas for the probabilities of rooted binary trees and cladograms under Ford's $\alpha$-model., Comment: 9 pages

The cophenetic metrics $d_{\varphi,p}$, for $p\in {0}\cup[1,\infty[$, are a recent addition to the kit of available distances for the comparison of phylogenetic trees. Based on a fifty years old idea of Sokal and Rohlf, these metrics compare phylogenetic trees on a same set of taxa by encoding them by means of their vectors of cophenetic values of pairs of taxa and depths of single taxa, and then computing the $L^p$ norm of the difference of the corresponding vectors. In this paper we compute the expected value of the square of $d_{\varphi,2}$ on the space of fully resolved rooted phylogenetic trees with $n$ leaves, under the Yule and the uniform probability distributions., Comment: 22 pages

Phylogenetic tree comparison metrics are an important tool in the study of evolution, and hence the definition of such metrics is an interesting problem in phylogenetics. In a paper in Taxon fifty years ago, Sokal and Rohlf proposed to measure quantitatively the difference between a pair of phylogenetic trees by first encoding them by means of their half-matrices of cophenetic values, and then comparing these matrices. This idea has been used several times since then to define dissimilarity measures between phylogenetic trees but, to our knowledge, no proper metric on weighted phylogenetic trees with nested taxa based on this idea has been formally defined and studied yet. Actually, the cophenetic values of pairs of different taxa alone are not enough to single out phylogenetic trees with weighted arcs or nested taxa. In this paper we define a family of cophenetic metrics that compare phylogenetic trees on a same set of taxa by encoding them by means of their vectors of cophenetic values of pairs of taxa and depths of single taxa, and then computing the $L^p$ norm of the difference of the corresponding vectors. Then, we study, either analytically or numerically, some of their basic properties: neighbors, diameter, distribution, and their rank correlation with each other and with other metrics., Comment: The "authors' cut" of a paper published in BMC Bioinformatics 14:3 (2013). 46 pages

The graph isomorphism problem has a long history in mathematics and computer science, with applications in computational chemistry and biology, and it is believed to be neither solvable in polynomial time nor NP-complete. E. Luks proposed in 1982 the best algorithm so far for the solution of this problem, which moreover runs in polynomial time if an upper bound for the degrees of the nodes in the graphs is taken as a constant. Unfortunately, Luks' algorithm is purely theoretical, very difficult to use in practice, and, in particular, we have not been able to find any implementation of it in the literature. The main goal of this paper is to present an efficient implementation of this algorithm for ternary graphs in the SAGE system, as well as an adaptation to fully resolved rooted phylogenetic networks on a given set of taxa., Comment: 16 pages

The path-difference metric is one of the oldest and most popular distances for the comparison of phylogenetic trees, but its statistical properties are still quite unknown. In this paper we compute the expected value under the Yule model of evolution of its square on the space of fully resolved rooted phylogenetic trees with n leaves. This complements previous work by Steel-Penny and Mir-Rossell\'o, who computed this mean value for fully resolved unrooted and rooted phylogenetic trees, respectively, under the uniform distribution., Comment: 10 pages, extended version of a paper submitted to Applied Mathematics Letter

One of the main applications of balance indices is in tests of null models of evolutionary processes. The knowledge of an exact formula for a statistic of a balance index, holding for any number n of leaves, is necessary in order to use this statistic in tests of this kind involving trees of any size. In this paper we obtain exact formulas for the variance under the Yule model of the Sackin index, the Colless index and the total cophenetic index of binary rooted phylogenetic trees with n leaves. We also obtain the covariance of the Sackin and the total cophenetic index., Comment: 32 pages. The final version will appear in the J. Comp. Biol. v2 covers the Colless index, which did not appear in v1

Several indices that measure the degree of balance of a rooted phylogenetic tree have been proposed so far in the literature. In this work we define and study a new index of this kind, which we call the total cophenetic index: the sum, over all pairs of different leaves, of the depth of their least common ancestor. This index makes sense for arbitrary trees, can be computed in linear time and it has a larger range of values and a greater resolution power than other indices like Colless' or Sackin's. We compute its maximum and minimum values for arbitrary and binary trees, as well as exact formulas for its expected value for binary trees under the Yule and the uniform models of evolution. As a byproduct of this study, we obtain an exact formula for the expected value of the Sackin index under the uniform model, a result that seems to be new in the literature., Comment: 24 pages, 2 figures, preliminary version presented at the JBI 2012

We compute an explicit formula for the expected value of the Colless index of a phylogenetic tree generated under the Yule model, and an explicit formula for the expected value of the Sackin index of a phylogenetic tree generated under the uniform model., Comment: 11 pages

Galled networks, directed acyclic graphs that model evolutionary histories with reticulation cycles containing only tree nodes, have become very popular due to both their biological significance and the existence of polynomial time algorithms for their reconstruction. In this paper we prove that Nakhleh's $m$ measure is a metric for this class of phylogenetic networks and hence it can be safely used to evaluate galled network reconstruction methods.

We establish a limit formula for the median of the distance between two leaves in a fully resolved unrooted phylogenetic tree with n leaves. More precisely, we prove that this median is equal, in the limit, to the square root of 4*ln(2)*n., Comment: 4 pages

The path-difference metric is one of the oldest distances for the comparison of fully resolved phylogenetic trees, but its statistical properties are still quite unknown. In this paper we compute the mean value of the square of the path-difference metric between two fully resolved rooted phylogenetic trees with $n$ leaves, under the uniform distribution. This complements previous work by Steel and Penny, who computed this mean value for fully resolved unrooted phylogenetic trees., Comment: 16 pages

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., Comment: 36 pages

Galled trees, evolutionary networks with isolated reticulation cycles, have appeared under several slightly different definitions in the literature. In this paper we establish the actual relationships between the main four such alternative definitions: namely, the original galled trees, level-1 networks, nested networks with nesting depth 1, and evolutionary networks with arc-disjoint reticulation cycles., Comment: 13 pages

In a previous work, we gave a metric on the class of semibinary tree-sibling time consistent phylogenetic networks that is computable in polynomial time; in particular, the problem of deciding if two networks of this kind are isomorphic is in P. In this paper, we show that if we remove the semibinarity condition above, then the problem becomes much harder. More precisely, we proof that the isomorphism problem for generic tree-sibling time consistent phylogenetic networks is polynomially equivalent to the graph isomorphism problem. Since the latter is believed to be neither in P nor NP-complete, the chances are that it is impossible to define a metric on the class of all tree-sibling time consistent phylogenetic networks that can be computed in polynomial time., Comment: 10 pages, 3 figures

We prove that Nakhleh's latest dissimilarity measure for phylogenetic networks is a metric on the classes of tree-child phylogenetic networks, of semi-binary time consistent tree-sibling phylogenetic networks, and of multi-labeled phylogenetic trees. We also prove that it distinguishes phylogenetic networks with different reduced versions. In this way, it becomes the dissimilarity measure for phylogenetic networks with the strongest separation power available so far., Comment: 15 pages

Hybridization networks are representations of evolutionary histories that allow for the inclusion of reticulate events like recombinations, hybridizations, or lateral gene transfers. The recent growth in the number of hybridization network reconstruction algorithms has led to an increasing interest in the definition of metrics for their comparison that can be used to assess the accuracy or robustness of these methods. In this paper we establish some basic results that make it possible the generalization to tree-child time consistent (TCTC) hybridization networks of some of the oldest known metrics for phylogenetic trees: those based on the comparison of the vectors of path lengths between leaves. More specifically, we associate to each hybridization network a suitably defined vector of `splitted' path lengths between its leaves, and we prove that if two TCTC hybridization networks have the same such vectors, then they must be isomorphic. Thus, comparing these vectors by means of a metric for real-valued vectors defines a metric for TCTC hybridization networks. We also consider the case of fully resolved hybridization networks, where we prove that simpler, `non-splitted' vectors can be used., Comment: 31 pages

Dissimilarity measures for (possibly weighted) phylogenetic trees based on the comparison of their vectors of path lengths between pairs of taxa, have been present in the systematics literature since the early seventies. But, as far as rooted phylogenetic trees goes, these vectors can only separate non-weighted binary trees, and therefore these dissimilarity measures are metrics only on this class. In this paper we overcome this problem, by splitting in a suitable way each path length between two taxa into two lengths. We prove that the resulting splitted path lengths matrices single out arbitrary rooted phylogenetic trees with nested taxa and arcs weighted in the set of positive real numbers. This allows the definition of metrics on this general class by comparing these matrices by means of metrics in spaces of real-valued $n\times n$ matrices. We conclude this paper by establishing some basic facts about the metrics for non-weighted phylogenetic trees defined in this way using $L^p$ metrics on these spaces of matrices., Comment: 26 pages, Supplementary Material available at http://bioinfo.uib.es/~recerca/phylotrees/nodal/

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. We present in this paper a distance measure on the class of 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 twofold: 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. 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 paper., Comment: 16 pages, 16 figures

We prove that Nakhleh's latest dissimilarity measure for phylogenetic networks separates distinguishable phylogenetic networks, and that a slight modification of it provides a true distance on the class of all phylogenetic networks., Comment: 9 pages

Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of evolutionary events acting at the population level, like recombination between genes, hybridization between lineages, and lateral gene transfer. While most phylogenetics tools implement a wide range of algorithms on phylogenetic trees, there exist only a few applications to work with phylogenetic networks, and there are no open-source libraries either. In order to improve this situation, we have developed a Perl package that relies on the BioPerl bundle and implements many algorithms on phylogenetic networks. We have also developed a Java applet that makes use of the aforementioned Perl package and allows the user to make simple experiments with phylogenetic networks without having to develop a program or Perl script by herself. The Perl package has been accepted as part of the BioPerl bundle. It can be downloaded from http://dmi.uib.es/~gcardona/BioInfo/Bio-PhyloNetwork.tgz. The web-based application is available at http://dmi.uib.es/~gcardona/BioInfo/. The Perl package includes full documentation of all its features., Comment: 5 pages

Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of non-treelike evolutionary events, like recombination, hybridization, or lateral gene transfer. In this paper, we present and study a new class of phylogenetic networks, called tree-child phylogenetic networks, where every non-extant species has some descendant through mutation. We provide an injective representation of these networks as multisets of vectors of natural numbers, their path multiplicity vectors, and we use this representation to define a distance on this class and to give an alignment method for pairs of these networks. To the best of our knowledge, they are respectively the first true distance and the first alignment method defined on a meaningful class of phylogenetic networks strictly extending the class of phylogenetic trees. 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, and they have been implemented as a Perl package and a Java applet, and they are available at http://bioinfo.uib.es/~recerca/phylonetworks/mudistance, Comment: 37 pages

Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of non-treelike evolutionary events, like recombination, hybridization, or lateral gene transfer. In a recent series of papers devoted to the study of reconstructibility of phylogenetic networks, Moret, Nakhleh, Warnow and collaborators introduced the so-called {tripartition metric for phylogenetic networks. In this paper we show that, in fact, this tripartition metric does not satisfy the separation axiom of distances (zero distance means isomorphism, or, in a more relaxed version, zero distance means indistinguishability in some specific sense) in any of the subclasses of phylogenetic networks where it is claimed to do so. We also present a subclass of phylogenetic networks whose members can be singled out by means of their sets of tripartitions (or even clusters), and hence where the latter can be used to define a meaningful metric., Comment: 26 pages, 9 figures

The relationship between two important problems in tree pattern matching, the largest common subtree and the smallest common supertree problems, is established by means of simple constructions, which allow one to obtain a largest common subtree of two trees from a smallest common supertree of them, and vice versa. These constructions are the same for isomorphic, homeomorphic, topological, and minor embeddings, they take only time linear in the size of the trees, and they turn out to have a clear algebraic meaning., Comment: 32 pages

The search for similarity and dissimilarity measures on phylogenetic trees has been motivated by the computation of consensus trees, the search by similarity in phylogenetic databases, and the assessment of clustering results in bioinformatics. The transposition distance for fully resolved phylogenetic trees is a recent addition to the extensive collection of available metrics for comparing phylogenetic trees. In this paper, we generalize the transposition distance from fully resolved to arbitrary phylogenetic trees, through a construction that involves an embedding of the set of phylogenetic trees with a fixed number of labeled leaves into a symmetric group and a generalization of Reidys-Stadler's involution metric for RNA contact structures. We also present simple linear-time algorithms for computing it., Comment: 15 pages

Kolmogorov complexity has inspired several alignment-free distance measures, based on the comparison of lengths of compressions, which have been applied successfully in many areas. One of these measures, the so-called Universal Similarity Metric (USM), has been used by Krasnogor and Pelta to compare simple protein contact maps, showing that it yielded good clustering on four small datasets. We report an extensive test of this metric using a much larger and representative protein dataset: the domain dataset used by Sierk and Pearson to evaluate seven protein structure comparison methods and two protein sequence comparison methods. One result is that Krasnogor-Pelta method has less domain discriminant power than any one of the methods considered by Sierk and Pearson when using these simple contact maps. In another test, we found that the USM based distance has low agreement with the CATH tree structure for the same benchmark of Sierk and Pearson. In any case, its agreement is lower than the one of a standard sequential alignment method, SSEARCH. Finally, we manually found lots of small subsets of the database that are better clustered using SSEARCH than USM, to confirm that Krasnogor-Pelta's conclusions were based on datasets that were too small., Comment: 11 pages; It replaces the former "The Universal Similarity Metric does not detect domain similarity." This version reports on more extensive tests

Compatibility of phylogenetic trees is the most important concept underlying widely-used methods for assessing the agreement of different phylogenetic trees with overlapping taxa and combining them into common supertrees to reveal the tree of life. The notion of ancestral compatibility of phylogenetic trees with nested taxa was introduced by Semple et al in 2004. In this paper we analyze in detail the meaning of this compatibility from the points of view of the local structure of the trees, of the existence of embeddings into a common supertree, and of the joint properties of their cluster representations. Our analysis leads to a very simple polynomial-time algorithm for testing this compatibility, which we have implemented and is freely available for download from the BioPerl collection of Perl modules for computational biology., Comment: Submitted

In this paper we introduce a fuzzy version of symport/antiport membrane systems. Our fuzzy membrane systems handle possibly inexact copies of reactives and their rules are endowed with threshold functions that determine whether a rule can be applied or not to a given set of objects, depending of the degree of accuracy of these objects to the reactives specified in the rule. We prove that these fuzzy membrane systems generate exactly the recursively enumerable finite-valued fuzzy sets of natural numbers., Comment: 20 pages, 0 figures

The measurement of the similarity of RNA secondary structures, and in general of contact structures, of a fixed length has several specific applications. For instance, it is used in the analysis of the ensemble of suboptimal secondary structures generated by a given algorithm on a given RNA sequence, and in the comparison of the secondary structures predicted by different algorithms on a given RNA molecule. It is also a useful tool in the quantitative study of sequence-structure maps. A way to measure this similarity is by means of metrics. In this paper we introduce a new class of metrics $d_{m}$, $m\geq 3$, on the set of all contact structures of a fixed length, based on their representation by means of edge ideals in a polynomial ring. These metrics can be expressed in terms of Hilbert functions of monomial ideals, which allows the use of several public domain computer algebra systems to compute them. We study some abstract properties of these metrics, and we obtain explicit descriptions of them for $m=3,4$ on arbitrary contact structures and for $m=5,6$ on RNA secondary structures., Comment: Presented at the Biomolecular Mathematics Special Session of the First Joint AMS-RSME Meeting (Sevilla, june 2003)

In this paper we model several simple biochemical operations on RNA molecules that modify their secondary structure by means of a suitable variation of Gro\ss e-Rhode's Algebra Transformation Systems., Comment: 10 pages

We compute explicitly several abstract metrics for RNA secondary structures defined by Reidys and Stadler., Comment: 6 pages