{'fraction_non_alphanumeric': 0.049429657794676805, 'fraction_numerical': 0.015696597445646877, 'mean_word_length': 3.7942276232764667, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 38, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parameter identifiability for a profile mixture model of protein evolution

A Profile Mixture Model is a model of protein evolution, describing sequence data in which sites are assumed to follow many related substitution processes on a single evolutionary tree. The processes depend in part on different amino acid distributions, or profiles, varying over sites in aligned sequences. A fundamental question for any stochastic model, which must be answered positively to justify model-based inference, is whether the parameters are identifiable from the probability distribution they determine. Here we show that a Profile Mixture Model has identifiable parameters under circumstances in which it is likely to be used for empirical analyses. In particular, for a tree relating 9 or more taxa, both the tree topology and all numerical parameters are generically identifiable when the number of profiles is less than 74.


Introduction
A Profile Mixture model is a certain stochastic model of protein sequence evolution that describes the changes in sequences along the tree of evolutionary relationships of a collection of taxa. Such a model is often used for the inference of the tree from sequence data, using standard maximum likelihood or Bayesian statistical frameworks. Here we investigate the question of parameter identifiability for this model: Are the model parameters -both the tree topology and numerical ones -determined by a site pattern distribution arising from the model? Parameter identifiability, which informally means that valid parameter inference is possible in ideal circumstances, is an essential component of the theoretical justification for standard statistical inference approaches.
In models of protein sequence generation, amino acid site patterns are generally assumed to be independent and identically distributed across the sites. Common continuous-time models of amino acid substitutions are instances of the general time-reversible model (GTR) which assumes a single rate matrix Q constant over a metric tree, or extensions that allow for additional scalar rate variation at individual sites. The rate matrix Q has off-diagonal entries from R diag(π), where R is a symmetric matrix of exchangeabilities and π is a vector of frequencies of the amino acids which remains stable under the model.
In principle, one can infer R, π, and a metric tree of taxon relationships from protein sequence data using standard statistical frameworks. However, with 20 amino acids the state space for the model is large, so an exchangeability matrix R is often fixed in advance, having been previously determined empirically for particular types of data. Well-known exchangeabilities for protein alignments include the JTT [Jones et al., 1992], WAG [Whelan and Goldman, 2001], and LG [Le et al., 2008] matrices.
When inspecting protein sequence data, however, it is often clear that the GTR assumption of identically distributed sites is a poor one, since sites have visibly different amino acid compositions. Site residue distributions, or profiles, likely differ because of biophysical properties of amino acids (e.g., hydrophilia, polarity, or charge), and the associated structural and functional constraints on the protein. This phenomenon suggests a model with multiple classes of substitution processes, and in particular a mixture model using a variety of profiles with the same exchangeabilities for all classes. Mixture models can provide better fit to data as they introduce more parameters, though they also increase computational time and may lead to overfitting of the data.
But a more fundamental issue with adopting a mixture model is that one may lose parameter identifiability. If several choices, or even more worrisome, infinitely many choices of parameters lead to the same probability distribution under the model, then even with an idealized infinite data set perfectly in accord with the model one could not recover the parameter values under which the data arose. Since the goal of most phylogenetic analyses is to infer model parameters -generally the topological tree but often numerical parameters as well -identifiability is an essential property for a model to be useful. Non-identifiability poses particular challenges in Bayesian MCMC analyses, where it may be manifested as a lack of convergence [Rannala, 2002].
For non-mixture site substitution models in phylogenetics parameter identifiability has long been established, but mixture models provide greater challenges. Although computational work may suggest whether it holds or fails, parameter identifiability can only be established theoretically as it is a model property, and not dependent on an inference method. In recent years algebraic methods have been introduced and successfully applied to a number of phylogenetic mixture models, see, for example, Allman and Rhodes [2006, Allman et al. [2010Allman et al. [ , 2011Allman et al. [ , 2019, Chifman and Kubatko [2015], Long and Sullivant [2015], Hollering and Sullivant [2019], Wascher and Kubatko [2020]. While one of these works [Rhodes and Sullivant, 2012] established a rather general result on parameter identifiability of phylogenetic mixture models with many components, it unfortunately does not apply to the profile mixture model's specific structure.
In this work, we prove parameter identifiability for a Profile Mixture Model (PM) of amino acid site substitution. PM models were introduced in the Bayesian context [Lartillot and Philippe, 2004, Lartillot et al., 2009, 2013 where the number of profiles might be inferred using a Dirichlet process prior, and as finite mixtures with a fixed number of components in a Maximum Likelihood analysis [Le et al., 2008]. Studies suggest that PM models perform better than single-class models, particularly on data that is saturated or with an underlying long branch attraction bias [Lartillot et al., 2007, Wang et al., 2008. Mixtures with as many as 60 classes have been investigated with empirical data sets, with indications that around 20 profiles often provides good fit [Le et al., 2008]. For a recent study assessing the performance under simulation of mixture models including discrete-Γ rates-across-sites and PM models, see Wang et al. [2014].
Our main result, Theorem 5.7, establishes that parameters of a profile mixture model with up to 73 classes on a tree of 9 or more taxa, are generically identifiable; that is, identifiable outside an exceptional parameter set of measure zero. For any fixed number of classes, the parameters include the tree topology, the tree's edge lengths, the exchangeabilities, the profiles, and weights of the mixture components.
The proof techniques we employ are algebraic in nature, using ideas from tensor decomposition and algebraic geometry. These tools, which have been introduced and used previously for phylogenetic models [Allman and Rhodes, 2006, Rhodes and Sullivant, 2012, are based in the algebraic properties of matrices and 3-way tensors obtained from rearranging the entries of the distribution of site pattern frequencies. However, the structure of the PM model, with profiles varying over classes while the exchangeabilities do not, introduce important differences that prevent any easy deduction of the result from previous work. At several points in our arguments we use exact integer computation, performed by the software Pari/GP [The PARI Group, 2019], to establish certain generic conditions we need on ranks of matrices.
As motivated by applications to amino acid models, our main theorem is stated for the profile mixture model with a state space of size 20. However, the techniques used for establishing it apply to arbitrary sizes κ of the state space. For example, κ might be 4 for DNA, or 61 for codons. However, appropriate rank computations would need to be carried out to complete the proof in such contexts. In the κ = 20 setting we also believe the proof techniques could be pushed to establish identifiability for more than 73 profiles, at the expense of requiring more taxa on the tree. This paper is organized as follows: In Section 2 we introduce phylogenetic substitution models, and in particular the profile mixture model under study. Section 3 provides algebraic definitions and lemmas, though removed from the biological setting of interest. Section 4 then connects the phylogenetic profile mixture model with these algebraic notions. We conclude in Section 5 with the proof of our main theorem on identifiability of the PM model parameters.

Markov Models on Trees
We begin by introducing Markov models of site substitution along a tree. Throughout, let κ be the size of the state space, which we identify with [κ] = {1, 2, 3, . . . , κ}. For protein data, κ = 20. Let T ρ be a rooted topological tree, with root ρ and leaves labelled by elements of the taxon set X. The general Markov model of κ-state sequence evolution along T ρ is parameterized by 1) A 1 × κ vector π giving the distribution of states at the root; and 2) for each edge e directed away from the root, a κ × κ Markov matrix M e giving the conditional probabilities of state transitions along e. These determine the expected site pattern frequency array, or joint distribution of states at the leaves, which we view as a κ × κ × · · · × κ n array or tensor, P . Each site in an alignment is modeled as independent and identically distributed according to P .
A subclass of general Markov models is composed of the general time-reversible models (GTR). For a GTR model, there is an single underlying rate matrix Q, and for each edge e of T ρ a length t e with M e = exp(Qt e ). Time-reversibility is the assumption that for some symmetric κ×κ matrix R of non-negative exchangeabilities and the root distribution π the diagonal entries of Q are those of the product R diag(π), with the diagonal entries chosen so that row sums are zero. This results in diag(π)Q = Q T diag(π). One consequence of time-reversibility is that the Markov matrix M e is independent of the direction of e. It follows that the tree parameter in a GTR model is de facto unrooted since the location of the root is not identifiable. We repeatedly take advantage of this to 'move the root' to locations in T convenient for our arguments.
Profile mixture models are finite mixtures of GTR models, where the underlying exchangeability matrix R is the same for each class. The particular profile mixture model examined here has parameters as follows.
Definition 2.1. Let T be a rooted topological tree, κ ≥ 2 a number of states, and m ≥ 1 a number of classes. Then the numerical parameters of the Profile Mixture Model on T , PM=PM (T, κ, m), are: (1) a collection of non-negative branch lengths {t e }, one for each edge e of T ; (2) a symmetric κ × κ matrix R of non-negative exchangeabilities; (3) a collection of m class weights {w i }, with w i > 0 and w i = 1; and (4) For each class i = 1, 2, . . . , m, − a 1 × κ root distribution vector π i , called a profile; and − a scalar rate parameter r i ≥ 0.
The scalar rate parameters {r i } are used to incorporate across-site rate variation into the PM model. Specifically, for class i with Q i the rate matrix determined by R, π i , the Markov matrix on edge e in T is M e i = exp(r i Q i t e ). We note that site rate variation for PM models may be implemented differently in software, with a rate for each site [Lartillot and Philippe, 2004] or with a discrete-Γ(4) [Le et al., 2008]. In the first implementation, the PM model is very likely overparameterized and ideally the MCMC would limit the number of rate multipliers. Implementation of the rate variation using a discrete-Γ has a long history in computation phylogenetics [Yang, 1994], but proofs of such rate variation identifiability are only known for the continuous Γ [Allman et al., 2008, Chai andHousworth, 2011].
While probability distributions from mixture models are often described as weighted sums of distributions from the various classes, phylogenetic mixture models can be equivalently presented as a single model on a tree T with mκ states at internal nodes of T , and κ states at the leaves. The internal states are pairs (i, j) where i is a class and j ∈ [κ] is a 'usual' state. In this formulation, Markov matrices on internal edges e for the PM model are mκ × mκ block diagonal matrices, where the the m blocks are the M e i , i = 1, . . . , m. The block structure prevents changes from one class to another, though the 'usual' states may change within the class. For the terminal edges e of T , leading to leaves where the class information is not observable, the PM Markov matrix for an edge is formed by stacking the m Markov matrices M e i for the classes. The root distribution is an mκ vector formed by concatenating w i π i for the classes.
We collect these observations for parameterizing the PM model on a tree.
Definition 2.2. Given parameters for the profile mixture model P M(T, κ, m), assume that T is rooted at r. Then the 1 × mκ vector Π = Π r = (w 1 π 1 , w 2 π 2 , . . . , w κ π κ ), the mκ × mκ matrices M e = exp(Qt e ) where Q is block diagonal with blocks r i Q i for each internal edge e of length t e , and the mκ × κ matrix M e formed by stacking the matrices M e i for each class i on a terminal edge give a parameterization of the PM model as a Markov model of site substitution on T .
Since our main goal is to prove parameter identifiability for the PM model, we formally define the notion of generic identifiability.
Definition 2.3. Consider a parametric model, specified by a parameterization map φ from some parameter space to a space of probability distributions. If φ is one-to-one, then the model parameters are identifiable. If φ is one-to-one except possibly on a subset of measure zero in the parameter space, then the model parameters are generically identifiable.
It is well known that for the GTR model some normalization is needed for rates and branch lengths since Qt = (sQ) t s shows rescaling all rates in Q can be offset by decreasing branch lengths. Once understood and addressed, this model overparameterization, or lack of identifiability, is of little consequence. Typically, the rate matrix Q is normalized so that branch lengths are measured in expected number of substitutions per site over the elapsed time. In the strictest sense, only the normalized variant of the GTR model has identifiable parameters, a result used in our proof of the main theorem.
Theorem 2.4. For a single class GTR model on an unrooted metric tree, the tree topology and all numerical parameters are generically identifiable, up to a normalization of Q.

Algebraic Definitions and Lemmas
In this section we collect algebraic definitions and theorems that will play a role in our analysis of the PM model. We present these in a purely algebraic setting, deferring the connection to the phylogenetic models, and in particular the PM model, to later sections. We begin by defining tensors and certain algebraic operations on them leading up to a theorem of J. Kruskal on the structure of 3-way tensors, an important tool that we will use several times. We then briefly introduce algebraic varieties and conclude by stating a theorem for identifying generic properties, a tool also used repeatedly in our proofs.

Tensors. Our first definition is a standard one.
Definition 3.1. Let A be an m × k matrix and B be an n × l matrix. The tensor, or Kronecker, product A ⊗ B is the mn × kl matrix whose rows are indexed by the ordered pair (i 1 , j 1 ), i 1 ∈ [m], j 1 ∈ [n] and whose columns are indexed by ordered pair (i 2 , j 2 ), Less standard is the following.
In the case that A = B and ℓ is a positive integer, then the ℓ th row-tensor power of A is We do not specify the precise order of row and column indices in these tensor products, since for our applications it will either be clear from context, or inconsequential. In particular, we often only need results on the ranks of these products, which are independent of row and column ordering.
Since Kruskal's Theorem concerns 3-way tensors, we next describe reformatting n-way tensors into 3-way ones. Suppose P is an n-way tensor with indices labeled by X. Then a tripartition I|J|K of X is a collection three disjoint non-empty subsets of X whose union is X, X = I ⊔ J ⊔ K. A bipartition of X, or a split, is defined similarly, with the disjoint sets required to be non-empty.
Definition 3.3. Let A be an n-way κ × · · · × κ tensor with I|J a split of the index set X. Then the matrix flattening of A with respect to I, J, denoted Flat I|J (A), is a κ |I| × κ |J| matrix. If, by permuting indices, we assume that I = {1, 2, · · · , |I|}, J = {|I| + 1, · · · , n}, then the (i, j)-entry is Similarly for a tripartition I|J|K of X, the 3-way tensor Flat I|J|K (A) is Kruskal's theorem requires the notion of a 3-way tensor obtained as sum of "outer products" of the rows of 3 matrices.
, and similarly for matrices B and C of size k × n B and k × n C respectively. Then [A, B, C] denotes the 3-way n A × n B × n C tensor where the tensor products in the summands are formatted to preserve an index for each matrix. For instance, where T denotes the transpose. To illustrate, suppose that A, B, C are 2 × 2, 2 × 3, and 2 × 4 matrices respectively, A = 1 2 3 4 , B = 1 2 3 4 5 6 , C = 1 2 3 4 5 6 7 8 . As a simple extension of Definition 3.4 for use with phylogenetic models, we write where π = (π 1 , π 2 , · · · , π k ). Before the stating Kruskal's Theorem, we need the following.
Definition 3.5. Let A be a matrix. The Kruskal (row) rank of a matrix A is the largest number k such that every set of k rows of A are independent.
For example, letting V denote the set of all 3 × 3 matrices, a set of dimension 9, consider matrices of the form where (a, b, c), (d, e, f ) are independent. These matrices have rank 2 but Kruskal rank 1, and form a subset of lower dimension inside the 9-dimensional space V . It is clear that Kruskal rank is less than or equal to matrix rank, but when a matrix has full row rank, the two notions coincide. In subsequent sections, we exploit this observation by creating matrices with full row rank and therefore full Kruskal rank.
Kruskal's theorem can be viewed as a generic identifiability theorem for 3-way arrays, showing that triple products satisfying a particular rank condition are decomposable in essentially a unique way.
Theorem 3.6 (Kruskal [1977]). Let A, B, C be l × n A , l × n B , and l × n C matrices with Kruskal rank p, q, r respectively. If By way of contrast, note that for two compatible matrices A, B, the natural analog of the bracket product is the matrix product [A, B] = A T B. However, from [A, B], A and B can not be determined uniquely, since there are many matrix products that give the same result. For instance, A T B = (QA) T (QB) for any orthogonal matrix Q. Kruskal's theorem thus states a significant difference between matrices and 3-way tensors.
3.2. Generic points in parameter space. Algebraic geometry provides a convenient tool for understanding exceptional sets, like those that fail to satisfy the rank conditions necessary to apply Kruskal's Theorem. We briefly give the needed definitions.
Definition 3.7. Let S be a finite set of polynomials in C[x 1 , . . . , x n ]. The common zero set in C n of the polynomials in S is the algebraic variety V (S). A subset of a variety that is itself a variety is called a subvariety. For any algebraic variety The main result of this work is that PM model parameters are identifiable except for 'rare' choices. This is expressed using the following terminology.
Definition 3.8. A property is generic on a full-dimensional subset W of R n or C n if it holds at all points of W except possibly for those points in some subset U ⊂ W of measure 0. If V is an algebraic variety in C n , we say a property is generic on V if it holds at all points except those in a proper subvariety of V .
Note that proper subvarieties of varieties always have measure 0, so these notions of generic are consistent with one another.
Example 2. The set of 3 × 3 matrices forms a variety V (S) with S = {0}. The property of having rank, or equivalently Kruskal rank, 3 is generic on V , since matrices of rank at most 2, including those of the form (1), lie in a finite union of lower dimensional sets. This subvariety of exceptional matrices is defined by a single polynomial, the 3×3 determinant.
A fundamental tool for drawing conclusions that model parameters are generically identifiable is the following variant of a proposition in Rhodes and Sullivant [2012], which we use repeatedly.
Proposition 3.9. Let Φ : U → C n be an complex analytic map with U an open subset of C ℓ . Let V be a variety in C n . Suppose f ∈ I(V ), and that there exists a point p 1 = Φ(u 1 ) with f (p 1 ) = 0. Then for generic points u ∈ U or u ∈ U ∩ R n , the point Φ(u) lies off of V .
Proof. This follows from basic properties of complex analytic functions of many variables (see, for instance, the text by Range [1986]). The function f • Φ is analytic, and not identically zero. Its zero set is therefore of measure zero, so for generic u ∈ U, Φ(u) lies off V (f ) ⊇ V . The real points in the zero set must similarly have measure zero.
3.3. Rank Propositions. For the proof of our main theorem, the ranks and Kruskal ranks of some special matrices arising in the PM model are needed, and we compile these rank computations here. By giving these algebraic results in advance, the proof of Theorem 5.7 can be presented more cleanly. Note that our arguments depend in part on some computations that were performed with the software Pari/GP. As these computations were performed using exact integer arithmetic, they may be taken as valid proofs, up to the usual assumptions of correct programming and no hardware faults.
We begin by defining a particular structured matrix that can arise from particular parameter choices for the PM model.
Proof. We begin with the special case of ℓ = 3. An exact Pari/GP calculation shows that for m = 77 by picking distinct random integers for a 1 , . . . , a κ for each of the m blocks in M, we may find a point p 1 = M for which M ⊗ 3 r has full row rank. By removing some of the blocks from this example if m < 77 we obtain a point p 1 for which M ⊗ 3 r has full row rank for smaller m as well.
so it is enough to know that the entries of some single column of M ⊗ ℓ−3 r are nonzero and that M ⊗ 3 r has independent rows to ensure M ⊗ ℓ r has independent rows. But this is true for generic choices of parameters for M.
The next proposition gives a lower bound on Kruskal row rank, valid for all M ⊗ ℓ r .
Proposition 3.12. For κ ≥ 2, let M be a mκ × κ matrix formed by stacking m ≥ 1 choices of matrices of the form M(a 1 , . . . , a κ ). For ℓ ≥ 1, M ⊗ ℓ r has Kruskal row rank greater than or equal to 2 for generic choices of the a i .
Proof. Consider first the case that ℓ = 1. The matrices of Kruskal rank at most 1 form an algebraic variety V . By Proposition 3.9, it is enough to find a single matrix M not in V to see that generically such matrices have Kruskal rank at least two. Choose mκ distinct positive small numbers as the free entries a 1 , . . . , a κ in each block of M, so that the diagonal entries are the largest in the block. Then no two rows within any block M(a 1 , . . . , a κ ) are multiples of each other, and no two rows of different blocks are multiples either, since the a i 's are distinct. Thus M has Kruskal rank greater than or equal to two.
The case when ℓ > 1 follows by an argument similar to that at the end of the proof of Proposition 3.11.
The final propositions in this section involve generic ranks of stacked matrices formed by taking certain tensor products of matrices of the form above.
Proposition 3.13. Let M be a mκ 2 ×κ 3 matrix formed by stacking m choices of matrices of the form M(a 1 , · · · , a κ ) ⊗ 2 r ⊗ M(a 1 , · · · , a κ ). Then for κ = 20 and m < 77, the matrix M has rank greater than mκ for generic choices of the a i .
Proposition 3.14. Let M 1 be of the form of M in Proposition 3.13, and M 2 be formed by stacking m matrices of the form M(a 1 , · · · , a κ ) ⊗ M(a 1 , · · · , a κ ) ⊗ 2 r . Let L be a mκ 2 × mκ 2 diagonal matrix with positive entries. Then for κ = 20 and m < 74, M T 2 LM 1 has rank greater than mκ for generic choices of the a i .
The rank computation for m = 4 shows additionally that there exist choices of a i giving rank(M T 2 LM 1 ) = 1480 for larger m , since blocks can be repeated. But 1480 = 20 × 74 so by Proposition 3.9, generically then the rank must be greater than mκ for all m < 74.

Algebraic Aspects of the Profile Mixture Model
Next we relate the algebraic definitions made in the previous section to phylogenetic models and the PM model in particular. We begin by describing how a row tensor product of Markov matrices relates to parameters on a star tree.
Definition 4.1. Let A be a set of taxa on a star tree rooted at its internal node, with pendant edges e 1 , . . . , e |A| and associated Markov matrices M e i . Then For an m-class PM model on a star tree, the matrix M A is of size mκ × κ |A| . Its entries are conditional probabilities of observing different |A|-tuples of states at the taxa in set A, given the state at the root.
Given a tree T on taxa X, tripartitions and splits of X can be associated to the topological structure of T . For instance, the tree of Figure 1   When a tree T displays a tripartition of a set of taxa, then the flattening of a joint distribution corresponding to that tripartition can be expressed using the 3-way matrix product of certain matrices built from model parameters. For establishing generic properties of the PM model, we will often consider the particular choice of the exchangabilities given by the matrix R = 1 whose entries are all 1. This is in essence the CAT-F81 model Philippe, 2004, Le et al., 2008], with the number of profiles some fixed m. For this R, a Markov matrix has the form given in equation (3)  Provided s = 0 (equivalently r = 0), this correspondence is one-to-one.

Identifiability of Parameters for the Profile Mixture Model
With preliminaries completed, we now turn to establishing our main result, on generic parameter identifiability for the PM model. The first step is to understand that the ranks of matrix flattenings of a model distribution are affected by whether the associated split is, or is not, displayed on the tree T .
Proposition 5.1. Let T be an n-taxon tree on X and P a distribution from the model PM= PM (T, κ, m) with κ = 20 and m < 74. Suppose that A|B is a split of X with |A|, |B| ≥ 3.
(1) If A|B is displayed on T , then Flat A|B (P ) has rank at most mκ; (2) If A|B is not displayed on T , then Flat A|B (P ) generically has rank greater than mκ.
Before beginning the proof, we present a simplified example to illustrate how the matrix rank of flattenings of joint distributions from Markov models on trees carries information about the absence/presence of an internal edges on T .
Example 3. Consider a single-class 2-state Markov model on the 4-taxon tree shown in Figure 2. A special case of this model is P M (T, 2, 1). The joint distribution of states at the leave of T is the 2 × 2 × 2 × 2 array P , with entries p ijkl indexed by leaves in the order a, b, c, d.  ((1, 2), (1, 1)) entry is p 1211 . In contrast, if A ′ = {a, c} and B ′ = {b, d}, the flattening Flat A ′ |B ′ (P ) has ((1, 2), (1, 1))-entry is p 1121 . Now suppose that the terminal edges of T have length 0, so that the states at a and b must agree, as must those at c and d, since no substitutions occur on terminal edges. Then the matrix Flat A|B (P ) arises from the joint distribution of states at the internal nodes v 1 and v 2 , and its only non-zero entries are p iijj . Thus the matrix flattening for the split A|B displayed by T has form with rank at most 2 = mκ.
If the terminal edges of T are of positive length, then the resulting joint distribution P can be obtained by a simple and generically rank-preserving linear action on the rows and columns of the flattenings above. Thus, flattenings respecting the topology of T generically have rank mκ while those that do not generically have larger rank.
Proof of Proposition 5.1. To show claim (1), suppose the split A|B is displayed on T with associated edge e = (v A , v B ). Let M A be the mκ×κ |A| matrix and M B the mκ×κ |B| matrix giving the conditional probabilities of jointly observing states at A and B, conditioned on states at v A and v B respectively. Then, by rooting the tree at v A and letting M e denote the mκ × mκ Markov matrix associated to e, the joint distribution of (v A , v B ) is diag(Π)M e and it follows that Since rank(M e ) ≤ mκ, it follows that Flat A|B (P ) has rank at most mκ.
For claim (2), suppose now A|B is not displayed on T . Let V be the variety of matrices of size κ |A| × κ |B| with rank at most mκ, defined by the set of all (mκ + 1) × (mκ + 1) minors. By Proposition 3.9, it suffices to find a single choice of P M(T, κ, m) parameters that produces a point off V , as the parameterization extends to a complex analytic function.
Since T does not display A|B, by Theorem 3.8.6 of Semple and Steel [2003], there is an edge e = (v 1 , v 2 ) of T with associated split C|D such that A ′ = A ∩ C, A ′′ = A ∩ D, B ′ = B ∩ C, B ′′ = B ∩ D are all non-empty. To find the needed choice of parameters, fix all internal edges of T except e to have length 0, so the Markov matrices on these edges are I, and fix the edge lengths of all terminal edges and e to be 1. See Figure 3. Take R = 1 and mixing weights w i = 1/m to be uniform. Values for the parameters π i , r i will be specified later in the argument. For this choice of parameters, T is formed by joining two star trees at the ends of e. Taking r = v 1 to be the root of T , let K = diag(Π)M e be the mκ × mκ block diagonal matrix which is the joint distribution of classes and states at v 1 and v 2 . The probabilities of observing states i, j, k, l at leaves in A ′ , B ′ , A ′′ , B ′′ respectively, P (i, j, k, l), are the Define a mκ × mκ × mκ × mκ tensor Q, The tensor Q is the joint distribution of states at the leaves of the tree T of Figure 3 when terminal edges have length zero and A ′ , B ′ , A ′′ , B ′′ are single taxa. Indeed, since A|B is not displayed on T , the matrix Q = Flat A|B (Q) is (mκ) 2 × (mκ) 2 with entries Q ((i, j), (k, l)) = Q(i, k, j, l).
Since K is block diagonal, Q has at most mκ 2 nonzero entries, all appearing on the diagonal, and Q is generically of rank mκ 2 . To see that in the general case Flat A|B (P ) has a similar structure, let are given as in equation (4) of Definition 4.1. Then We now establish that claim (2) holds when |A| = |B| = 3, so the tree is one of those shown in Figure 4. Suppose first that |A ′ | = |B ′ | = 2 and |A ′′ | = |B ′′ | = 1, as shown for tree (a) of the figure. In this case N A = N B . Since Q is diagonal with at most mκ 2 non-zero entries due to the block structure of K, in equation (5) we can replace Q by a diagonal mκ 2 × mκ 2 matrix Q by eliminating zero rows and columns. To do this, we must also replace N A = N B with an mκ 2 × κ 3 matrix N formed by taking tensor products of the individual class components of M A ′ = M ⊗ 2 r and M A ′′ = M and then restacking. To be concrete, for class c the Markov matrix for a terminal edge is M c = M(a c 1 , . . . , a c κ ) by Lemma 4.3, and N is formed by stacking m matrices (M c ) ⊗ 2 r ⊗ M c . Since Q is diagonal with generically positive entries, using equation (5) we have that Flat A|B (P ) = N T Q 1/2 Q 1/2 N = Λ T Λ, where Λ = Q 1/2 N. By the singular value decomposition, it follows that rank(Λ T Λ) = rank(Λ) = rank(N).
The Pari/GP calculation presented in Proposition 3.13, together with Proposition 3.9 show that rank(N) > mκ generically, and thus for generic π i and r i it follows that rank(Flat A|B (P )) > mκ. Now continuing with |A| = |B| = 3 suppose that |A ′ | = |B ′′ | = 2 and |A ′′ | = |B ′ | = 1, as shown by Figure 4(b). The previous argument fails for this tree because now N A = N B , as the tensor products defining these matrices, are taken in different orders. However, a more complicated Pari/GP calculation, presented as Proposition 3.14, shows that Flat A|B (P ) generically has rank greater than mκ in this case.
Finally, for the general case of |A|, |B| ≥ 3, take A to be a 3-element subset of A with at least one element from A ′ and one from A ′′ , and similarly take B to be a 3-element subset of B with at least one element from B ′ and from B ′′ . Let P be the probability distribution for the taxa A ∪ B. Since the row indices of Flat A|B (P ) depend on the states at the taxa in A and the column indices depend on the states at the taxa in B, marginalizing over all possible states for the taxa in A which are not in A, and similarly for B, gives the matrix Flat A| B ( P ). There exist matrices, J 1 , J 2 which perform this marginalization on Flat A|B (P ), Since Flat A| B ( P ) generically has rank greater than mκ and Flat A|B (P ) has rank greater than or equal to Flat A| B ( P ) by this equation, it follows that Flat A|B (P ) generically has rank greater than mκ.
As a consequence of Proposition 5.1, from a distribution P computed from generic PM model parameters we can identify every edge in the tree for which there are at least three taxa on either side, by computing ranks of flattenings of P . In the following, we see that Proposition 5.1 also helps to identify at least one tripartition on the tree.
Proposition 5.2. Let T be an n-taxon tree on X with n ≥ 9, and P a joint distribution from generic parameters for the model P M(T, κ, m) with κ = 20 and m < 74. Then there is at least one tripartition A|B|C displayed on T , with |A|, |B| ≥ 3, which can be identified from P .
Proof. By Lemma 4.8 of Rhodes and Sullivant [2012], every unrooted binary tree T with n ≥ 3 has an internal vertex v which induces a tripartition A|B|C such that two of the three components contain at least ⌈n/4⌉ leaves of T .
The two edges incident to v that correspond to subsets of X with at least ⌈n/4⌉ leaves are generically identifiable by Proposition 5.1, since for n ≥ 9, ⌈n/4⌉ ≥ 3. If the third edge incident to v has 3 or more taxa in its component, it also can be identified. Thus, it remains to establish that the third edge incident to v can be identified when the number of taxa in its component is 1 or 2. Examples of such trees are illustrated for n = 9 in Figure 5. If the third component has only one leaf, as in Figure 5(a), the two bipartitions A ∪ {c}|B and A|B ∪ {c} are identifiable by Proposition 5.1. Together this implies that the tripartition induced by v is A|B|{c}. If the third component has two leaves as in Figure 5 (b), the two splits A ∪ {c 1 , c 2 }|B and A|B ∪ {c 1 , c 2 } are identifiable, but A ∪ {c 1 }|B ∪ {c 2 } and A ∪ {c 2 }|B ∪ {c 1 } are not displayed on T , and that can be detected by Proposition 5.1. This implies the tripartition A|B|{c 1 , c 2 } is on the tree.
With a tripartition on the tree identifiable by the preceding proposition, we prepare to apply Kruskal's Theorem. Letting P be a joint distribution from P M(T, κ, m), pick an internal vertex v of T inducing such a tripartition A|B|C. Then by Lemma 4.2 Proof. Using Proposition 3.9, it is enough to show there is a single choice of parameters for which the tensor power has full row rank. Let R = 1, and take the terminal branch lengths to be 1. Then by Lemma 4.3 the Markov matrix M e on a terminal edge has the form of stacked matrices of the form M(a 1 , . . . , a κ ). By the Pari/GP calculation of Proposition 3.11, for generic choices of the other parameters, M ⊗ ℓ r e , ℓ ≥ 3, has full row rank.
Using Proposition 3.12 in a similar argument we obtain the following.
Lemma 5.4. Consider the model P M(T, κ, m) with κ ≥ 2 and m ≥ 1. Then for ℓ ≥ 1, the ℓ th row tensor power of the mκ × κ Markov matrix associated to a terminal edge of T generically has Kruskal rank at least 2.
Lemma 5.5. For a distribution from the model P M(T, κ, m) with κ = 20 and m ≤ 77, let M A , M B , M C be the matrices described above. If |A|, |B| ≥ 3, and |C| ≥ 1, then generically M A , M B have full Kruskal rank and M C has Kruskal rank at least 2.
Proof. Using Proposition 3.9, we need only show there is a single choice of parameters for which these rank claims hold. Set all internal branch lengths 0 and all terminal branch lengths 1, so that T is a star tree rooted at the central node v. Then by Lemma 5.3, since |A|, |B| ≥ 3 for generic choices of the profiles π i the matrices M A (and therefore M A ) and M B have full row rank and therefore full Kruskal rank. Also by Lemma 5.4, M C has Kruskal rank at least 2.
We add the last ingredient before the main result.
Proposition 5.6. Suppose T is a tree on X which displays a known tripartition A|B|C corresponding to vertex r with |A|, |B| ≥ 3, |C| ≥ 1. If κ = 20 and m ≤ 77 then both T and the numerical parameters of the PM(T, κ, m) model are generically identifiable, up to arbitrary rescaling of the tree and the exchangeability matrix R.
Proof. Using the notation and result of Lemma 5.5, if a distribution P comes from generic parameters of P M(T, κ, m), then Also, by factoring out row sums from the matrices, we can generically identify the root distribution vector Π at the node r and M A , M B , M C up to simultaneous permutation of the entries of Π and the rows of the matrices. Considering any entry of Π, and supposing that this corresponds to an unknown class u ∈ [m] and state w ∈ [κ], then the same rows of M A , M B , M C correspond to the same class u and state w. Since Kruskal's theorem yields identifiability only up to permutation, we must determine which of the mκ rows of M A , M B , M C correspond to the same fixed class u.
Consider first the special case that |A| = 3 where A = {a, b, c}. Then T , which is generically binary, has a subtrees rooted at r, with leaves A = {x, y, z} as shown in Figure 6, though we do not know which two taxa from a, b, c form the cherry {y, z}. The Markov matrix M A is of size mκ × κ 3 . Choose the ℓ th row of M A where ℓ = (u, w) for unknown u, w. It is a row vector with κ 3 entries, but we can reconfigure it as a 3dimensional tensor of size κ × κ × κ so its (i, j, k)-entry is P (a = i, b = j, c = k | r = ℓ). Since the PM model is time reversible, take v 1 as the root of the subtree in Figure 6. Then for unknown 1 × κ vector π v 1 , and κ × κ Markov matrices M x , M y , M z , M 1 , M 2 for class u on this subtree, the joint distribution of states at x, y, z, r for fixed class u is P (x = i, y = j, z = k, r = (u, w)) = κ α=1 κ β=1 π v 1 (β)M y (β, j)M z (β, k)M 2 (β, α)M 1 (α, w)M x (α, i) where M (u,w) = M 2 diag(M 1 (·, w))M x with M 1 (·, w) denoting the w th column of M 1 . For fixed u this is simply a rescaling of the conditional distribution P (x = i, y = j, z = k | r = (u, w)) given in the ℓ th row of M A .
Thus applying Kruskal's theorem to each row of M A reshaped into such a 3-way tensor, we can decompose P (x = i, y = j, z = k | r = ℓ) for each ℓ = (u, w) into a triple product, as the matrices generically all have rank κ. Note that for each ℓ = (u, w), Kruskal's theorem gives the matrices M y , M z , M (u,w) up to ordering of their κ rows. Two of these matrices, M y , M z , will be dependent only on the class u, but not the state w. So considering all ℓ = (u, w), we can find κ rows of M A with the same (possibly permuted rows) version of M y and M z which correspond to a single class u. In this way we can group the rows of M A , M B , M C with entries of Π by class u. Now taking those rows of M A , M B , M C , and entries of Π for one class u and reassembling them in a 3-way product gives a tensor for a single class GTR model on the full tree T . Both the tree T and numerical parameters are identifiable for this single-class model by Theorem 2.4.
For the general case, suppose |A|, |B| ≥ 3. Then by marginalization down to |A| = 3 we can identify the subtrees and parameters for B, C. Then interchanging the roles of A and B identifies the subtree and parameters for A.
Combining Proposition 5.2 with Proposition 5.6, we have proved the main result.
Theorem 5.7. Let T be a tree with at least 9 taxa. Then under the PM (T, 20, m) model with m < 74, both T and numerical parameters are generically identifiable, up to arbitrary rescaling of the tree and the exchangeability matrix R.
Theorem 5.7 extends to certain tree shapes with fewer than 9 taxa. To apply Proposition 5.6, T must display a tripartition with two of its subsets of size at least 3, so that T must have at least 7 taxa. Such a tripartition will be generically identifiable by the argument given for Proposition 5.2.
Corollary 5.8. For the profile mixture model P M(T, 20, m) with m < 74, parameters are generically identifiable if T has any of the 8-taxon tree shapes (a)-(d) shown in Figure 7, or the 7-taxon caterpillar shape.