Source author record

Ruriko Yoshida

Ruriko Yoshida appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

22works
10topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

22 published item(s)

preprint2026arXiv

Phylogenetic Tree Inference with Tropical Axial Attention

In this work, we introduce a Tropical Axial Attention neural reasoning architecture that replaces vanilla softmax dot-product attention with max-plus operators, inducing a piecewise-linear structure aligned with dynamic programming formulations. From multi-species sequence alignments, our model learns all possible pairwise distances and is trained using a combination of $\ell_1$ and tropical symmetric distance metric losses with an ultrametric violation penalty. We leverage the well known isomorphic relationship between the space of all phylogenetic trees with $n$ species and tropical Grassmannian to show that tropical attention provides a natural geometric framework for phylogenetic inference. On empirical $DS1-DS11$ alignments, where true trees are unknown, the tropical model produces distance matrices that are substantially closer to their BME-induced tree metrics than the baseline models. These results suggest that tropical attention is a useful geometric inductive bias for neural phylogenetic inference, especially under distribution shift and when tree-metric consistency is important.

preprint2022arXiv

SARS-CoV-2 Dissemination using a Network of the United States Counties

During 2020 and 2021, severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) transmission has been increasing amongst the world's population at an alarming rate. Reducing the spread of SARS-CoV-2 and other diseases that are spread in similar manners is paramount for public health officials as they seek to effectively manage resources and potential population control measures such as social distancing and quarantines. By analyzing the United States' county network structure, one can model and interdict potential higher infection areas. County officials can provide targeted information, preparedness training, as well as increase testing in these areas. While these approaches may provide adequate countermeasures for localized areas, they are inadequate for the holistic United States. We solve this problem by collecting coronavirus disease 2019 (COVID-19) infections and deaths from the Center for Disease Control and Prevention{\color{black},} and {\color{black} adjacency between all counties obtained} from the United States Census Bureau. Generalized network autoregressive (GNAR) time series models have been proposed as an efficient learning algorithm for networked datasets. This work fuses network science and operations research techniques to univariately model COVID-19 cases, deaths, and current survivors across the United States' county network structure.

preprint2022arXiv

Tropical Geometry of Phylogenetic Tree Space: A Statistical Perspective

Phylogenetic trees are the fundamental mathematical representation of evolutionary processes in biology. They are also objects of interest in pure mathematics, such as algebraic geometry and combinatorics, due to their discrete geometry. Although they are important data structures, they face the significant challenge that sets of trees form a non-Euclidean phylogenetic tree space, which means that standard computational and statistical methods cannot be directly applied. In this work, we explore the statistical feasibility of a pure mathematical representation of the set of all phylogenetic trees based on tropical geometry for both descriptive and inferential statistics, and unsupervised and supervised machine learning. Our exploration is both theoretical and practical. We show that the tropical geometric phylogenetic tree space endowed with a generalized Hilbert projective metric exhibits analytic, geometric, and topological properties that are desirable for theoretical studies in probability and statistics and allow for well-defined questions to be posed. We illustrate the statistical feasibility of the tropical geometric perspective for phylogenetic trees with an example of both a descriptive and inferential statistical task. Moreover, this approach exhibits increased computational efficiency and statistical performance over the current state-of-the-art, which we illustrate with a real data example on seasonal influenza. Our results demonstrate the viability of the tropical geometric setting for parametric statistical and probabilistic studies of sets of phylogenetic trees.

preprint2020arXiv

Tropical Data Science

Phylogenomics is a new field which applies to tools in phylogenetics to genome data. Due to a new technology and increasing amount of data, we face new challenges to analyze them over a space of phylogenetic trees. Because a space of phylogenetic trees with a fixed set of labels on leaves is not Euclidean, we cannot simply apply tools in data science. In this paper we survey some new developments of machine learning models using tropical geometry to analyze a set of phylogenetic trees over a tree space.

preprint2020arXiv

Tropical Support Vector Machine and its Applications to Phylogenomics

