# PhylogeneticTrees -- a package to compute phylogenetic invariants associated to group-based models

## Description

PhylogeneticTrees is a package for phylogenetic algebraic geometry. This package calculates generating sets for phylogenetic ideals and their joins and secants. Additionally, the package computes lower bounds for the dimensions of secants and joins of phylogenetic ideals.

This package handles a class of commonly used tree-based Markov models called group-based models. These models are subject to the Fourier-Hadamard coordinate transformation, which make the parametrizations monomial and the ideals toric. See the following for more details: [1] and [2].

For these models, the PhylogeneticTrees package includes two methods for computing a generating set for ideals of phylogenetic invariants. The first method calls FourTiTwo to compute the generating set of the toric ideal. The second implements a theoretical construction for inductively determining the ideal of phylogenetic invariants for any $k$-valent tree from the $k$-leaf claw tree as described in Theorem 24 of [3].

This package also handles the joins and secants of these ideals by implementing the elimination method described in [4].

In cases where computing a generating set for a join or secant ideal is infeasible, the package provides a probabilistic method, based on Terracini’s Lemma, to compute a lower bound on the dimension of a join or secant ideal.

References:

[1] S.N. Evans and T.P. Speed, it Invariants of some probability models used in phylogenetic inference, Ann. Statist. 21 (1993), no. 1, 355–377, and

[2] L. Székely, P.L. Erdös, M.A. Steel, and D. Penny, A Fourier inversion formula for evolutionary trees, Applied Mathematics Letters 6 (1993), no. 2, 13–17.

[3] Bernd Sturmfels and Seth Sullivant, Toric ideals of phylogenetic invariants, J. Comp. Biol. 12 (2005), no. 2, 204–228.

[4] Bernd Sturmfels and Seth Sullivant, Combinatorial secant varieties, Quarterly Journal of Pure and Applied Mathematics 2 (2006), 285–309.

## Authors

• Hector Baños
• Nathaniel Bushek
• Ruth Davidson
• Elizabeth Gross
• Pamela Harris
• Robert Krone
• Colby Long
• AJ Stewart
• Robert Walker

## Certification

Version 2.0 of this package was accepted for publication in volume 11 of The Journal of Software for Algebra and Geometry on 8 August 2020, in the article Phylogenetic trees. That version can be obtained from the journal or from the Macaulay2 source code repository.

## Version

This documentation describes version 2.0 of PhylogeneticTrees.

## Source code

The source code from which this documentation is derived is in the file PhylogeneticTrees.m2.

## Exports

