Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel��s conjecture

A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on n leaves, sample sequences of length ??(log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than ${p^{\ast} = (\sqrt{2}-1)/2^{3/2}}$ , then the tree can be recovered from sequences of length O(log n). The value p* is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel??s conjecture was proven by the second author in the special case where the tree is ??balanced.?? The second author also proved that if all edges have mutation probability larger than p* then the length needed is n ^??(1). Here we show that Steel??s conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from O(log n)-length sequences when the mutation probabilities are discretized and less than p*. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.     

Non-impeding noisy-AND tree causal models over multi-valued variables

To specify a Bayesian network (BN), a conditional probability table (CPT), often of an effect conditioned on its n causes, must be assessed for each node. Its complexity is generally exponential in n. Noisy-OR and a number of extensions reduce the complexity to linear, but can only represent reinforcing causal interactions. Non-impeding noisy-AND (NIN-AND) trees are the first causal models that explicitly express reinforcement, undermining, and their mixture. Their acquisition has a linear complexity, in terms of both the number of parameters and the size of the tree topology. As originally proposed, however, they allow only binary effects and causes. This work generalizes binary NIN-AND tree models to multi-valued effects and causes. It is shown that the generalized NIN-AND tree models express reinforcement, undermining, and their mixture at multiple levels, relative to each active value of the effect. The model acquisition is still efficient. For binary variables, they degenerate into binary NIN-AND tree models. Hence, this contribution enables CPTs of discrete BNs of arbitrary variables (binary or multi-valued) to be specified efficiently through the intuitive concepts of reinforcement and undermining.     

An O(n2) simplex algorithm for a class of linear programs with tree structure

In connection with the optimal design of centralized circuit-free networks linear 0–1 programming problems arise which are related to rooted trees. For each problem the variables correspond to the edges of a given rooted tree T. Each path from a leaf to the root of T, together with edge weights, defines a linear constraint, and a global linear objective is to be maximized. We consider relaxations of such problems where the variables are not restricted to 0 or 1 but are allowed to vary continouosly between these bounds. The values of the optimal solutions of such relaxations may be used in a branch and bound procedure for the original 0–1 problem. While in [10] a primal algorithm for these relaxations is discussed, in this paper, we deal with the dual linear program and present a version of the simplex algorithm for its solution which can be implemented to run in time O(n²). For balanced trees T this time can be reduced to O(n log n).     

On the maximum size of minimal definitive quartet sets

In this paper, we investigate a problem concerning quartets; a quartet is a particular kind of tree on four leaves. Loosely speaking, a set of quartets is said to be ‘definitive’ if it completely encapsulates the structure of some larger tree, and ‘minimal’ if it contains no redundant information. Here, we address the question of how large a minimal definitive quartet set on n leaves can be, showing that the maximum size is at least 2n−8 for all n≥4. This is an enjoyable problem to work on, and we present a pretty construction, which employs symmetry.     

Uniform election in trees and polyominoids

Election is a classical paradigm in distributed algorithms. This paper aims to design and analyze a distributed algorithm choosing a node in a graph which models a network. In case the graph is a tree, a simple schema of algorithm acts as follows: it removes leaves until the graph is reduced to a single vertex; the elected one. In Métivier et al. (2003) [7], the authors studied a randomized variant of this schema which gives the same probability of being elected to each node of the tree. They conjectured that the expected election duration of this algorithm is O(ln(n)) where n denotes the size of the tree, and asked whether it is possible to use the same algorithm to obtain a fair election in other classes of graphs.In this paper, we prove their conjecture. We then introduce a new structure called polyominoid graphs. We show how a spanning tree for these graphs can be computed locally so that our algorithm, applied to this spanning tree, gives a uniform election algorithm on polyominoids.     

Treed Regression

Abstract

Given a data set consisting of n observations on p independent variables and a single dependent variable, treed regression creates a binary tree with a simple linear regression function at each of the leaves. Each node of the tree consists of an inequality condition on one of the independent variables. The tree is generated from the training data by a recursive partitioning algorithm. Treed regression models are more parsimonious than CART models because there are fewer splits. Additionally, monotonicity in some or all of the variables can be imposed.     

Electrical and magnetic properties of 3d-transition metal vanadates

The electrical and magnetic properties of vanadates of the general formula (MO) _n .V₂O₅, where M=Mn, Co, Ni, Cu and Zn, andn=1, 2 and 3, are discussed. Conduction in these materials occurs due to small deviations from the stoichiometric composition in the form of anion-(n-type) or cation—(p-type) vacancies. The mechanism of electrical transport is of a thermally activated hopping of charge carriers on equivalent cation lattice sites. It has been found that the meta vanadates (n=1) are alln-type while the pyro—(n=2) and ortho—(n=3) compounds of Mn, Co and Ni arep-type; but Cu and Zn analogues remainn-type only. The vanadates obey Curie-Weiss law at 80–340 K. The effective magnetic moments for MV₂O₆ are nearly the same as spin only values for the magnetic M²⁺ ions, and diminish with increasing MO contents. The predominant exchange interactions are the weak 90° MOM super-exchange and M—O—O—M super-super exchange. The Weiss constant is negative (antiferro-) for all the compounds except Co₃V₂O₈ which has a positive (ferro-) value. Cooperative phenomena, if any, have not been observed in this temperature range.     

Finiteness for the k-factor model and chirality varieties

This paper deals with two families of algebraic varieties arising from applications. First, the k-factor model in statistics, consisting of n×n covariance matrices of n observed Gaussian random variables that are pairwise independent given k hidden Gaussian variables. Second, chirality varieties inspired by applications in chemistry. A point in such a chirality variety records chirality measurements of all k-subsets among an n-set of ligands. Both classes of varieties are given by a parameterisation, while for applications having polynomial equations would be desirable. For instance, such equations could be used to test whether a given point lies in the variety. We prove that in a precise sense, which is different for the two classes of varieties, these equations are finitely characterisable when k is fixed and n grows.     

Shelling Coxeter-like complexes and sorting on trees

In their work on ‘Coxeter-like complexes’, Babson and Reiner introduced a simplicial complex ΔT associated to each tree T on n nodes, generalizing chessboard complexes and type A Coxeter complexes. They conjectured that ΔT is (n−b−1)-connected when the tree has b leaves. We provide a shelling for the (n−b)-skeleton of ΔT, thereby proving this conjecture. In the process, we introduce notions of weak order and inversion functions on the labellings of a tree T which imply shellability of ΔT, and we construct such inversion functions for a large enough class of trees to deduce the aforementioned conjecture and also recover the shellability of chessboard complexes Mm,n with n?2m−1. We also prove that the existence or nonexistence of an inversion function for a fixed tree governs which networks with a tree structure admit greedy sorting algorithms by inversion elimination and provide an inversion function for trees where each vertex has capacity at least its degree minus one.     

Gene tree correction for reconciliation and species tree inference: Complexity and algorithms

Reconciliation consists in mapping a gene tree T into a species tree S, and explaining the incongruence between the two as evidence for duplication, loss and other events shaping the gene family represented by the leaves of T. When S is unknown, the Species Tree Inference Problem is to infer, from a set of gene trees, a species tree leading to a minimum reconciliation cost. As reconciliation is very sensitive to errors in T, gene tree correction prior to reconciliation is a fundamental task. In this paper, we investigate the complexity of four different combinatorial approaches for deleting misplaced leaves from T. First, we consider two problems (Minimum Leaf Removal and Minimum Species Removal) related to the reconciliation of T with a known species tree S. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) so that T is “MD-consistent” with S. Second, we consider two problems (Minimum Leaf Removal Inference and Minimum Species Removal Inference) related to species tree inference. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) from T so that there exists a species tree S such that T is MD-consistent with S. We prove that Minimum Leaf Removal and Minimum Species Removal are APX-hard, even when each label has at most two occurrences in the input gene tree, and we present fixed-parameter algorithms for the two problems. We prove that Minimum Leaf Removal Inference is not only NP-hard, but also W[2]-hard and inapproximable within factor $c\ln n$, where n is the number of leaves in the gene tree. Finally, we show that Minimum Species Removal Inference is NP-hard and W[2]-hard, when parameterized by the size of the solution, that is the minimum number of species removals.     