Most data in genome-wide phylogenetic analysis (phylogenomics) is essentially multidimensional, posing a major challenge to human comprehension and computational analysis. Also, we can not directly apply statistical learning models in data science to a set of phylogenetic trees since the space of phylogenetic trees is not Euclidean. In fact, the space of phylogenetic trees is a tropical Grassmannian in terms of max-plus algebra. Therefore, to classify multi-locus data sets for phylogenetic analysis, we propose tropical support vector machines (SVMs). Like classical SVMs, a tropical SVM is a discriminative classifier defined by the tropical hyperplane which maximizes the minimum tropical distance from data points to itself in order to separate these data points into sectors (half-spaces) in the tropical projective torus. Both hard margin tropical SVMs and soft margin tropical SVMs can be formulated as linear programming problems. We focus on classifying two categories of data, and we study a simpler case by assuming the data points from the same category ideally stay in the same sector of a tropical separating hyperplane. For hard margin tropical SVMs, we prove the necessary and sufficient conditions for two categories of data points to be separated, and we show an explicit formula for the optimal value of the feasible linear programming problem. For soft margin tropical SVMs, we develop novel methods to compute an optimal tropical separating hyperplane. Computational experiments show our methods work well. We end this paper with open problems.

preprint2016arXiv

Distributions of topological tree metrics between a species tree and a gene tree

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.

preprint2016arXiv

Principal component analysis and the locus of the Frechet mean in the space of phylogenetic trees

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échet 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.

preprint2015arXiv

Extremal Positive Semidefinite Matrices for Graphs without $K_5$ Minors

For a graph $G$ with $p$ vertices the closed convex cone $\mathbb{S}^p_{\succeq0}(G)$ consists of all real positive semidefinite $p\times p$ 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. For a graph $G$ without $K_5$ minors, we show that the normal vectors to the facets of the $(\pm1)$-cut polytope of $G$ specify the off-diagonal entries of extremal matrices in $\mathbb{S}^p_{\succeq0}(G)$. We also prove that the constant term of the linear equation of each facet-supporting hyperplane is the rank of its corresponding extremal matrix in $\mathbb{S}^p_{\succeq0}(G)$. Furthermore, we show that if $G$ is series-parallel then this gives a complete characterization of all possible extremal ranks of $\mathbb{S}^p_{\succeq0}(G)$, consequently solving the sparsity order problem for series-parallel graphs.

preprint2015arXiv

Multi Loci Phylogenetic Analysis with Gene Tree Clustering

Summary: Both theory and empirical evidence indicate that phylogenies (trees) of different genes (loci) do not display precisely matched topologies. This phylogenetic incongruence is attributed to the reticulated evolutionary history of most species due to meiotic sexual recombination in eukaryotes, or horizontal transfers of genetic materials in prokaryotes. Nonetheless, most genes do display topologically related phylogenies; this implies they form cohesive subsets (clusters). In this work, we compare popular clustering methods, and show how the performance of the normalized cut framework is efficient and statistically accurate when obtaining clusters on the set of gene trees based on the geodesic distance between them over the Billera-Holmes-Vogtmann (BHV) tree space. We proceed to present a computational study on the performance of different clustering methods with and without preprocessing under different distance metrics and using a series of dimension reduction techniques. Results: First, we show using simulated data that indeed the Ncut framework accurately clusters the set of gene trees given a species tree under the coalescent process. We then depict the success of our framework by comparing its performance to other clustering techniques, including k-means and hierarchical clustering. The main computational results can be summarized to the stellar performance of the Ncut framework even without dimension reduction, the similar performance portrayed by k-means and Ncut under most dimension reduction schemes, the utter failure of hierarchical clustering to accurately capture clusters, as well as the significantly better performance of the NJp method, as compared to MLE.

preprint2015arXiv

Normalizing Kernels in the Billera-Holmes-Vogtmann Treespace

