Search

We study the behavior of phylogenetic tree shapes in the tropical geometric interpretation of tree space. Tree shapes are formally referred to as tree topologies; a tree topology can also be thought of as a tree combinatorial type, which is given by the tree’s branching configuration and leaf labeling. We use the tropical line segment as a framework to define notions of variance as well as invariance of tree topologies: we provide a combinatorial search theorem that describes all tree topologies occurring along a tropical line segment, as well as a setting under which tree topologies do not change along a tropical line segment. Our study is motivated by comparison to the moduli space endowed with a geodesic metric proposed by Billera, Holmes, and Vogtmann (referred to as BHV space); we consider the tropical geometric setting as an alternative framework to BHV space for sets of phylogenetic trees. We give an algorithm to compute tropical line segments which is lower in computational complexity than the fastest method currently available for BHV geodesics and show that its trajectory behaves more subtly: while the BHV geodesic traverses the origin for vastly different tree topologies, the tropical line segment bypasses it.

In the fall of 2009 and in the spring of 2012, supported by the National Institute of General Medical Sciences (NIGMS) in the National Institutes of Health (NIH), we designed a course “Phylogenetic...

Evolutionary hypotheses provide important underpinnings of biological and medical sciences, and comprehensive, genome-wide understanding of evolutionary relationships among organisms are needed to test and refine such hypotheses. Theory and empirical evidence clearly indicate that phylogenies (trees) of different genes (loci) should not display precisely matching topologies. The main reason for such phylogenetic incongruence is reticulated evolutionary history of most species due to meiotic sexual recombination in eukaryotes, or horizontal transfers of genetic material in prokaryotes. Nevertheless, many genes should display topologically related phylogenies, and should group into one or more (for genetic hybrids) clusters in poly-dimensional “tree space”. Unusual evolutionary histories or effects of selection may result in “outlier” genes with phylogenies that fall outside the main distribution(s) of trees in tree space. We present a new phylogenomic method, CURatio , which uses ratios of total branch lengths in gene trees to help identify phylogenetic outliers in a given set of ortholog groups from multiple genomes. An advantage of CURatio over other methods is that genes absent from and/or duplicated in some genomes can be included in the analysis. We conducted a simulation study under the coalescent model, and showed that, given sufficient species depth and topological difference, these ratios are significantly higher for the “outlier” gene phylogenies. Also, we applied CURatio to a set of annotated genomes of the fungal family, Clavicipitaceae, and identified alkaloid biosynthesis genes as outliers, probably due to a history of duplication and loss. The source code is available at https://github.com/QiwenKang/CURatio , and the empirical data set for Clavicipitaceae and simulated data set are available at Mendeley https://data.mendeley.com/datasets/mrxts7wjrr/1 .

Uncrewed autonomous vehicles (UAVs) have made significant contributions to reconnaissance and surveillance missions in past US military campaigns. As the prevalence of UAVs increases, there has also been improvements in counter-UAV technology that makes it difficult for them to successfully obtain valuable intelligence within an area of interest. Hence, it has become important that modern UAVs can accomplish their missions while maximizing their chances of survival. In this work, we specifically study the problem of identifying a short path from a designated start to a goal, while collecting all rewards and avoiding adversaries that move randomly on the grid. We also provide a possible application of the framework in a military setting, that of autonomous casualty evacuation. We present a comparison of three methods to solve this problem: namely we implement a Deep Q-Learning model, an ε-greedy tabular Q-Learning model, and an online optimization framework. Our computational experiments, designed using simple grid-world environments with random adversaries showcase how these approaches work and compare them in terms of performance, accuracy, and computational time. R.Y. is partially supported by NSF DMS 1916037 and Consortium for Robotics and Unmanned Systems Education and Research (CRUSER). NSF DMS 1916037 Consortium for Robotics and Unmanned Systems Education and Research (CRUSER)

