Bootstrap confidence levels for phylogenetic trees

Evolutionary trees are often estimated from DNA or RNA sequence data. How much confidence should we have in the estimated trees? In 1985, Felsenstein [Felsenstein, J. (1985) Evolution 39, 783–791] suggested the use of the bootstrap to answer this question. Felsenstein’s method, which in concept is a straightforward application of the bootstrap, is widely used, but has been criticized as biased in the genetics literature. This paper concerns the use of the bootstrap in the tree problem. We show that Felsenstein’s method is not biased, but that it can be corrected to better agree with standard ideas of confidence levels and hypothesis testing. These corrections can be made by using the more elaborate bootstrap method presented here, at the expense of considerably more computation.

Matchings and phylogenetic trees

This paper presents a natural coordinate system for phylogenetic trees using a correspondence with the set of perfect matchings in the complete graph. This correspondence produces a distance between phylogenetic trees, and a way of enumerating all trees in a minimal step order. It is useful in randomized algorithms because it enables moves on the space of trees that make random optimization strategies “mix” quickly. It also promises a generalization to intermediary trees when data are not decisive as to their choice of tree, and a new way of constructing Bayesian priors on tree space.

Convex polytopes and quantization of symplectic manifolds

Quantum mechanics associate to some symplectic manifolds M a quantum model Q(M), which is a Hilbert space. The space Q(M) is the quantum mechanical analogue of the classical phase space M. We discuss here relations between the volume of M and the dimension of the vector space Q(M). Analogues for convex polyhedra are considered.

Visualization of Cavitated Vessels in Winter and Refilled Vessels in Spring in Diffuse-Porous Trees by Cryo-Scanning Electron Microscopy1

Xylem cavitation in winter and recovery from cavitation in the spring were visualized in two species of diffuse-porous trees, Betula platyphylla var. japonica Hara and Salix sachalinensis Fr. Schm., by cryo-scanning electron microscopy after freeze-fixation of living twigs. Water in the vessel lumina of the outer three annual rings of twigs of B. platyphylla var. japonica and of S. sachalinensis gradually disappeared during the period from January to March, an indication that cavitation occurs gradually in these species during the winter. In April, when no leaves had yet expanded, the lumina of most of the vessels of both species were filled with water. Many vessel lumina in twigs of both species were filled with water during the period from the subsequent growth season to the beginning of the next winter. These observations indicate that recovery in spring occurs before the onset of transpiration and that water transport through twigs occurs during the subsequent growing season. We found, moreover, that vessels repeat an annual cycle of winter cavitation and spring recovery from cavitation for several years until irreversible cavitation occurs.

Bootstrap confidence levels for phylogenetic trees.

Evolutionary trees are often estimated from DNA or RNA sequence data. How much confidence should we have in the estimated trees? In 1985, Felsenstein [Felsenstein, J. (1985) Evolution 39, 783-791] suggested the use of the bootstrap to answer this question. Felsenstein's method, which in concept is a straightforward application of the bootstrap, is widely used, but has been criticized as biased in the genetics literature. This paper concerns the use of the bootstrap in the tree problem. We show that Felsenstein's method is not biased, but that it can be corrected to better agree with standard ideas of confidence levels and hypothesis testing. These corrections can be made by using the more elaborate bootstrap method presented here, at the expense of considerably more computation.

Hyperplane arrangements, interval orders, and trees.

A hyperplane arrangement is a finite set of hyperplanes in a real affine space. An especially important arrangement is the braid arrangement, which is the set of all hyperplanes xi - xj = 1, 1 trees. For instance, the number of labeled interval orders that can be obtained from n intervals I1,..., In of generic lengths is counted. There is also discussed an arrangement due to N. Linial whose number of regions is the number of alternating (or intransitive) trees, as defined by Gelfand, Graev, and Postnikov [Gelfand, I. M., Graev, M. I., and Postnikov, A. (1995), preprint]. Finally, a refinement is given, related to counting labeled trees by number of inversions, of a result of Shi [Shi, J.-Y. (1986), Lecture Notes in Mathematics, no. 1179, Springer-Verlag] that a certain deformation of the braid arrangement has (n + 1)n-1 regions.