As costs of genome sequencing have dropped precipitously, development of efficient bioinformatic methods to analyze genome structure and evolution have become ever more urgent. For example, most published phylogenomic studies involve either massive concatenation of sequences, or informal comparisons of phylogenies inferred on a small subset of orthologous genes, neither of which provides a comprehensive overview of evolution or systematic identification of genes with unusual and interesting evolution (e.g. horizontal gene transfers, gene duplication and subsequent neofunctionalization). We are interested in identifying such "outlying" gene trees from the set of gene trees and estimating the distribution of the tree over the "tree space". This paper describes an improvement to the kdetrees algorithm, an adaptation of classical kernel density estimation to the metric space of phylogenetic trees (Billera-Holmes-Vogtman treespace), whereby the kernel normalizing constants, are estimated through the use of the novel holonomic gradient methods. As the original kdetrees paper, we have applied kdetrees to a set of Apicomplexa genes and it identified several unreliable sequence alignments which had escaped previous detection, as well as a gene independently reported as a possible case of horizontal gene transfer.

preprint2015arXiv

Stochastic safety radius on Neighbor-Joining method and Balanced Minimal Evolution on small trees

A distance-based method to reconstruct a phylogenetic tree with $n$ leaves takes a distance matrix, $n \times n$ symmetric matrix with $0$s in the diagonal, as its input and reconstructs a tree with $n$ leaves using tools in combinatorics. A safety radius is a radius from a tree metric (a distance matrix realizing a true tree) within which the input distance matrices must all lie in order to satisfy a precise combinatorial condition under which the distance-based method is guaranteed to return a correct tree. A stochastic safety radius is a safety radius under which the distance-based method is guaranteed to return a correct tree within a certain probability. In this paper we investigated stochastic safety radii for the neighbor-joining (NJ) method and balanced minimal evolution (BME) method for $n = 5$.

preprint2014arXiv

kdetrees: Nonparametric Estimation of Phylogenetic Tree Distributions

Motivation: While 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 quite 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 nonparametric method of estimating distributions of phylogenetic trees, with the goal of identifying trees which 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 which 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 Epichloe genes, fungi symbiotic with grasses, successfully identifying a contrived instance of paralogy. Availability: Our method for estimating tree distributions and identifying outlying trees is implemented as the R package KDETREES, and is available for download from CRAN.

preprint2013arXiv

Markov degree of the three-state toric homogeneous Markov chain model

We consider the three-state toric homogeneous Markov chain model (THMC) without loops and initial parameters. At time $T$, the size of the design matrix is $6 \times 3\cdot 2^{T-1}$ and the convex hull of its columns is the model polytope. We study the behavior of this polytope for $T\geq 3$ and we show that it is defined by 24 facets for all $T\ge 5$. Moreover, we give a complete description of these facets. From this, we deduce that the toric ideal associated with the design matrix is generated by binomials of degree at most 6. Our proof is based on a result due to Sturmfels, who gave a bound on the degree of the generators of a toric ideal, provided the normality of the corresponding toric variety. In our setting, we established the normality of the toric variety associated to the THMC model by studying the geometric properties of the model polytope.

preprint2013arXiv

The characteristic imset polytope of Bayesian networks with ordered nodes

In 2010, M. Studený, R. Hemmecke, and S. Linder explored a new algebraic description of graphical models, called characteristic imsets. Compare with standard imsets, characteristic imsets have several advantages: they are still unique vector representative of conditional independence structures, they are 0-1 vectors, and they are more intuitive in terms of graphs than standard imsets. After defining a characteristic imset polytope (cim-polytope) as the convex hull of all characteristic imsets with a given set of nodes, they also showed that a model selection in graphical models, which maximizes a quality criterion, can be converted into a linear programming problem over the cim-polytope. However, in general, for a fixed set of nodes, the cim-polytope can have exponentially many vertices over an exponentially high dimension. Therefore, in this paper, we focus on the family of directed acyclic graphs (DAGs) whose nodes have a fixed order. This family includes diagnosis models which can be described by Bipartite graphs with a set of $m$ nodes and a set of $n$ nodes for any $m, n \in \Z_+$. In this paper, we first consider cim-polytopes for all diagnosis models and show that these polytopes are direct products of simplices. Then we give a combinatorial description of all edges and all facets of these polytopes. Finally, we generalize these results to the cim-polytopes for all Bayesian networks with a fixed underlying ordering of nodes with or without fixed (or forbidden) edges.

