BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Seth Sullivant

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

ResearcherUnclaimed source record
math.COmath.STStatistics Theorymath.AGmath.ACPopulations and Evolutionmath.OCmath.DSQuantitative MethodsComputationComputational Geometrycond-mat.stat-mechData Structures and AlgorithmsDiscrete MathematicsMachine Learningmath.CAmath.MG

Catalog footprint

What is connected

37works
17topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

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

37 published item(s)

preprint2022arXiv

Directed Gaussian graphical models with toric vanishing ideals

Directed Gaussian graphical models are statistical models that use a directed acyclic graph (DAG) to represent the conditional independence structures between a set of jointly normal random variables. The DAG specifies the model through recursive factorization of the parametrization, via restricted conditional distributions. In this paper, we make an attempt to characterize the DAGs whose vanishing ideals are toric ideals. In particular, we give some combinatorial criteria to construct such DAGs from smaller DAGs which have toric vanishing ideals. An associated monomial map called the shortest trek map plays an important role in our description of toric Gaussian DAG models. For DAGs whose vanishing ideal is toric, we prove results about the generating sets of those toric ideals.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Structural Identifiability of Series-Parallel LCR Systems

We consider the identifiability problem for the parameters of series-parallel LCR circuit networks. We prove that for networks with only two classes of components (inductor-capacitor (LC), inductor-resistor (LR), and capacitor-resistor (RC)), the parameters are identifiable if and only if the number of non-monic coefficients of the constitutive equations equals the number of parameters. The notion of the "type" of the constitutive equations plays a key role in the identifiability of LC, LR, and RC networks. We also investigate the general series-parallel LCR circuits (with all three classes of components), and classify the types of constitutive equations that can arise, showing that there are 22 different types. However, we produce an example that shows that the basic notion of type that works to classify identifiability of two class networks is not sufficient to classify the identifiability of general series-parallel LCR circuits.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Gaussian graphical models with toric vanishing ideals

Gaussian graphical models are semi-algebraic subsets of the cone of positive definite covariance matrices. They are widely used throughout natural sciences, computational biology and many other fields. Computing the vanishing ideal of the model gives us an implicit description of the model. In this paper, we resolve two conjectures of Sturmfels and Uhler from \cite{BS n CU}. In particular, we characterize those graphs for which the vanishing ideal of the Gaussian graphical model is generated in degree $1$ and $2$. These turn out to be the Gaussian graphical models whose ideals are toric ideals, and the resulting graphs are the $1$-clique sums of complete graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Cavender-Farris-Neyman Model with a Molecular Clock

We give a combinatorial description of the toric ideal of invariants of the Cavender-Farris-Neyman model with a molecular clock (CFN-MC) on a rooted binary phylogenetic tree and prove results about the polytope associated to this toric ideal. Key results about the polyhedral structure include that the number of vertices of this polytope is a Fibonacci number, the facets of the polytope can be described using the combinatorial "cluster" structure of the underlying rooted tree, and the volume is equal to an Euler zig-zag number. The toric ideal of invariants of the CFN-MC model has a quadratic Groebner basis with squarefree initial terms. Finally, we show that the Ehrhart polynomial of these polytopes, and therefore the Hilbert series of the ideals, depends only on the number of leaves of the underlying binary tree, and not on the topology of the tree itself. These results are analogous to classic results for the Cavender-Farris-Neyman model without a molecular clock. However, new techniques are required because the molecular clock assumption destroys the toric fiber product structure that governs group-based models without the molecular clock.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Algebraic Tools for the Analysis of State Space Models

We present algebraic techniques to analyze state space models in the areas of structural identifiability, observability, and indistinguishability. While the emphasis is on surveying existing algebraic tools for studying ODE systems, we also present a variety of new results. In particular: on structural identifiability, we present a method using linear algebra to find identifiable functions of the parameters of a model for unidentifiable models. On observability, we present techniques using Gröbner bases and algebraic matroids to test algebraic observability of state space models. On indistinguishability, we present a sufficient condition for distinguishability using computational algebra and demonstrate testing indistinguishability.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Matrix Schubert varieties and Gaussian conditional independence models