Background The detailed complexity of triceps brachii insertional footprint continues to challenge surgeons as evidenced by continued reports of triceps-associated complications following elbow procedures. The purpose of this study is to describe the three-dimensional footprint of the triceps brachii at its olecranon insertion at the elbow. Methods 22 cadaveric elbows were dissected leaving only the distal insertion of the triceps intact. The insertion was defined and probed with a three-dimensional digitizer to create a digital three-dimensional footprint allowing width, height, and surface area of the footprint to be recorded relative to the bare area. The insertional soft tissues of tendon versus muscle along with the shape of the footprints were qualitatively described. Results The mean width and surface area of the lateral segment was greater in males than in females (30.07 mm vs. 24.37 mm, p = 0.0339 and 282.1 mm vs. 211. 56 mm, p = 0.0181, respectively). No other statistically significant differences between the sexes were noted. The triceps insertional footprint was “crescent-shaped” and consisted of three regions: central tendon, medial muscular extension, and lateral muscular extension. Discussion These findings can help explain the importance of avoiding these muscular structures during triceps-off approaches and provides the framework for future clinical studies. Clinical Relevance: Basic Science, anatomy study, cadaver dissection.

Stephen Fienberg (1942-2016) was a statistician whose career has been an inspiration for the engagement of statistics with social and scientific issues, and it is in this spirit that he helped steer algebraic statistics toward more of a mainstream. Many of his favorite topics in the area are covered in this special issue. We are grateful to all authors for contributing to this volume to honor him and his influence on the field. During the preparation of this issue, we also learned about the tragic killing of his widow, Joyce Fienberg, in the Tree of Life Synagogue in Pittsburgh. This issue is dedicated to their memory.

Support Vector Machines (SVMs) are one of the most popular supervised learning models to classify using a hyperplane in an Euclidean space. Similar to SVMs, tropical SVMs classify data points using a tropical hyperplane under the tropical metric with the max-plus algebra. In this paper, first we show generalization error bounds of tropical SVMs over the tropical projective torus. While the generalization error bounds attained via Vapnik-Chervonenkis (VC) dimensions in a distribution-free manner still depend on the dimension, we also show numerically and theoretically by extreme value statistics that the tropical SVMs for classifying data points from two Gaussian distributions as well as empirical data sets of different neuron types are fairly robust against the curse of dimensionality. Extreme value statistics also underlie the anomalous scaling behaviors of the tropical distance between random vectors with additional noise dimensions. Finally, we define tropical SVMs over a function space with the tropical metric., To appear in Neural Networks 2022+

Motivation Due to new technology for efficiently generating genome data, machine learning methods are urgently needed to analyze large sets of gene trees over the space of phylogenetic trees. However, the space of phylogenetic trees is not Euclidean, so ordinary machine learning methods cannot be directly applied. In 2019, Yoshida et al. introduced the notion of tropical principal component analysis (PCA), a statistical method for visualization and dimensionality reduction using a tropical polytope with a fixed number of vertices that minimizes the sum of tropical distances between each data point and its tropical projection. However, their work focused on the tropical projective space rather than the space of phylogenetic trees. We focus here on tropical PCA for dimension reduction and visualization over the space of phylogenetic trees. Results Our main results are 2-fold: (i) theoretical interpretations of the tropical principal components over the space of phylogenetic trees, namely, the existence of a tropical cell decomposition into regions of fixed tree topology; and (ii) the development of a stochastic optimization method to estimate tropical PCs over the space of phylogenetic trees using a Markov Chain Monte Carlo approach. This method performs well with simulation studies, and it is applied to three empirical datasets: Apicomplexa and African coelacanth genomes as well as sequences of hemagglutinin for influenza from New York. Availability and implementation Dataset: http://polytopes.net/Data.tar.gz. Code: http://polytopes.net/tropica_MCMC_codes.tar.gz. Supplementary information Supplementary data are available at Bioinformatics online.

We study the geometry of metrics and convexity structures on the space of phylogenetic trees, which is here realized as the tropical linear space of all \ ultrametrics. The ${\rm CAT}(0)$-metric of Billera-Holmes-Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the Owen-Provan algorithm, geodesic triangles are complicated. We show that the dimension of such a triangle can be arbitrarily high. Tropical convexity and the tropical metric behave better. They exhibit properties desirable for geometric statistics, such as geodesics of small depth., Comment: 21 pages, 5 figures; Theorem 13 is now proved in all dimensions

Logistic regression is one of the most popular models to classify in data science, and in general, it is easy to use. However, in order to conduct a goodness-of-fit test, we cannot apply asymptotic methods if we have sparse datasets. In the case, we have to conduct an exact conditional inference via a sampler, such as Markov Chain Monte Carlo (MCMC) or Sequential Importance Sampling (SIS). In this chapter, the authors investigate the rejection rate of the SIS procedure on a multiple logistic regression models with categorical covariates. Using tools from algebra, they show that in general SIS can have a very high rejection rate even though we apply Linear Integer Programming (IP) to compute the support of the marginal distribution for each variable. More specifically, the semigroup generated by the columns of the design matrix for a multiple logistic regression has infinitely many “holes.” They end with application of a hybrid scheme of MCMC and SIS to NUN study data on Alzheimer disease study.