preprint2011arXiv

Degree Bounds for a Minimal Markov Basis for the Three-State Toric Homogeneous Markov Chain Model

We study the three state toric homogeneous Markov chain model and three special cases of it, namely: (i) when the initial state parameters are constant, (ii) without self-loops, and (iii) when both cases are satisfied at the same time. Using as a key tool a directed multigraph associated to the model, the state-graph, we give a bound on the number of vertices of the polytope associated to the model which does not depend on the time. Based on our computations, we also conjecture the stabilization of the f-vector of the polytope, analyze the normality of the semigroup, give conjectural bounds on the degree of the Markov bases.

preprint2011arXiv

Estimating the number of zero-one multi-way tables via sequential importance sampling

In 2005, Chen et al introduced a sequential importance sampling (SIS) procedure to analyze zero-one two-way tables with given fixed marginal sums (row and column sums) via the conditional Poisson (CP) distribution. They showed that compared with Monte Carlo Markov chain (MCMC)-based approaches, their importance sampling method is more efficient in terms of running time and also provides an easy and accurate estimate of the total number of contingency tables with fixed marginal sums. In this paper we extend their result to zero-one multi-way ($d$-way, $d \geq 2$) contingency tables under the no $d$-way interaction model, i.e., with fixed $d - 1$ marginal sums. Also we show by simulations that the SIS procedure with CP distribution to estimate the number of zero-one three-way tables under the no three-way interaction model given marginal sums works very well even with some rejections. We also applied our method to Samson's monks' data set. We end with further questions on the SIS procedure on zero-one multi-way tables.

preprint2011arXiv

Optimality of the Neighbor Joining Algorithm and Faces of the Balanced Minimum Evolution Polytope

Balanced minimum evolution (BME) is a statistically consistent distance-based method to reconstruct a phylogenetic tree from an alignment of molecular data. In 2000, Pauplin showed that the BME method is equivalent to optimizing a linear functional over the BME polytope, the convex hull of the BME vectors obtained from Pauplin's formula applied to all binary trees. The BME method is related to the Neighbor Joining (NJ) algorithm, now known to be a greedy optimization of the BME principle. Further, the NJ and BME algorithms have been studied previously to understand when the NJ Algorithm returns a BME tree for small numbers of taxa. In this paper we aim to elucidate the structure of the BME polytope and strengthen knowledge of the connection between the BME method and NJ Algorithm. We first prove that any subtree-prune-regraft move from a binary tree to another binary tree corresponds to an edge of the BME polytope. Moreover, we describe an entire family of faces parametrized by disjoint clades. We show that these {\em clade-faces} are smaller dimensional BME polytopes themselves. Finally, we show that for any order of joining nodes to form a tree, there exists an associated distance matrix (i.e., dissimilarity map) for which the NJ Algorithm returns the BME tree. More strongly, we show that the BME cone and every NJ cone associated to a tree $T$ have an intersection of positive measure.

preprint2011arXiv

Semigroups and sequential importance sampling for multiway tables and beyond

When an interval of integers between the lower bound l_i and the upper bounds u_i is the support of the marginal distribution n_i|(n_{i-1}, ...,n_1), Chen et al. 2005 noticed that sampling from the interval at each step, for n_i during the sequential importance sampling (SIS) procedure, always produces a table which satisfies the marginal constraints. However, in general, the interval may not be equal to the support of the marginal distribution. In this case, the SIS procedure may produce tables which do not satisfy the marginal constraints, leading to rejection [Chen et al. 2006]. Rejecting tables is computationally expensive and incorrect proposal distributions result in biased estimators for the number of tables given its marginal sums. This paper has two focuses; (1) we propose a correction coefficient which corrects an interval of integers between the lower bound l_i and the upper bounds u_i to the support of the marginal distribution asymptotically even with rejections and with the same time complexity as the original SIS procedure (2) using univariate and bivariate logistic regression models, we present extensive experiments on simulated data sets for estimating the number of tables, and (3) we applied the volume test proposed by Diaconis and Efron 1985 on 2x2x6 randomly generated tables to compare the performance of SIS versus MCMC. When estimating the number of tables in our simulation study, we used univariate and bivariate logistic regression models since under these models the SIS procedure seems to have higher rate of rejections even with small tables. We also apply our correction coefficients to data sets on coronary heart disease and occurrence of esophageal cancer.