Matrix Schubert varieties are certain varieties in the affine space of square matrices which are determined by specifying rank conditions on submatrices. We study these varieties for generic matrices, symmetric matrices, and upper triangular matrices in view of two applications to algebraic statistics: we observe that special conditional independence models for Gaussian random variables are intersections of matrix Schubert varieties in the symmetric case. Consequently, we obtain a combinatorial primary decomposition algorithm for some conditional independence ideals. We also characterize the vanishing ideals of Gaussian graphical models for generalized Markov chains. In the course of this investigation, we are led to consider three related stratifications, which come from the Schubert stratification of a flag variety. We provide some combinatorial results, including describing the stratifications using the language of rank arrays and enumerating the strata in each case.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Normal Binary Hierarchical Models

Each simplicial complex and integer vector yields a vector configuration whose combinatorial properties are important for the analysis of contingency tables. We study the normality of these vector configurations including a description of operations on simplicial complexes that preserve normality, constructions of families of minimally nonnormal complexes, and computations classifying all of the normal complexes on up to six vertices. We repeat this analysis for compressed vector configurations, classifying all of the compressed complexes on up to six vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Statistically-Consistent k-mer Methods for Phylogenetic Tree Reconstruction

Frequencies of $k$-mers in sequences are sometimes used as a basis for inferring phylogenetic trees without first obtaining a multiple sequence alignment. We show that a standard approach of using the squared-Euclidean distance between $k$-mer vectors to approximate a tree metric can be statistically inconsistent. To remedy this, we derive model-based distance corrections for orthologous sequences without gaps, which lead to consistent tree inference. The identifiability of model parameters from $k$-mer frequencies is also studied. Finally, we report simulations showing the corrected distance out-performs many other $k$-mer methods, even when sequences are generated with an insertion and deletion process. These results have implications for multiple sequence alignment as well, since $k$-mer methods are usually the first step in constructing a guide tree for such algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Unimodular Binary Hierarchical Models

Associated to each simplicial complex is a binary hierarchical model. We classify the simplicial complexes that yield unimodular binary hierarchical models. Our main theorem provides both a construction of all unimodular binary hierarchical models, together with a characterization in terms of excluded minors, where our definition of a minor allows the taking of links and induced complexes. A key tool in the proof is the lemma that the class of unimodular binary hierarchical models is closed under the Alexander duality operation on simplicial complexes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lifting Markov Bases and Higher Codimension Toric Fiber Products

We study how to lift Markov bases and Gröbner bases along linear maps of lattices. We give a lifting algorithm that allows to compute such bases iteratively provided a certain associated semigroup is normal. Our main application is the toric fiber product of toric ideals, where lifting gives Markov bases of the factor ideals that satisfy the compatible projection property. We illustrate the technique by computing Markov bases of various infinite families of hierarchical models. The methodology also implies new finiteness results for iterated toric fiber products.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Maximum Likelihood Threshold of a Graph

The maximum likelihood threshold of a graph is the smallest number of data points that guarantees that maximum likelihood estimates exist almost surely in the Gaussian graphical model associated to the graph. We show that this graph parameter is connected to the theory of combinatorial rigidity. In particular, if the edge set of a graph $G$ is an independent set in the $n-1$-dimensional generic rigidity matroid, then the maximum likelihood threshold of $G$ is less than or equal to $n$. This connection allows us to prove many results about the maximum likelihood threshold.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Identifiability of 3-Class Jukes-Cantor Mixtures

We prove identifiability of the tree parameters of the 3-class Jukes-Cantor mixture model. The proof uses ideas from algebraic statistics, in particular: finding phylogenetic invariants that separate the varieties associated to different triples of trees; computing dimensions of the resulting phylogenetic varieties; and using the disentangling number to reduce to trees with a small number of leaves. Symbolic computation also plays a key role in handling the many different cases and finding relevant phylogenetic invariants.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Identifiability results for several classes of linear compartment models