Introduction: The aim of our study was to examine both age and gender-related alterations in collagen expression of the transverse carpal ligament (TCL) in patients with idiopathic carpal tunnel syndrome (CTS). Methods: Resected TCLs were collected from 10 patients undergoing open carpal tunnel decompression. These were randomly divided equally into two groups of five patients, with equal numbers of men (average age 49.6) and women (average age 57.4). Histological staining [Hematoxylin & eosin and Picrosirius red (PSR)] and Western blot analysis were performed on the resected tissue. Results: Data from the histological analysis showed a 73% increase in fibroblast cell densities in the TCL specimens from the CTS patients. The PSR staining-polarization microscopic and immunoblot analysis data shows that men have significantly increased collagen I and decreased collagen III (P ˂ 0.05) compared to women. An age-related decline was observed in the expression of collagen I in both sexes, and the ratio of collagens III to I was significantly increased (P ˂ 0.05) in women compared to men. The major component of the TCL in both sexes was found to be Collagen type VI. Levels of collagens II, V and X were also elevated to lesser extents. Discussion: Our data enhances the understanding of collagen alterations in the transverse carpal ligament in CTS. Collagens I and III are significantly elevated, especially in males, while other collagen isoforms, II, V, VI, and X, are also up-regulated. Moreover, there appears to be a general decrease in the up-regulation of collagen levels as a function of advancing age.

For a graph G with p vertices the closed convex cone S ⪰ 0 ( G ) consists of all real positive semidefinite p × p matrices whose sparsity pattern is given by G, that is, those matrices with zeros in the off-diagonal entries corresponding to nonedges of G. The extremal rays of this cone and their associated ranks have applications to matrix completion problems, maximum likelihood estimation in Gaussian graphical models in statistics, and Gauss elimination for sparse matrices. While the maximum rank of an extremal ray in S ⪰ 0 ( G ) , known as the sparsity order of G, has been characterized for different classes of graphs, we here study all possible extremal ranks of S ⪰ 0 ( G ) . We investigate when the geometry of the ( ± 1 ) -cut polytope of G yields a polyhedral characterization of the set of extremal ranks of S ⪰ 0 ( G ) . For a graph G without K 5 minors, we show that appropriately chosen normal vectors to the facets of the ( ± 1 ) -cut polytope of G specify the off-diagonal entries of extremal matrices in S ⪰ 0 ( G ) . We also prove that for appropriately chosen scalars the constant term of the linear equation of each facet-supporting hyperplane is the rank of its corresponding extremal matrix in S ⪰ 0 ( G ) . Furthermore, we show that if G is series-parallel then this gives a complete characterization of all possible extremal ranks of S ⪰ 0 ( G ) . Consequently, the sparsity order problem for series-parallel graphs can be solved in terms of polyhedral geometry.

In order to conduct a statistical analysis on a given set of phylogenetic gene trees, we often use a distance measure between two trees. In a statistical distance-based method to analyze discordance between gene trees, it is a key to decide "biological meaningful" and "statistically well-distributed" distance between trees. Thus, in this paper, we study the distributions of the three tree distance metrics: the edge difference, the path difference, and the precise $K$ interval cospeciation distance, between two trees: first, we focus on distributions of the three tree distances between two random unrooted trees with $n$ leaves ($n \geq 4$); and then we focus on the distributions the three tree distances between a fixed rooted species tree with $n$ leaves and a random gene tree with $n$ leaves generated under the coalescent process with given the species tree. We show some theoretical results as well as simulation study on these distributions., 18 pages, 11 figures