preprint2010arXiv

Markov bases and subbases for bounded contingency tables

In this paper we study the computation of Markov bases for contingency tables whose cell entries have an upper bound. In general a Markov basis for unbounded contingency table under a certain model differs from a Markov basis for bounded tables. Rapallo, (2007) applied Lawrence lifting to compute a Markov basis for contingency tables whose cell entries are bounded. However, in the process, one has to compute the universal Gröbner basis of the ideal associated with the design matrix for a model which is, in general, larger than any reduced Gröbner basis. Thus, this is also infeasible in small- and medium-sized problems. In this paper we focus on bounded two-way contingency tables under independence model and show that if these bounds on cells are positive, i.e., they are not structural zeros, the set of basic moves of all $2 \times 2$ minors connects all tables with given margins. We end this paper with an open problem that if we know the given margins are positive, we want to find the necessary and sufficient condition on the set of structural zeros so that the set of basic moves of all $2 \times 2$ minors connects all incomplete contingency tables with given margins.

preprint2010arXiv

Statistical analysis on detecting recombination sites in DNA-beta satellites associated with the old world geminiviruses

Although an exchange of genetic information by recombination plays an important role in the evolution of viruses, it is not clear how it generates diversity. {\it Geminiviruses} are plant viruses which have ambisense single-stranded circular DNA genomes and one of the most economically important plant viruses in agricultural production. Small circular single-stranded DNA satellites, termed DNA-$β$, have recently been found associated with some geminivirus infections. In this paper we analyze a satellite molecule DNA-$β$ of geminiviruses for recombination events using phylogenetic and statistical analysis and we find that one strain from ToLCMaB has a recombination pattern and is possibly recombinant molecule between two strains from two species, PaLCuB-[IN:Chi:05] (major parent) and ToLCB-[IN:CP:04] (minor parent).

preprint2010arXiv

Statistical Phylogenetic Tree Analysis Using Differences of Means

We propose a statistical method to test whether two phylogenetic trees with given alignments are significantly incongruent. Our method compares the two distributions of phylogenetic trees given by the input alignments, instead of comparing point estimations of trees. This statistical approach can be applied to gene tree analysis for example, detecting unusual events in genome evolution such as horizontal gene transfer and reshuffling. Our method uses difference of means to compare two distributions of trees, after embedding trees in a vector space. Bootstrapping alignment columns can then be applied to obtain p-values. To compute distances between means, we employ a "kernel trick" which speeds up distance calculations when trees are embedded in a high-dimensional feature space, e.g. splits or quartets feature space. In this pilot study, first we test our statistical method's ability to distinguish between sets of gene trees generated under coalescence models with species trees of varying dissimilarity. We follow our simulation results with applications to various data sets of gophers and lice, grasses and their endophytes, and different fungal genes from the same genome. A companion toolkit, {\tt Phylotree}, is provided to facilitate computational experiments.

preprint2008arXiv

On connectivity of fibers with positive marginals in multiple logistic regression

In this paper we consider exact tests of a multiple logistic regression, where the levels of covariates are equally spaced, via Markov beses. In usual application of multiple logistic regression, the sample size is positive for each combination of levels of the covariates. In this case we do not need a whole Markov basis, which guarantees connectivity of all fibers. We first give an explicit Markov basis for multiple Poisson regression. By the Lawrence lifting of this basis, in the case of bivariate logistic regression, we show a simple subset of the Markov basis which connects all fibers with a positive sample size for each combination of levels of covariates.