Identifiability concerns finding which unknown parameters of a model can be estimated from given input-output data. If some subset of the parameters of a model cannot be determined given input-output data, then we say the model is unidentifiable. In past work we identified a class of models, that we call identifiable cycle models, which are not identifiable but have the simplest possible identifiable functions (so-called monomial cycles). Here we show how to modify identifiable cycle models by adding inputs, adding outputs, or removing leaks, in such a way that we obtain an identifiable model. We also prove a constructive result on how to combine identifiable models, each corresponding to strongly connected graphs, into a larger identifiable model. We apply these theoretical results to several real-world biological models from physiology, cell biology, and ecology.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multigraded Commutative Algebra of Graph Decompositions

The toric fiber product is a general procedure for gluing two ideals, homogeneous with respect to the same multigrading, to produce a new homogeneous ideal. Toric fiber products generalize familiar constructions in commutative algebra like adding monomial ideals and the Segre product. We describe how to obtain generating sets of toric fiber products in non-zero codimension and discuss persistence of normality and primary decompositions under toric fiber products. Several applications are discussed, including (a) the construction of Markov bases of hierarchical models in many new cases, (b) a new proof of the quartic generation of binary graph models associated to $K_{4}$-minor free graphs, and (c) the recursive computation of primary decompositions of conditional independence ideals.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sequential Importance Sampling for Two-dimensional Ising Models

In recent years, sequential importance sampling (SIS) has been well developed for sampling contingency tables with linear constraints. In this paper, we apply SIS procedure to 2-dimensional Ising models, which give observations of 0-1 tables and include both linear and quadratic constraints. We show how to compute bounds for specific cells by solving linear programming (LP) problems over cut polytopes to reduce rejections. The computational results, which includes both simulations and real data analysis, suggest that our method performs very well for sparse tables and when the 1's are spread out: the computational times are short, the acceptance rates are high, and if proper tests are used then in most cases our conclusions are theoretically reasonable.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Structural identifiability of viscoelastic mechanical systems

We solve the local and global structural identifiability problems for viscoelastic mechanical models represented by networks of springs and dashpots. We propose a very simple characterization of both local and global structural identifiability based on identifiability tables, with the purpose of providing a guideline for constructing arbitrarily complex, identifiable spring-dashpot networks. We illustrate how to use our results in a number of examples and point to some applications in cardiovascular modeling.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Tying Up Loose Strands: Defining Equations of the Strand Symmetric Model

The strand symmetric model is a phylogenetic model designed to reflect the symmetry inherent in the double-stranded structure of DNA. We show that the set of known phylogenetic invariants for the general strand symmetric model of the three leaf claw tree entirely defines the ideal. This knowledge allows one to determine the vanishing ideal of the general strand symmetric model of any trivalent tree. Our proof of the main result is computational. We use the fact that the Zariski closure of the strand symmetric model is the secant variety of a toric variety to compute the dimension of the variety. We then show that the known equations generate a prime ideal of the correct dimension using elimination theory.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distance-based phylogenetic methods around a polytomy

Distance-based phylogenetic algorithms attempt to solve the NP-hard least squares phylogeny problem by mapping an arbitrary dissimilarity map representing biological data to a tree metric. The set of all dissimilarity maps is a Euclidean space properly containing the space of all tree metrics as a polyhedral fan. Outputs of distance-based tree reconstruction algorithms such as UPGMA and Neighbor-Joining are points in the maximal cones in the fan. Tree metrics with polytomies lie at the intersections of maximal cones. A phylogenetic algorithm divides the space of all dissimilarity maps into regions based upon which combinatorial tree is reconstructed by the algorithm. Comparison of phylogenetic methods can be done by comparing the geometry of these regions. We use polyhedral geometry to compare the local nature of the subdivisions induced by least squares phylogeny, UPGMA, and Neighbor-Joining. Our results suggest that in some circumstances, UPGMA and Neighbor-Joining poorly match least squares phylogeny when the true tree has a polytomy.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Graphical models in Macaulay2