At the present time it is often stated that the maximum likelihood or the Bayesian method of phylogenetic construction is more accurate than the neighbor joining (NJ) method. Our computer simulations, however, have shown that the converse is true if we use p distance in the NJ procedure and the criterion of obtaining the true tree (Pc expressed as a percentage) or the combined quantity (c) of a value of Pc and a value of Robinson-Foulds' average topological error index (dT). This c is given by Pc (1 - dT/dTmax) = Pc (m - 3 - dT/2)/(m - 3), where m is the number of taxa used and dTmax is the maximum possible value of dT, which is given by 2(m - 3). This neighbor joining method with p distance (NJp method) will be shown generally to give the best data-fit model. This c takes a value between 0 and 1, and a tree-making method giving a high value of c is considered to be good. Our computer simulations have shown that the NJp method generally gives a better performance than the other methods and therefore this method should be used in general whether the gene is compositional or it contains the mosaic DNA regions or not.

Advances in modern genomics have allowed researchers to apply phylogenetic analyses on a genome-wide scale. While large volumes of genomic data can be generated cheaply and quickly, data missingness is a non-trivial and somewhat expected problem. Since the available information is often incomplete for a given set of genetic loci and individual organisms, a large proportion of trees that depict the evolutionary history of a single genetic locus, called gene trees, fail to contain all individuals. Data incompleteness causes difficulties in data collection, information extraction, and gene tree inference. Furthermore, identifying outlying gene trees, which can represent horizontal gene transfers, gene duplications, or hybridizations, is difficult when data is missing from the gene trees. The typical approach is to remove all individuals with missing data from the gene trees, and focus the analysis on individuals whose information is fully available – a huge loss of information. In this work, we propose and design an optimization-based imputation approach to infer the missing distances between leaves in a set of gene trees via a mixed integer non-linear programming model. We also present a new research pipeline, imPhy , that can (i) simulate a set of gene trees with leaves randomly missing in each tree, (ii) impute the missing pairwise distances in each gene tree, (iii) reconstruct the gene trees using the Neighbor Joining (NJ) and Unweighted Pair Group Method with Arithmetic Mean (UPGMA) methods, and (iv) analyze and report the efficiency of the reconstruction. To impute the missing leaves, we employ our newly proposed non-linear programming framework, and demonstrate its capability in reconstructing gene trees with incomplete information in both simulated and empirical datasets. In the empirical datasets apicomplexa and lungfish , our imputation has very small normalized mean square errors, even in the extreme case where 50 percent of the individuals in each gene tree are missing. Data, software, and user manuals can be found at https://github.com/yasuiniko/imPhy .