Calculating the probability of multitaxon evolutionary trees: bootstrappers Gambit.

The reconstruction of multitaxon trees from molecular sequences is confounded by the variety of algorithms and criteria used to evaluate trees, making it difficult to compare the results of different analyses. A global method of multitaxon phylogenetic reconstruction described here, Bootstrappers Gambit, can be used with any four-taxon algorithm, including distance, maximum likelihood, and parsimony methods. It incorporates a Bayesian-Jeffreys'-bootstrap analysis to provide a uniform probability-based criterion for comparing the results from diverse algorithms. To examine the usefulness of the method, the origin of the eukaryotes has been investigated by the analysis of ribosomal small subunit RNA sequences. Three common algorithms (paralinear distances, Jukes-Cantor distances, and Kimura distances) support the eocyte topology, whereas one (maximum parsimony) supports the archaebacterial topology, suggesting that the eocyte prokaryotes are the closest prokaryotic relatives of the eukaryotes.

Hybrid convex combinations for IIR system identification.

The low complexity of IIR adaptive filters (AFs) is specially appealing to realtime applications but some drawbacks have been preventing their widespread use so far. For gradient based IIR AFs, adverse operational conditions cause convergence problems in system identification scenarios: underdamped and clustered poles, undermodelling or non-white input signals lead to error surfaces where the adaptation nearly stops on large plateaus or get stuck at sub-optimal local minima that can not be identified as such a priori. Furthermore, the non-stationarity in the input regressor brought by the filter recursivity and the approximations made by the update rules of the stochastic gradient algorithms constrain the learning step size to small values, causing slow convergence. In this work, we propose IIR performance enhancement strategies based on hybrid combinations of AFs that achieve higher convergence rates than ordinary IIR AFs while keeping the stability.

Trees as Tools in Environmental Improvement; An Analysis of the Contribution of Vegetation to Energy and Water Conservation in the Front Range of Colorado

The Denver metropolitan area is facing rapid population growth that increases the stress on already limited resources. Research and advanced computer modeling show that trees, especially those in urban areas, have significant environmental benefits. These benefits include air quality improvements, energy savings, greenhouse gas reduction, and possible water conservation. This Capstone Project applies statistical methods to analyze a small data set of residential homes and their energy and water consumption, as a function of their individual landscape. Results indicate that tree shade can influence water conservation, and that irrigation methods can be an influential factor as well. The Capstone is a preliminary analysis for future study to be performed by the Institute for Environmental Solutions in 2007.

Quantitative stability of linear infinite inequality systems under block perturbations with applications to convex systems

The original motivation for this paper was to provide an efficient quantitative analysis of convex infinite (or semi-infinite) inequality systems whose decision variables run over general infinite-dimensional (resp. finite-dimensional) Banach spaces and that are indexed by an arbitrary fixed set J. Parameter perturbations on the right-hand side of the inequalities are required to be merely bounded, and thus the natural parameter space is l ∞(J). Our basic strategy consists of linearizing the parameterized convex system via splitting convex inequalities into linear ones by using the Fenchel–Legendre conjugate. This approach yields that arbitrary bounded right-hand side perturbations of the convex system turn on constant-by-blocks perturbations in the linearized system. Based on advanced variational analysis, we derive a precise formula for computing the exact Lipschitzian bound of the feasible solution map of block-perturbed linear systems, which involves only the system’s data, and then show that this exact bound agrees with the coderivative norm of the aforementioned mapping. In this way we extend to the convex setting the results of Cánovas et al. (SIAM J. Optim. 20, 1504–1526, 2009) developed for arbitrary perturbations with no block structure in the linear framework under the boundedness assumption on the system’s coefficients. The latter boundedness assumption is removed in this paper when the decision space is reflexive. The last section provides the aimed application to the convex case.