The Macaulay2 package GraphicalModels contains algorithms for the algebraic study of graphical models associated to undirected, directed and mixed graphs, and associated collections of conditional independence statements. Among the algorithms implemented are procedures for computing the vanishing ideal of graphical models, for generating conditional independence ideals of families of independence statements associated to graphs, and for checking for identifiable parameters in Gaussian mixed graph models. These procedures can be used to study fundamental problems about graphical models.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Identifiable reparametrizations of linear compartment models

Identifiability concerns finding which unknown parameters of a model can be quantified from given input-output data. Many linear ODE models, used in systems biology and pharmacokinetics, are unidentifiable, which means that parameters can take on an infinite number of values and yet yield the same input-output data. We use commutative algebra and graph theory to study a particular class of unidentifiable models and find conditions to obtain identifiable scaling reparametrizations of these models. Our main result is that the existence of an identifiable scaling reparametrization is equivalent to the existence of a scaling reparametrization by monomial functions. We also provide partial results beginning to classify graphs which possess an identifiable scaling reparametrization.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Polyhedral Combinatorics of UPGMA Cones

Distance-based methods such as UPGMA (Unweighted Pair Group Method with Arithmetic Mean) continue to play a significant role in phylogenetic research. We use polyhedral combinatorics to analyze the natural subdivision of the positive orthant induced by classifying the input vectors according to tree topologies returned by the algorithm. The partition lattice informs the study of UPGMA trees. We give a closed form for the extreme rays of UPGMA cones on n taxa, and compute the normalized volumes of the UPGMA cones for small n. Keywords: phylogenetic trees, polyhedral combinatorics, partition lattice

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Positive margins and primary decomposition

We study random walks on contingency tables with fixed marginals, corresponding to a (log-linear) hierarchical model. If the set of allowed moves is not a Markov basis, then there exist tables with the same marginals that are not connected. We study linear conditions on the values of the marginals that ensure that all tables in a given fiber are connected. We show that many graphical models have the positive margins property, which says that all fibers with strictly positive marginals are connected by the quadratic moves that correspond to conditional independence statements. The property persists under natural operations such as gluing along cliques, but we also construct examples of graphical models not enjoying this property. We also provide a negative answer to a question of Engström, Kahle, and Sullivant by demonstrating that the global Markov ideal of the complete bipartite graph K_(3,3) is not radical. Our analysis of the positive margins property depends on computing the primary decomposition of the associated conditional independence ideal. The main technical results of the paper are primary decompositions of the conditional independence ideals of graphical models of the $N$-cycle and the complete bipartite graph $K_(2,N-2)$, with various restrictions on the size of the nodes.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Positivity for Gaussian graphical models

Gaussian graphical models are parametric statistical models for jointly normal random variables whose dependence structure is determined by a graph. In previous work, we introduced trek separation, which gives a necessary and sufficient condition in terms of the graph for when a subdeterminant is zero for all covariance matrices that belong to the Gaussian graphical model. Here we extend this result to give explicit cancellation-free formulas for the expansions of nonzero subdeterminants.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

When Do Phylogenetic Mixture Models Mimic Other Phylogenetic Models?

Phylogenetic mixture models, in which the sites in sequences undergo different substitution processes along the same or different trees, allow the description of heterogeneous evolutionary processes. As data sets consisting of longer sequences become available, it is important to understand such models, for both theoretical insights and use in statistical analyses. Some recent articles have highlighted disturbing "mimicking" behavior in which a distribution from a mixture model is identical to one arising on a different tree or trees. Other works have indicated such problems are unlikely to occur in practice, as they require very special parameter choices. After surveying some of these works on mixture models, we give several new results. In general, if the number of components in a generating mixture is not too large and we disallow zero or infinite branch lengths, then it cannot mimic the behavior of a non-mixture on a different tree. On the other hand, if the mixture model is locally over-parameterized, it is possible for a phylogenetic mixture model to mimic distributions of another tree model. Though theoretical questions remain, these sorts of results can serve as a guide to when the use of mixture models in either ML or Bayesian frameworks is likely to lead to statistically consistent inference, and when mimicking due to heterogeneity should be considered a realistic possibility.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Finite Groebner bases in infinite dimensional polynomial rings and applications