An optimal contour algorithm for iso-oriented rectangles

Given a set of n iso-oriented rectangles in 2-space we describe an algorithm which determines the contour of their union in O(n log n + p) time and O(n + p) space, where p is the number of edges in the contour. This performance is time-optimal. The space requirements are the same as in the best previously known algorithm. We achieve this by introducing a new data structure, the contracted segment tree, which is a non-trivial modification of the well known segment tree. If only the pieces of the contour are to be reported then this approach yields a time- and space-optimal algorithm.     

On the degree distribution of the nodes in increasing trees

Simple families of increasing trees can be constructed from simply generated tree families, if one considers for every tree of size n all its increasing labellings, i.e., labellings of the nodes by distinct integers of the set {1,…,n} in such a way that each sequence of labels along any branch starting at the root is increasing. Three such tree families are of particular interest: recursive trees, plane-oriented recursive trees and binary increasing trees. We study the quantity degree of node j in a random tree of size n and give closed formulae for the probability distribution and all factorial moments for those subclass of tree families, which can be constructed via a tree evolution process. Furthermore limiting distribution results of this parameter are given, which completely characterize the phase change behavior depending on the growth of j compared to n.     

On-line Construction of Two-Dimensional Suffix Trees

We say that a data structure is builton-lineif, at any instant, we have the data structure corresponding to the input we have seen up to that instant. For instance, consider the suffix tree of a stringx[1, n]. An algorithm building iton-lineis such that, when we have read the firstisymbols ofx[1, n], we have the suffix tree forx[1, i]. We present a new technique, which we refer to asimplicit updates, based on which we obtain: (a) an algorithm for theon-lineconstruction of the Lsuffix tree of ann×nmatrixA—this data structure is the two-dimensional analog of the suffix tree of a string; (b) simple algorithms implementing primitive operations forLZ1-typeon-line losslessimage compression methods. Those methods, recently introduced by Storer, are generalizations ofLZ1-typecompression methods for strings. For the problem in (a), we get nearly an order of magnitude improvement over algorithms that can be derived from known techniques. For the problem in (b), we do not get an asymptotic speed-up with respect to what can be done with known techniques; rather we show that our algorithms are a natural support for the primitive operations. This may lead to faster implementations of those primitive operations. To the best of our knowledge, our technique is the first one that effectively addresses problems related to theon-lineconstruction of two-dimensional suffix trees.     