Motzkin decomposition of closed convex sets via truncation

A nonempty set F is called Motzkin decomposable when it can be expressed as the Minkowski sum of a compact convex set C with a closed convex cone D. In that case, the sets C and D are called compact and conic components of F. This paper provides new characterizations of the Motzkin decomposable sets involving truncations of F (i.e., intersections of FF with closed halfspaces), when F contains no lines, and truncations of the intersection F̂ of F with the orthogonal complement of the lineality of F, otherwise. In particular, it is shown that a nonempty closed convex set F is Motzkin decomposable if and only if there exists a hyperplane H parallel to the lineality of F such that one of the truncations of F̂ induced by H is compact whereas the other one is a union of closed halflines emanating from H. Thus, any Motzkin decomposable set F can be expressed as F=C+D, where the compact component C is a truncation of F̂. These Motzkin decompositions are said to be of type T when F contains no lines, i.e., when C is a truncation of F. The minimality of this type of decompositions is also discussed.

On the stability of the Motzkin representation of closed convex sets

A set is called Motzkin decomposable when it can be expressed as the Minkowski sum of a compact convex set with a closed convex cone. This paper analyzes the continuity properties of the set-valued mapping associating to each couple (C,D) formed by a compact convex set C and a closed convex cone D its Minkowski sum C + D. The continuity properties of other related mappings are also analyzed.

Primal Attainment in Convex Infinite Optimization Duality

This article provides results guarateeing that the optimal value of a given convex infinite optimization problem and its corresponding surrogate Lagrangian dual coincide and the primal optimal value is attainable. The conditions ensuring converse strong Lagrangian (in short, minsup) duality involve the weakly-inf-(locally) compactness of suitable functions and the linearity or relative closedness of some sets depending on the data. Applications are given to different areas of convex optimization, including an extension of the Clark-Duffin Theorem for ordinary convex programs.

Comparative study of RPSALG algorithm for convex semi-infinite programming

The Remez penalty and smoothing algorithm (RPSALG) is a unified framework for penalty and smoothing methods for solving min-max convex semi-infinite programing problems, whose convergence was analyzed in a previous paper of three of the authors. In this paper we consider a partial implementation of RPSALG for solving ordinary convex semi-infinite programming problems. Each iteration of RPSALG involves two types of auxiliary optimization problems: the first one consists of obtaining an approximate solution of some discretized convex problem, while the second one requires to solve a non-convex optimization problem involving the parametric constraints as objective function with the parameter as variable. In this paper we tackle the latter problem with a variant of the cutting angle method called ECAM, a global optimization procedure for solving Lipschitz programming problems. We implement different variants of RPSALG which are compared with the unique publicly available SIP solver, NSIPS, on a battery of test problems.

New glimpses on convex infinite optimization duality

Given a convex optimization problem (P) in a locally convex topological vector space X with an arbitrary number of constraints, we consider three possible dual problems of (P), namely, the usual Lagrangian dual (D), the perturbational dual (Q), and the surrogate dual (Δ), the last one recently introduced in a previous paper of the authors (Goberna et al., J Convex Anal 21(4), 2014). As shown by simple examples, these dual problems may be all different. This paper provides conditions ensuring that inf(P)=max(D), inf(P)=max(Q), and inf(P)=max(Δ) (dual equality and existence of dual optimal solutions) in terms of the so-called closedness regarding to a set. Sufficient conditions guaranteeing min(P)=sup(Q) (dual equality and existence of primal optimal solutions) are also provided, for the nominal problems and also for their perturbational relatives. The particular cases of convex semi-infinite optimization problems (in which either the number of constraints or the dimension of X, but not both, is finite) and linear infinite optimization problems are analyzed. Finally, some applications to the feasibility of convex inequality systems are described.