The question whether there exists an integral solution to the system of linear equations with non-negative constraints, $A\x = \b, \, \x \ge 0$, where $A \in \Z^{m\times n}$ and ${\mathbf b} \in \Z^m$, finds its applications in many areas, such as operation research, number theory and statistics. In order to solve this problem, we have to understand the semigroup generated by the columns of the matrix $A$ and the structure of the "holes" which are the difference between the semigroup generated by the columns of the matrix $A$ and its saturation. In this paper, we discuss the implementation of an algorithm by Hemmecke, Takemura, and Yoshida that computes the set of holes of a semigroup, % generated by the columns of $A$ and we discuss applications to problems in combinatorics. Moreover, we compute the set of holes for the common diagonal effect model, and we show that the $n$th linear ordering polytope has the integer-decomposition property for $n\leq 7$. The software is available at \url{http://ehrhart.math.fu-berlin.de/People/fkohl/HASE/}.

Principal component analysis is a widely-used method for the dimensionality reduction of a given data set in a high-dimensional Euclidean space. Here we define and analyze two analogues of principal component analysis in the setting of tropical geometry. In one approach, we study the Stiefel tropical linear space of fixed dimension closest to the data points in the tropical projective torus; in the other approach, we consider the tropical polytope with a fixed number of vertices closest to the data points. We then give approximative algorithms for both approaches and apply them to phylogenetics, testing the methods on simulated phylogenetic data and on an empirical dataset of Apicomplexa genomes., 28 pages

Motivation: Although the majority of gene histories found in a clade of organisms are expected to be generated by a common process (e.g. the coalescent process), it is well known that numerous other coexisting processes (e.g. horizontal gene transfers, gene duplication and subsequent neofunctionalization) will cause some genes to exhibit a history distinct from those of the majority of genes. Such ‘outlying’ gene trees are considered to be biologically interesting, and identifying these genes has become an important problem in phylogenetics. Results: We propose and implement kdetrees, a non-parametric method for estimating distributions of phylogenetic trees, with the goal of identifying trees that are significantly different from the rest of the trees in the sample. Our method compares favorably with a similar recently published method, featuring an improvement of one polynomial order of computational complexity (to quadratic in the number of trees analyzed), with simulation studies suggesting only a small penalty to classification accuracy. Application of kdetrees to a set of Apicomplexa genes identified several unreliable sequence alignments that had escaped previous detection, as well as a gene independently reported as a possible case of horizontal gene transfer. We also analyze a set of Epichloë genes, fungi symbiotic with grasses, successfully identifying a contrived instance of paralogy. Availability and implementation: Our method for estimating tree distributions and identifying outlying trees is implemented as the R package kdetrees and is available for download from CRAN. Contact: ruriko.yoshida@uky.edu Supplementary information: Supplementary Data are available at Bioinformatics online.

On March 11, 2011, Japan was struck by the Great East Japan earthquake followed by a 23-foot tsunami, which crippled the Fukushima Daiichi nuclear plant. Because of a lack of plans for livestock evacuation in the case of a nuclear power plant accident, local farmers in the Fukushima exclusion zone had significant losses. Development of a rigorous and mathematical formulation of an evacuation plan for livestock in a case of disasters is essential for producers to lessen the financial and emotional impacts. Thus, we propose two mathematical models for evacuation plan for livestock in the area around a nuclear power plant using integer programming over networks. Since solving an evacuation problem on a time dynamic network is NP-hard, we propose algorithms to estimate an optimal solution for our problem. The methods and models discussed herein apply not only to nuclear plant related disasters, but also to a variety of other emergencies.

Most biological data are multidimensional, posing a major challenge to human comprehension and computational analysis. Principal component analysis is the most popular approach to rendering two- or three-dimensional representations of the major trends in such multidimensional data. The problem of multidimensionality is acute in the rapidly growing area of phylogenomics. Evolutionary relationships are represented by phylogenetic trees, and very typically a phylogenomic analysis results in a collection of such trees, one for each gene in the analysis. Principal component analysis offers a means of quantifying variation and summarizing a collection of phylogenies by dimensional reduction. However, the space of all possible phylogenies on a fixed set of species does not form a Euclidean vector space, so principal component analysis must be reformulated in the geometry of tree-space, which is a CAT(0) geodesic metric space. Previous work has focused on construction of the first principal component, or principal geodesic. Here we propose a geometric object which represents a $k$-th order principal component: the locus of the weighted Fr\'echet mean of $k+1$ points in tree-space, where the weights vary over the standard $k$-dimensional simplex. We establish basic properties of these objects, in particular that locally they generically have dimension $k$, and we propose an efficient algorithm for projection onto these surfaces. Combined with a stochastic optimization algorithm, this projection algorithm gives a procedure for constructing a principal component of arbitrary order in tree-space. Simulation studies confirm these algorithms perform well, and they are applied to data sets of Apicomplexa gene trees and the African coelacanth genome. The results enable visualizations of slices of tree-space, revealing structure within these complex data sets., Comment: 26 pages, 5 figures

In a metric space, the Fermat-Weber points of a sample are statistics to measure the central tendency of the sample and it is well-known that the Fermat-Weber point of a sample is not necessarily unique in the metric space. We investigate the computation of Fermat-Weber points under the tropical metric on the quotient space $\mathbb{R}^{n} \!/ \mathbb{R} {\bf 1}$ with a fixed $n \in \mathbb{N}$, motivated by its application to the space of equidistant phylogenetic trees with $N$ leaves (in this case $n=\binom{N}{2}$) realized as the tropical linear space of all ultrametrics. We show that the set of all tropical Fermat-Weber points of a finite sample is always a classical convex polytope, and we present a combinatorial formula for a key value associated to this set. We identify conditions under which this set is a singleton. We apply numerical experiments to analyze the set of the tropical Fermat-Weber points within a space of phylogenetic trees. We discuss the issues in the computation of the tropical Fermat-Weber points., 20 Pages, 2 figures. To appear in SIAM Journal on Discrete Mathematics

Phylogenetic trees are mathematical objects which summarize the most recent common ancestor relationships between a given set of organisms. There is often a need to quantify the degree of similarity or discordance between two proposed trees. For instance, a person may be interested in knowing whether the phylogenetic trees reconstructed from two distinct sequence alignments are truly different, or if the differences are so minor as to be attributable only to statistical variation. In this article we summarize several of the most widely known methods for defining distances between phylogenetic trees, and provide examples of the calculations when feasible.