The pos/neg-weighted 2-medians in balanced trees with subtree-shaped customers

This paper deals with the pos/neg-weighted p-median problem on tree graphs where all customers are modeled as subtrees. We present a polynomial algorithm for the 2-median problem on an arbitrary tree. Then we improve the time complexity to O(n log n) for the problem on a balanced tree, where n is the number of the vertices in the tree.     

Extended formulations for the cardinality constrained subtree of a tree problem

Given a tree with n nodes, we consider the problem of finding the most profitable subtree of that tree with at most K nodes which is known as the Cardinality Subtree of a Tree Problem. We present a new exact linear extended formulation with O(nK) two-indexed variables and O(nK) constraints.     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

Minimum broadcast tree decompositions

Recursive constructions for decomposing the complete directed graph D_n into minimum broadcast trees of order n are given, thereby showing the existence of such decompositions for all n. Such decompositions can be used for a routing system in a network where every participant has the ability to broadcast a message to the group; as each arc is used in only one tree, a participant’s further actions upon receipt of a message depend only on its sender, and so all routing information can be stored locally rather than in the message itself.     

Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees

This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(r_vnlogn) time where the parameter r_v is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang.     

Efficient algorithms for a family of matroid intersection problems

Consider a matroid where each element has a real-valued cost and a color, red or green; a base is sought that contains q red elements and has smallest possible cost. An algorithm for the problem on general matroids is presented, along with a number of variations. Its efficiency is demonstrated by implementations on specific matroids. In all cases but one, the running time matches the best-known algorithm for the problem without the red element constraint: On graphic matroids, a smallest spanning tree with q red edges can be found in time O(n log n) more than what is needed to find a minimum spanning tree. A special case is finding a smallest spanning tree with a degree constraint; here the time is only O(m + n) more than that needed to find one minimum spanning tree. On transversal and matching matroids, the time is the same as the best-known algorithms for a minimum cost base. This also holds for transversal matroids for convex graphs, which model a scheduling problem on unit-length jobs with release times and deadlines. On partition matroids, a linear-time algorithm is presented. Finally an algorithm related to our general approach finds a smallest spanning tree on a directed graph, where the given root has a degree constraint. Again the time matches the best-known algorithm for the problem without the red element (i.e., degree) constraint.     

The Hamiltonian problem on distance-hereditary graphs

In this paper, we first present an O(n+m)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G, respectively. This algorithm is faster than the previous best known algorithm for the problem which takes O(n²) time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(logn) time using O((n+m)/logn) processors on an EREW PRAM.