# 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 Banos
• Nathaniel Bushek
• Ruth Davidson
• Elizabeth Gross
• Pamela Harris
• Robert Krone
• Colby Long
• AJ Stewart
• Robert Walker

## Version

This documentation describes version 1.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
• edgeContract -- Contracts an edge of a tree
• edgeCut -- Breaks up a tree at an edge
• fourierToProbability -- Map from Fourier coordinates to probablity coordinates
• internalEdges -- Lists the internal edges of a tree
• internalVertices -- List the internal vertices of a tree
• joinIdeal -- Computes the join of several ideals
• leafColorings -- lists the friendly colorings of a tree
• leafTree -- Construct a LeafTree
• model -- Construct a Model
• phyloToric42 -- Compute the invariants of a group-based phylogenetic tree model using the 4ti2 package.
• phyloToricAMatrix -- Constructs the A matrix whose columns parametrize the toric variety of the tree T with n leaves
• phyloToricFP -- Compute the invariants of a group-based phylogenetic tree model using the toric fiber product structure
• phyloToricLinears -- Compute the linear invariants of a group-based phylogenetic tree model
• phyloToricQuads -- Compute the quadratic invariants of a group-based phylogenetic tree model
• phyloToricRandom -- Compute a random invariant of a group-based phylogenetic tree model using the toric fiber product structure
• pRing -- Constructs the ring of probability coordinates
• qRing -- Constructs the ring of Fourier coordinates
• secant -- Computes the secant of an ideal
• toricJoinDim -- Dimension of a join of toric varieties
• toricSecantDim -- dimension of a secant of a toric variety
• vertexCut -- Breaks up a tree at a vertex
• Methods
• "edgeContract(LeafTree,List)" -- see edgeContract -- Contracts an edge of a tree
• "edgeContract(LeafTree,Set)" -- see edgeContract -- Contracts an edge of a tree
• "edgeCut(LeafTree,List,Thing)" -- see edgeCut -- Breaks up a tree at an edge
• "edgeCut(LeafTree,Set,Thing)" -- see edgeCut -- Breaks 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) -- Converts a LeafTree to Graph
• "internalEdges(LeafTree)" -- see internalEdges -- Lists the internal edges of a tree
• "internalVertices(LeafTree)" -- see internalVertices -- List the internal vertices of a tree
• "joinIdeal(Ideal,Ideal)" -- see joinIdeal -- Computes the join of several ideals
• "joinIdeal(List)" -- see joinIdeal -- Computes the join of several ideals
• "leafColorings(LeafTree,Model)" -- see leafColorings -- lists the friendly colorings of a tree
• "leafColorings(ZZ,Model)" -- see leafColorings -- lists the friendly colorings of a tree
• "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 tree model using the 4ti2 package.
• "phyloToric42(LeafTree,Model)" -- see phyloToric42 -- Compute the invariants of a group-based phylogenetic tree model using the 4ti2 package.
• "phyloToric42(ZZ,List,Model)" -- see phyloToric42 -- Compute the invariants of a group-based phylogenetic tree model using the 4ti2 package.
• "phyloToricAMatrix(Graph,Model)" -- see phyloToricAMatrix -- Constructs the A matrix whose columns parametrize the toric variety of the tree T with n leaves
• "phyloToricAMatrix(LeafTree,Model)" -- see phyloToricAMatrix -- Constructs the A matrix whose columns parametrize the toric variety of the tree T with n leaves
• "phyloToricAMatrix(ZZ,List,Model)" -- see phyloToricAMatrix -- Constructs the A matrix whose columns parametrize the toric variety of the tree T with n leaves
• "phyloToricFP(LeafTree,Model)" -- see phyloToricFP -- Compute the invariants of a group-based phylogenetic tree model using the toric fiber product structure
• "phyloToricFP(ZZ,List,Model)" -- see phyloToricFP -- Compute the invariants of a group-based phylogenetic tree model using the toric fiber product structure
• "phyloToricLinears(LeafTree,Model)" -- see phyloToricLinears -- Compute the linear invariants of a group-based phylogenetic tree model
• "phyloToricLinears(ZZ,List,Model)" -- see phyloToricLinears -- Compute the linear invariants of a group-based phylogenetic tree model
• "phyloToricRandom(LeafTree,Model)" -- see phyloToricRandom -- Compute a random invariant of a group-based phylogenetic tree model using the toric fiber product structure
• "phyloToricRandom(ZZ,List,Model)" -- see phyloToricRandom -- Compute a random invariant of a group-based phylogenetic tree model using the toric fiber product structure
• "pRing(LeafTree,Model)" -- see pRing -- Constructs the ring of probability coordinates
• "pRing(ZZ,Model)" -- see pRing -- Constructs the ring of probability coordinates
• "qRing(LeafTree,Model)" -- see qRing -- Constructs the ring of Fourier coordinates
• "qRing(ZZ,Model)" -- see qRing -- Constructs the ring of Fourier coordinates
• "secant(Ideal,ZZ)" -- see secant -- Computes 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
• "vertexCut(LeafTree,List,Thing,Thing)" -- see vertexCut -- Breaks up a tree at a vertex
• "vertexCut(LeafTree,Set,Thing,Thing)" -- see vertexCut -- Breaks 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 corresponging to the Cavender-Farris-Neyman model or binary Jukes Cantor
• JCmodel -- The model corresponding to the Jukes Cantor model
• K2Pmodel -- The model corresponging to the Kimura 2-parameter model
• K3Pmodel -- The model corresponging to the Kimura 3-parameter model

## For the programmer

The object PhylogeneticTrees is .