• Types
• LeafTree -- a tree described in terms of its leaves
• Model -- a group-based model
• Functions and commands
• Methods
• "buckets(Model)" -- see buckets -- the equivalence classes of group elements of a Model
• digraph(LeafTree,List) -- convert a LeafTree to a Digraph
• "digraph(LeafTree,Set)" -- see digraph(LeafTree,List) -- convert a LeafTree to a Digraph
• "edgeContract(LeafTree,List)" -- see edgeContract -- contract an edge of a tree
• "edgeContract(LeafTree,Set)" -- see edgeContract -- contract an edge of a tree
• "edgeCut(LeafTree,List,Thing)" -- see edgeCut -- break up a tree at an edge
• "edgeCut(LeafTree,Set,Thing)" -- see edgeCut -- break up a tree at an edge
• edges(LeafTree) -- list the edges of a tree
• "fourierToProbability(Ring,Ring,ZZ,Model)" -- see fourierToProbability -- map from Fourier coordinates to probablity coordinates
• graph(LeafTree) -- convert a LeafTree to Graph
• "group(Model)" -- see group -- the group of a Model
• "internalEdges(LeafTree)" -- see internalEdges -- list the internal edges of a tree
• "internalVertices(LeafTree)" -- see internalVertices -- list the internal vertices of a tree
• "isIsomorphic(LeafTree,LeafTree)" -- see isIsomorphic -- check isomorphism of two tree
• "joinIdeal(Ideal,Ideal)" -- see joinIdeal -- compute the join of several ideals
• "joinIdeal(List)" -- see joinIdeal -- compute the join of several ideals
• "labeledBinaryTrees(ZZ)" -- see labeledBinaryTrees -- enumerate all binary labeled trees
• "labeledTrees(ZZ)" -- see labeledTrees -- enumerate all labeled trees
• "leafColorings(LeafTree,Model)" -- see leafColorings -- list the consistent colorings of a tree
• "leafColorings(ZZ,Model)" -- see leafColorings -- list the consistent colorings of a tree
• "LeafTree == LeafTree" -- see LeafTree -- a tree described in terms of its leaves
• "leafTree(Graph)" -- see leafTree -- construct a LeafTree
• "leafTree(List,List)" -- see leafTree -- construct a LeafTree
• "leafTree(ZZ,List)" -- see leafTree -- construct a LeafTree
• leaves(LeafTree) -- list the leaves of a tree
• "model(List,List,List)" -- see model -- construct a Model
• "phyloToric42(Graph,Model)" -- see phyloToric42 -- compute the invariants of a group-based phylogenetic model with 4ti2
• "phyloToric42(LeafTree,Model)" -- see phyloToric42 -- compute the invariants of a group-based phylogenetic model with 4ti2
• "phyloToric42(ZZ,List,Model)" -- see phyloToric42 -- compute the invariants of a group-based phylogenetic model with 4ti2
• "phyloToricAMatrix(Graph,Model)" -- see phyloToricAMatrix -- construct the design matrix of a group-based phylogenetic model
• "phyloToricAMatrix(LeafTree,Model)" -- see phyloToricAMatrix -- construct the design matrix of a group-based phylogenetic model
• "phyloToricAMatrix(ZZ,List,Model)" -- see phyloToricAMatrix -- construct the design matrix of a group-based phylogenetic model
• "phyloToricFP(LeafTree,Model)" -- see phyloToricFP -- compute the invariants of a group-based phylogenetic model with toric fiber products
• "phyloToricFP(ZZ,List,Model)" -- see phyloToricFP -- compute the invariants of a group-based phylogenetic model with toric fiber products
• "phyloToricLinears(LeafTree,Model)" -- see phyloToricLinears -- compute the linear invariants of a group-based phylogenetic model
• "phyloToricLinears(ZZ,List,Model)" -- see phyloToricLinears -- compute the linear invariants of a group-based phylogenetic model
• "phyloToricRandom(LeafTree,Model)" -- see phyloToricRandom -- compute a random invariant of a group-based phylogenetic model
• "phyloToricRandom(ZZ,List,Model)" -- see phyloToricRandom -- compute a random invariant of a group-based phylogenetic model
• "pRing(LeafTree,Model)" -- see pRing -- construct the ring of probability coordinates
• "pRing(ZZ,Model)" -- see pRing -- construct the ring of probability coordinates
• "qRing(LeafTree,Model)" -- see qRing -- construct the ring of Fourier coordinates
• "qRing(ZZ,Model)" -- see qRing -- construct the ring of Fourier coordinates
• "rootedBinaryTrees(ZZ)" -- see rootedBinaryTrees -- enumerate all rooted binary trees
• "rootedTrees(ZZ)" -- see rootedTrees -- enumerate all rooted trees
• "secant(Ideal,ZZ)" -- see secant -- compute the secant of an ideal
• "toricJoinDim(List)" -- see toricJoinDim -- dimension of a join of toric varieties
• "toricJoinDim(Matrix,Matrix)" -- see toricJoinDim -- dimension of a join of toric varieties
• "toricSecantDim(Matrix,ZZ)" -- see toricSecantDim -- dimension of a secant of a toric variety
• "unlabeledTrees(ZZ)" -- see unlabeledTrees -- enumerate all unlabeled trees
• "vertexCut(LeafTree,List,Thing,Thing)" -- see vertexCut -- break up a tree at a vertex
• "vertexCut(LeafTree,Set,Thing,Thing)" -- see vertexCut -- break up a tree at a vertex
• vertices(LeafTree) -- list the vertices of a tree
• Symbols
• QRing -- optional argument to specify Fourier coordinate ring
• Other things
• CFNmodel -- the model corresponding to the Cavender-Farris-Neyman model or binary Jukes Cantor
• JCmodel -- the model corresponding to the Jukes Cantor model
• K2Pmodel -- the model corresponding to the Kimura 2-parameter model
• K3Pmodel -- the model corresponding to the Kimura 3-parameter model

## For the programmer

The object PhylogeneticTrees is .