We introduce the theory of monoidal Groebner bases, a concept which generalizes the familiar notion in a polynomial ring and allows for a description of Groebner bases of ideals that are stable under the action of a monoid. The main motivation for developing this theory is to prove finiteness theorems in commutative algebra and its applications. A major result of this type is that ideals in infinitely many indeterminates stable under the action of the symmetric group are finitely generated up to symmetry. We use this machinery to give new proofs of some classical finiteness theorems in algebraic statistics as well as a proof of the independent set conjecture of Hosten and the second author.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Geodesics in CAT(0) Cubical Complexes

We describe an algorithm to compute the geodesics in an arbitrary CAT(0) cubical complex. A key tool is a correspondence between cubical complexes of global non-positive curvature and posets with inconsistent pairs. This correspondence also gives an explicit realization of such a complex as the state complex of a reconfigurable system, and a way to embed any interval in the integer lattice cubing of its dimension.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Global identifiability of linear structural equation models

Structural equation models are multivariate statistical models that are defined by specifying noisy functional relationships among random variables. We consider the classical case of linear relationships and additive Gaussian noise terms. We give a necessary and sufficient condition for global identifiability of the model in terms of a mixed graph encoding the linear structural equations and the correlation structure of the error terms. Global identifiability is understood to mean injectivity of the parametrization of the model and is fundamental in particular for applicability of standard statistical methodology.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Identifiability of Large Phylogenetic Mixture Models

Phylogenetic mixture models are statistical models of character evolution allowing for heterogeneity. Each of the classes in some unknown partition of the characters may evolve by different processes, or even along different trees. The fundamental question of whether parameters of such a model are identifiable is difficult to address, due to the complexity of the parameterization. We analyze mixture models on large trees, with many mixture components, showing that both numerical and tree parameters are indeed identifiable in these models when all trees are the same. We also explore the extent to which our algebraic techniques can be employed to extend the result to mixtures on different trees.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Identifying Causal Effects with Computer Algebra

The long-standing identification problem for causal effects in graphical models has many partial results but lacks a systematic study. We show how computer algebra can be used to either prove that a causal effect can be identified, generically identified, or show that the effect is not generically identifiable. We report on the results of our computations for linear structural equation models, where we determine precisely which causal effects are generically identifiable for all graphs on three and four vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Trek separation for Gaussian graphical models

Gaussian graphical models are semi-algebraic subsets of the cone of positive definite covariance matrices. Submatrices with low rank correspond to generalizations of conditional independence constraints on collections of random variables. We give a precise graph-theoretic characterization of when submatrices of the covariance matrix have small rank for a general class of mixed graphs that includes directed acyclic and undirected graphs as special cases. Our new trek separation criterion generalizes the familiar $d$-separation criterion. Proofs are based on the trek rule, the resulting matrix factorizations and classical theorems of algebraic combinatorics on the expansions of determinants of path polynomials.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Algebraic statistical models

Many statistical models are algebraic in that they are defined in terms of polynomial constraints, or in terms of polynomial or rational parametrizations. The parameter spaces of such models are typically semi-algebraic subsets of the parameter space of a reference model with nice properties, such as for example a regular exponential family. This observation leads to the definition of an `algebraic exponential family'. This new definition provides a unified framework for the study of statistical models with algebraic structure. In this paper we review the ingredients to this definition and illustrate in examples how computational algebraic geometry can be used to solve problems arising in statistical inference in algebraic models.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Algebraic Factor Analysis: Tetrads, Pentads and Beyond

Factor analysis refers to a statistical model in which observed variables are conditionally independent given fewer hidden variables, known as factors, and all the random variables follow a multivariate normal distribution. The parameter space of a factor analysis model is a subset of the cone of positive definite matrices. This parameter space is studied from the perspective of computational algebraic geometry. Gröbner bases and resultants are applied to compute the ideal of all polynomial functions that vanish on the parameter space. These polynomials, known as model invariants, arise from rank conditions on a symmetric matrix under elimination of the diagonal entries of the matrix. Besides revealing the geometry of the factor analysis model, the model invariants also furnish useful statistics for testing goodness-of-fit.

0 citations0 reviewsNo code linkedOpen access