A New Quartet-Based Statistical Method for Comparing Sets of Gene Trees Is Developed Using a Generalized Hoeffding Inequality

Abstract

Extracting the strength of the tree signal that is encompassed by a collection of gene trees is an exceptionally challenging problem in phylogenomics. Often, this problem not only involves the construction of individual phylogenies based on different genes, which may be a difficult endeavor on its own, but is also exacerbated by many factors that create conflicts between the evolutionary histories of different gene families, such as duplications or losses of genes; hybridization events; incomplete lineage sorting; and horizontal gene transfer, the latter two play central roles in the evolution of eukaryotes and prokaryotes, respectively. In this work, we tackle the aforementioned problem by focusing on quartet trees, which are the most basic unit of information in the context of unrooted phylogenies. In the first part, we show how a theorem of Janson that generalizes the classical Hoeffding inequality can be used to develop a statistical test involving quartets. In the second part, we study real and simulated data using this theoretical advancement, thus demonstrating how the significance of the differences between sets of quartets can be assessed. Our results are particularly intriguing since they nonstandardly require the analysis of dependent random variables.

1. Introduction

Many phylogenomic analyses that dealt with the construction of gene trees (i.e., trees of ancestor–descendant relationships) for separate families of orthologous genes uncovered widespread contradictions among those trees (Galtier and Daubin, 2008). The construction of gene trees is often an intractable task (NP-hard) (Bininda-Emonds et al., 2002), and errors in the constructed trees are to be expected. However, there are biological processes that almost invariably lead to incongruences between inferred gene histories. Several examples are hybridization events, duplications and losses in gene families, incomplete lineage sorting (ILS), and horizontal genetic transfer (HGT) (Maddison, 1997; Doolittle, 1999; Ochman et al., 2000), the latter often regarded as the most prominent one, especially in the prokaryotic world (Treangen and Rocha, 2011). Thus, the underlying microbial phylogeny is usually inferred by constructing gene trees for ribosomal RNA genes, as they are typically considered to be immune to HGT.

Nevertheless, such genes are also known to have experienced HGT events, which obfuscate the central trend of evolutionary relationships (Yap et al., 1999; Schouls et al., 2003; van Berkum et al., 2003; Dewhirst et al., 2005). In addition, as these genes are highly conserved, the amount of evolutionary signal that they provide may be insufficient for reliable classification within a genus or even a family. Facing these disadvantages, it was suggested to construct the underlying species tree by considering a large collection of gene trees and amalgamating them together, an approach known as the supertree operation (Bininda-Emonds et al., 2002; Creevey and McInerney, 2005).

A special case of the supertree operation is the one in which the input is composed solely of quartet trees. Quartet trees, or simply quartets, are unrooted phylogenetic trees with four taxa and are of special interest since they constitute the smallest trees that carry any information in an unrooted context. Indeed, quartets were used as a basis for tree and network constructions in predominantly theoretical works (Holland et al., 2007; Snir and Rao, 2010; Allman et al., 2011; Roch and Snir, 2012; Yang et al., 2014; Davidson et al., 2015; Solís-Lemus and Ané, 2016) and were also considered in studies that focus on real biological data (Zhaxybayeva et al., 2006; Puigbò et al., 2010; Mao et al., 2012; Stenz et al., 2015; Avni and Snir, 2017), when efforts were made to discern between the vertical signals of evolution passed from parent to offspring and the horizontal signals that are the result of HGT or ILS. Despite the above, even the seemingly trivial problem of determining whether or not a collection of quartets is consistent (i.e., whether or not this collection agrees on some tree, see Section 2.1) was found to be NP-complete more than 25 years ago (Steel, 1992). Hence, a rigorous quantitative evaluation of the overall strength of the tree signal that a multitude of quartets support is still lacking.

In this work, we tackle the problem of assessing the general support of a collection of quartets in a vertical inheritance trend. In the first part, we show how a theorem of Janson that generalizes the classical Hoeffding inequality can be applied to quartets. To the best of our knowledge, this is the first time an approach to measure random variables based on quartets is presented, as these random variables are mutually dependent. In the second part, we discuss how sets of quartets can be assigned a measure—the mean plurality score (MPS)—that reflects their overall support of a tree signal. Using the statistical tool that we developed, we study real and simulated data and show how MPS can be used to distinguish between a number of those sets. We note that our proposed method allows one to consider any arbitrary subset of the quartets that are induced by a given collection of species. Thus, it enables one to either compare between whole sets of quartets (and species) or focus on different subsets of the quartets under study, a procedure that may shed light on biological processes that influence the resulting MPSs. Indeed, examples of both types of comparisons are given below.

2. Methods

2.1. Preliminaries

Here, we present the relevant and necessary background information of our work.

2.1.1. Phylogenetic trees

For a set of species (or taxa) \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X} ,$$ \end{document} a phylogenetic \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} -tree t is a tree for which there is a one-to-one correspondence between \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} and the set of leaves of t − \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{L} \left( t \right)$$ \end{document} . The removal of an edge from a tree disconnects the tree into two subtrees and induces a split on the taxa set. The split \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {U , { \cal X} \backslash U} \right)$$ \end{document} identified by the edge e is denoted as e_U or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${e_{{ \cal X} \backslash U}}$$ \end{document} alternatively. Let t be an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} -tree and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal A} \subseteq { \cal X}$$ \end{document} be a subset of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} . We denote by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$t{ \vert _{ \cal A}}$$ \end{document} the subtree that is induced by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal A}$$ \end{document} on t and is thus obtained: First, all the leaves in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X} \backslash { \cal A}$$ \end{document} , as well as paths leading exclusively to them, are removed. Next, all internal nodes (necessarily in paths connecting leaves from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal A}$$ \end{document} ) with degree two are contracted.

2.1.2. Consistent trees and supertrees

For two trees T and t, we say that T satisfies t (alternatively, t is induced by T) if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathcal{L} \left( t \right) \subseteq \mathcal{L} \left( T \right)$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$T{ \vert _{ \mathcal{L} \left( t \right) }} = t$$ \end{document} , otherwise, t is violated by T. For a set of trees \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal T} = \left\{ {{t_1} , \ldots , {t_k}} \right\} $$ \end{document} with possibly overlapping leaves, we say that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal T}$$ \end{document} is consistent if there exists a tree \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${t^{ \rm{*}}}$$ \end{document} that satisfies every tree \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${t_i} \in { \cal T}$$ \end{document} . Otherwise, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal T}$$ \end{document} is inconsistent. The problem of finding such a consistent tree \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${t^{ \rm{*}}}$$ \end{document} is known as the supertree problem. It is generally NP-complete (Steel, 1992). Tree amalgamation, that is, combining several trees into a unified supertree, may be carried out in several ways [see Bininda-Emonds et al. (2002) for some examples]. In general, each such procedure, also known as a supertree method, attempts to find a tree that maximizes a given function relating to the input. Except in a few special cases, this operation is computationally intensive (NP-hard), and heuristic approaches must be employed.

2.1.3. Quartets and the Maximum Quartet Consistency problem

A tree t is rooted if all edges are directed away from a given node, the root. When edges are undirected and there are no ancestor–descendant relationships between the nodes, the tree is unrooted. In this work, we deal only with unrooted trees. In this context, the basic unit of information is a tree with four taxa, a quartet tree. A quartet tree with taxa \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left\{ {a , b , c , d} \right\} $$ \end{document} is denoted by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a , b \vert c , d$$ \end{document} if a split \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( { \left\{ {a , b} \right\} , \left\{ {c , d} \right\} } \right)$$ \end{document} is induced by one of the tree's edges. More generally, a quartet \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$q = a , b \vert c , d$$ \end{document} is satisfied by a tree t if t has a split separating a, b from c, d. Notice that a rooted triplet is always transformed to a star tree in the unrooted case, which contains no biological information. For the same reason, unresolved quartets, that is, quartets whose topology is a star, are ignored in this study. A common special case of the supertree problem is when the input consists solely of quartets and the objective is to find a tree that satisfies the maximum number of quartets. This is denoted the Maximum Quartet Consistency problem.

2.1.4. The plurality inference rule and the plurality quartets

The plurality inference rule functions as a quartet oracle that helps to reconcile conflicting gene trees. As mentioned earlier, gene trees often exhibit remarkable discordance when different gene clusters are studied. Thus, while a given gene tree may induce one topology per one four-taxa set ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a , b \vert c , d$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a , c \vert b , d$$ \end{document} , or \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a , d \vert b , c$$ \end{document} for the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left\{ {a , b , c , d} \right\} $$ \end{document} ), when examining a collection of gene trees, different genes may induce different quartet topologies. In a study that involves a collection of gene trees, the number of trees satisfying each topology is counted. The plurality inference rule assumes that the most prevalent topology is identical to the original topology in the species tree [an assumption that is justified by Roch and Snir (2012)]. The quartet topologies that are inferred using this plurality rule are denoted the plurality quartets.

2.1.5. Quartet plurality scores and MPS

It is noteworthy that the number of “votes” a plurality quartet receives may change from one 4-taxa set to another. We use the term plurality score to denote the percentage of votes a plurality quartet has. For example, if the topology \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$q = a , b \vert c , d$$ \end{document} is induced by 60% of the gene trees, whereas \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$q{ \rm{ \prime }} = a , b \vert c , e$$ \end{document} is induced by 90% of the gene trees, we say that these quartets have 60% and 90% plurality scores, respectively. Unresolved quartets are excluded from this computation. Since there are three different topologies for a given four-taxa set, the sum over these three topologies votes is 100% and the plurality score (of the plurality quartet) is at least one-third. When examining a collection of gene trees, and the accompanying collection of species, each four-taxa set has its own plurality score. Thus, a collection of plurality scores may be constructed. The MPS is defined as the average of those plurality scores. Clearly, since each plurality score ranges between 1/3 and 1, the MPS ranges between 1/3 and 1 as well. Moreover, a high plurality score is an indication of a strong signal of agreement of that four-taxa set, and wide overall agreement among gene trees will lead to high plurality scores in most plurality quartets, and consequently to a high MPS. Thus, while the topology of the plurality quartets may be used to construct hypothesized phylogenies, information about the quality of the tree signal is conveyed through the plurality scores and the MPS.

2.2. The simulation procedure

Ten “species” trees with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n = 1000$$ \end{document} taxa were produced by a computer program we wrote based on the Yule model (Yule, 1924). Subsequently, “gene” trees were generated based on the species trees. As in Roch and Snir (2012), each gene tree was created when a species tree was subjected to an HGT process, which is, a series of HGT events, consistent with a Poisson process of a constant rate. Specifically, we assume that the number of recipients of HGTs per one unit length is a Poisson distributed random variable with parameter \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\lambda$$ \end{document} defined by the user. Once a recipient of HGT was chosen, the donor of HGT was selected randomly and uniformly from all the contemporaneous species of the recipient, and then, an HGT event was simulated by a subtree pruning and regrafting operation. For each simulated species tree, we generated 10 families of gene trees, based on 10 different rates of HGT ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\lambda = 0.01 , { \rm{ \;}}0.02 , \ldots , 0.1$$ \end{document} ), each family consists of 100 gene trees.

2.3. Real data

Real data gene trees, constructed based on 41 archaea and 59 bacteria, were taken from Puigbò et al. (2009; additional data file 2). From that file, we extracted the “NUTs” (nearly universal trees), trees in which at least 90 of the selected 100 taxa studied in the above article are represented. Thus, we found and analyzed a total of 123 NUTs.

3. Results

In this section, we present the results of our study. We first prove a generalization of Hoeffding inequality that relates to quartet plurality scores (see Section 2.1) and develop a statistical test based on this generalization. We then apply the devised test to sets of plurality quartets constructed using either real or simulated data, which enable us to identify several cases where the differences between those sets are statistically significant.

3.1. Mathematical theory

Here, we prove a theoretical result pertaining to dependent random variables indexed by quartets, based on a generalization of Hoeffding inequality (Hoeffding, 1963), which is due to Janson (2004). We use \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathbb{E}X$$ \end{document} to denote the expectation of the random variable X and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathbb{P} \left( {event} \right)$$ \end{document} to denote the probability of event.

We denote by X_q the random variable representing the plurality score of the quartet q. We assume that the phylogenies of two disjoint sets of species are completely independent, and hence, we assume that if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${q_1} \cap {q_2} = { \not 0}$$ \end{document} , then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${X_{{q_1}}}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${X_{{q_2}}}$$ \end{document} are independent random variables. More generally, we assume that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${X_{{q_0}}}$$ \end{document} is independent of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${X_{{q_1}}} , {X_{{q_2}}} , \ldots , {X_{{q_m}}}$$ \end{document} if the following condition pertaining to the quartets \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${q_0} , {q_1} , \ldots , {q_m}$$ \end{document} holds: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {q_0} \cap \left( { \cup _{i = 1}^m{q_i}} \right) = { \not 0}. \tag{1} \end{align*} \end{document}

Our main theoretical result is the following:

Lemma 3.1 Suppose that Q is the set of all \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {_4^n} \right)$$ \end{document} quartets induced by a set of taxa \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left\{ {1 , 2 , \ldots , n} \right\} $$ \end{document} and that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\bar X = \frac { 1 } { { \left( { _4^n } \right) } } \sum \nolimits_ { q \in Q } { { X_q } } $$ \end{document} . Then, for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$t > 0 ,$$ \end{document}

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mathbb { P } \left( { \bar X \ge \mathbb { E } \bar X + t } \right) \le { \rm { \; } } exp \left( { - \frac { 9 } { 2 } . { \frac { \left( { _4^n } \right) { t^2 } } { \left( { _4^n } \right) - \left( { _4^ { n - 4 } } \right) } } } \right) , \tag { 2 } \end{align*} \end{document}

which can be approximated to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mathbb{P} \left( { \bar X \ge \mathbb{E} \bar X + t} \right) \, \le \,exp \, \left( { - n \left( {9 / 32 + o \left( 1 \right) } \right) {t^2}} \right). \tag{3} \end{align*} \end{document}

The same holds for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathbb{P} \left( { \bar X \le \mathbb{E} \bar X - t} \right).$$ \end{document}

Before proving Lemma 3.1, we recall the definition of a dependency graph (Janson, 2004): for a set of random variables \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \left\{ {{X_ \alpha }} \right\} _{ \alpha \in {\cal A} }} ,$$ \end{document} a dependency graph is any graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ \Gamma }}$$ \end{document} with vertex set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal A}$$ \end{document} such that if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal B} \; \subseteq \;{ \cal A}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\alpha \in \;{ \cal A}$$ \end{document} is not connected by an edge to any vertex in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\cal B}$$ \end{document} , then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${X_ \alpha }$$ \end{document} is independent of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \left\{ {{X_ \beta }} \right\} _{ \beta \; \in \;{ \cal B} }}.$$ \end{document} Notice that in most cases, a dependency graph for a given set of random variables is not unique. The following theorem, due to Janson (2004) (theorem 2.1), extends the classical Hoeffding inequality (Hoeffding, 1963). We present here a simplified version that better suits our needs:

Theorem 3.2 Suppose that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X = \sum \nolimits_{ \alpha \; \in \;{ \cal A} } {{X_ \alpha }}$$ \end{document} where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \{ {X_ \alpha } \} _{ \alpha \; \in \;{ \cal A} }}$$ \end{document} are random variables and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \{ {a_ \alpha } , \,{b_ \alpha } \} _{ \alpha \; \in \;{ \cal A} }}$$ \end{document} are real numbers such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${a_ \alpha } \le {X_ \alpha } \le {b_ \alpha }$$ \end{document} for all \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\alpha \in { \cal A}$$ \end{document} . Then, for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$t > 0$$ \end{document} and every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Gamma$$ \end{document} , which is a dependency graph for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \{ {X_ \alpha } \} _{ \alpha \; \in \;{ \cal A} }} ,$$ \end{document} we have

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mathbb { P } \left( { X \ge \mathbb { E } X + t } \right) , \mathbb { P } \left( { X \le \mathbb { E } X - t } \right) \le { \rm { \; } } exp { \rm { \; } } \left( { - 2 { \frac { { t^2 } } { \left( { { \rm { \Delta } } \left( { \rm { \Gamma } } \right) + 1 } \right) \mathop \sum \nolimits_ { \alpha \; \in \; { \cal A } } { \rm { } } { { ( { b_ \alpha } - { a_ \alpha } ) } ^2 } } } } \right) , \tag { 4 } \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ \Delta }} \left( { \rm{ \Gamma }} \right)$$ \end{document} denotes the maximum degree of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ \Gamma }}{ \rm{.}}$$ \end{document}

We now turn to proving Lemma 3.1.

Proof: We define the following graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G = \left( {V , \,E} \right)$$ \end{document} : We define \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V = Q ,$$ \end{document} that is, the set of vertices V is the set of all \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {_4^n} \right)$$ \end{document} quartets. We then connect \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${q_1} , {q_2} \in Q \; ( {q_1} \ne {q_2} )$$ \end{document} by an edge if and only if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${q_1} \cap {q_2} \ne { \not 0}$$ \end{document} and define the set of edges E as the collection of all edges thus constructed. Let us explain why G is a dependency graph for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \left\{ {{X_q}} \right\} _{q \in Q}}$$ \end{document} . Indeed, if q₀ is not connected to any vertex in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left\{ {{q_1} , {q_2} , \ldots , {q_m}} \right\} $$ \end{document} , then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${q_0} \cap {q_k} = { \not 0}$$ \end{document} for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$k = 1 , 2 , \ldots , m.$$ \end{document} This implies that (1) holds and thus \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${X_{{q_0}}}$$ \end{document} is independent of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left\{ {{X_{{q_1}}} , {X_{{q_2}}} , \ldots , {X_{{q_m}}}} \right\} ,$$ \end{document} as required.

Clearly, the number of vertices in G is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( {_4^n} \right) = {n^4} \left( {1 / 24 + o \left( 1 \right) } \right)$$ \end{document} . The degree of any edge in G can be readily calculated: Since a quartet is not connected to itself, nor to any of the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( { _4^{ n - 4}} \right)$$ \end{document} quartets with which it has no elements in common, the degree of any vertex in G is

We now estimate \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathbb{P} \left( { \bar X \ge \mathbb{E} \bar X + t} \right).$$ \end{document} The following is obvious:

We apply (4) to the right-hand side of (6). Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \left\{ {{X_q}} \right\} _{q \in Q}}$$ \end{document} are random variables of plurality scores, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$1 / 3 \le {X_q} \le 1$$ \end{document} for all \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$q \in Q$$ \end{document} , so we set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${a_ \alpha } \equiv 1 / 3 , \,{b_ \alpha } \equiv 1$$ \end{document} and get

Combining (6), (7), and (5), we conclude that

which establishes (2). Furthermore, since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ \Delta }} \left( G \right) = {n^3} \left( {2{ \rm{ / }}3 + o \left( 1 \right) } \right) , \left( {_4^n} \right) = {n^4} \left( {1{ \rm{ / }}24 + o \left( 1 \right) } \right) ,$$ \end{document} we write

which establishes (3) and completes the proof. ▪

Theorem 3.2 enables one to prove the following:

Corollary 1 Let us assume that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${Y_1} , {Y_2} , \ldots , {Y_k} , {Z_1} , {Z_2} , \ldots , {Z_m}$$ \end{document} are random variables in the interval \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left[ {a , b} \right]$$ \end{document} . We define \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A = \left\{ {{Y_1} , {Y_2} , \ldots , {Y_k}} \right\} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B = \left\{ {{Z_1} , {Z_2} , \ldots , {Z_m}} \right\} $$ \end{document} . We also define \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\bar Y = \frac { 1 } { n } \sum \nolimits_ { i = 1 } ^k { { Y_i } } { \rm { } } $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\bar Z = \frac { 1 } { m } \sum \nolimits_ { i = 1 } ^m { { Z_i } } $$ \end{document} . Then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mathbb { P } \left( { \bar Y - \bar Z - \left( { \mathbb { E } \bar Y - \mathbb { E } \bar Z } \right) \ge t } \right) \le { \rm { \; } } exp { \rm { \; } } \left( { - 2 { \frac { { t^2 } } { \left( { { \rm { \Delta } } \left( { { \rm { \Gamma } } \left( { A , B } \right) } \right) + 1 } \right) { { ( b - a ) } ^2 } \left( { \frac { 1 } { k } + \frac { 1 } { m } } \right) } } } \right) , \tag { 10 } \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ \Gamma }} \left( {A , B} \right)$$ \end{document} is any dependency graph of the union \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \cup B = \left\{ {{Y_1} , {Y_2} , \ldots , {Y_k} , {Z_1} , {Z_2} , \ldots , {Z_m}} \right\} $$ \end{document} .

In addition, if Z_j is independent of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A = \left\{ {{Y_1} , {Y_2} , \ldots , {Y_k}} \right\} $$ \end{document} for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$j = 1 , 2 , \ldots , m$$ \end{document} and Y_i is independent of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B = \left\{ {{Z_1} , {Z_2} , \ldots , {Z_m}} \right\} $$ \end{document} for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i = 1 , 2 , \ldots , k$$ \end{document} , then (10) can be simplified to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mathbb { P } \left( { \bar Y - \bar Z - \left( { \mathbb { E } \bar Y - \mathbb { E } \bar Z } \right) \ge t } \right) \le { \rm { \;exp \; } } \left( { - 2 { \frac { { t^2 } } { \left( { { \rm { \;max \; } } \left( { { \rm { \Delta } } \left( { { \rm { \Gamma } } \left( A \right) } \right) , { \rm { \Delta } } \left( { { \rm { \Gamma } } \left( B \right) } \right) } \right) + 1 } \right) { { ( b - a ) } ^2 } \left( { \frac { 1 } { k } + \frac { 1 } { m } } \right) } } } \right). \tag { 11 } \end{align*} \end{document}

The proof of Corollary 1 can be found in the Supplementary Material. In the next section, we will show examples of how this corollary may be used.

3.2. Applications

As mentioned above, quartet trees may be used as input for computer programs that implement heuristic methods of phylogenetic construction based on the supertree approach. However, determining the overall agreement among the input quartets in a quantitative way remains a largely open problem. We offer MPS as a measure of the strength of this agreement. Several examples, applying the theory of Section 3.1 to simulated data and then to real data, demonstrate how this measure can be used.

3.2.1. Simulation runs

Here, we employ the theory we developed in Section 3.1 in several tests involving simulated gene trees. The gene trees were constructed by subjecting simulated species trees to an HGT process of a certain “rate.” We briefly mention that an HGT rate \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\lambda$$ \end{document} implies an expected value of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\lambda$$ \end{document} HGT events per 1 U length of the tree. The gene trees, having \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n = 1000$$ \end{document} leaves each, were divided into disjoint sets based on the HGT rates that underlie their construction. We used the HGT rates of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\lambda = 0.01 , 0.02 , \ldots , 0.1$$ \end{document} , thus a total of 10 sets of simulated gene trees were constructed, with 100 trees in each set. See Section 2.2 for details.

We test the statistical significance of the differences between the sets of simulated gene trees. For each set of gene trees, we consider \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Big ( { \begin{matrix} n \\ 4 \end{matrix} }\Big )$$ \end{document} random variables ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n = 1000$$ \end{document} ), representing the plurality scores of the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Big ( { \begin{matrix} n \\ 4 \\ \end{matrix} } \Big )$$ \end{document} quartets they induce. Thus, we computed the MPS of each of the 10 sets of gene trees aforementioned. We note that an increase in the rate of HGT events implies an increase in the number of quartets that are affected by HGT, a fact that is likely to weaken the strength of the tree signal that those quartets support. Consequently, we expect the MPS to be inversely correlated with the rate of HGT. Since the plurality score of each quartet, as induced by each set of gene trees, is completely independent of all the other gene trees sets, we use inequality (11) to estimate the probability of the difference between two MPSs, but first, we replace the inequality's parameters with concrete numeric values. In accordance with Corollary 1, when comparing two sets of gene trees, we define \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A = \left\{ {{Y_1} , {Y_2} , \ldots , {Y_{ \left( { \begin{matrix} n \\ 4 \\ \end{matrix} } \right) }}} \right\} $$ \end{document} to be the plurality scores of all \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Big ( { \begin{matrix} n \\ 4 \end{matrix} }\Big )$$ \end{document} quartets as computed based on the first set and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B = \left\{ {{Z_1} , {Z_2} , \ldots , {Z_{ \left( { \begin{matrix} n \\ 4 \\ \end{matrix} } \right) }}} \right\} $$ \end{document} to be the plurality scores of all \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Big ( { \begin{matrix} n \\ 4 \end{matrix} }\Big )$$ \end{document} quartets as computed based on the second set. The null hypothesis that we test is that the two MPSs are identical, hence we assume that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathbb{E} \bar Y = \mathbb{E} \bar Z$$ \end{document} . Naturally, since we deal with plurality scores, we set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a = 1 / 3$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$b = 1$$ \end{document} . Furthermore, we consider all \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Big ( { \begin{matrix} n \\ 4 \end{matrix} }\Big )$$ \end{document} quartets in this analysis, hence we set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$k = m = \Big ( { \begin{matrix} n \\ 4 \end{matrix} }\Big )$$ \end{document} (for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n = 1000$$ \end{document} ). Finally, as in the proof of Lemma 3.1, for both A and B, we can construct dependency graphs whose maximal degree is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\Big ( { \begin{matrix} n \\ 4 \end{matrix} }\Big ) - \Big ( { \begin{matrix} {n - 4} \\ 4 \\ \end{matrix} } \Big ) - 1$$ \end{document} . Thus, we may write \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ \Delta }} \left( {{ \rm{ \Gamma }} \left( A \right) } \right) = { \rm{ \Delta }} \left( {{ \rm{ \Gamma }} \left( B \right) } \right) = \Big ( { \begin{matrix} n \\ 4 \\ \end{matrix} } \Big ) - \Big ( { \begin{matrix} {n - 4} \\ 4 \\ \end{matrix} } \Big) - 1$$ \end{document} . Replacing those into inequality (11), we get

In Table 1, we see the HGT rates and MPSs of the 10 sets of gene trees, as well as the resulting estimations of the probabilities of their differences based on inequality (12). The cells in the table are marked based on the following rule: if the probability is greater than 5%, the cell is marked with a gray circle; if it is between 1% and 5%, the cell is marked with a gray triangle; and if it is lesser than 1%, the cell is marked with a gray rhombus. First, Table 1 demonstrates that an increase in the rate of HGT results in a decrease in the MPS, as to be expected. Second, we see that the resulting differences in the MPSs between the different sets of quartets are at times statistically significant, with a probability of less than 5% or even less than 1% for them to occur by chance. Thus, the theory developed in the previous section is used to refute the null hypothesis of no significant differences between the MPSs, which implies a fundamental difference in the HGT rates, in some of the cases we test.

Table 1.

Mean Plurality Scores and Estimations of Probability of Differences

HGT rate		0.01	0.02	0.03	0.04	0.05	0.06	0.07	0.08	0.09	0.1
	MPS	0.944297	0.893152	0.832823	0.790318	0.758686	0.723079	0.680982	0.662934	0.635024	0.607557
0.01	0.944297	•1	•0.6911	•0.1728	▴0.0351	⧫0.0077	⧫0.001	⧫6E-05	⧫1E-05	⧫1E-06	⧫1E-07
0.02	0.893152	•0.6911	•1	•0.598	•0.2245	•0.0778	▴0.0168	⧫0.0017	⧫0.0006	⧫8E-05	⧫1E-05
0.03	0.832823	•0.1728	•0.598	•1	•0.7748	•0.4601	•0.1824	▴0.0385	▴0.017	⧫0.004	⧫0.0008
0.04	0.790318	▴0.0351	•0.2245	•0.7748	•1	•0.8682	•0.528	•0.1848	•0.101	▴0.0332	⧫0.0089
0.05	0.758686	⧫0.0077	•0.0778	•0.4601	•0.8682	•1	•0.836	•0.4262	•0.2739	•0.1153	▴0.0397
0.06	0.723079	⧫0.001	▴0.0168	•0.1824	•0.528	•0.836	•1	•0.7785	•0.5999	•0.3344	•0.1518
0.07	0.680982	⧫6E-05	⧫0.0017	▴0.0385	•0.1848	•0.4262	•0.7785	•1	•0.955	•0.742	•0.4669
0.08	0.662934	⧫1E-05	⧫0.0006	▴0.017	•0.101	•0.2739	•0.5999	•0.955	•1	•0.8958	•0.6484
0.09	0.635024	⧫1E-06	⧫8E-05	⧫0.004	▴0.0332	•0.1153	•0.3344	•0.742	•0.8958	•1	•0.8989
0.1	0.607557	⧫1E-07	⧫1E-05	⧫0.0008	⧫0.0089	▴0.0397	•0.1518	•0.4669	•0.6484	•0.8989	•1

The table presents the estimations of the probabilities of the differences between the MPSs of the different sets of simulated gene trees, as computed using inequality (12). The cells of the table are marked based on those estimations: if the probability is greater than 5%, the cell is marked with a gray circle; if the probability is 1%–5%, the cell is marked with a gray triangle; and if the probability is lesser than 1%, the cell is marked with a gray rhombus.

HGT, horizontal gene transfer; MPS, mean plurality score.

3.2.2. Real data analysis

Here, we demonstrate how our theoretical result can be applied to real data analysis. A key difference between studies of real data gene trees and simulated gene trees is the pattern of HGT events. While we were able to impose a uniform HGT model on the construction of simulated gene trees, we clearly have no control over the HGT events that affect the evolution of genes in nature. Indeed, several articles specifically mention a variety of causes that yield biased HGTs, such as toxicity (Sorek et al., 2007), phylogenetic proximity (Popa et al., 2011; Skippington and Ragan, 2012), gene function (Beiko et al., 2005; Nakamura et al., 2004; Wellner et al., 2007), or restricted recombination (Thomas and Nielsen, 2005). Therefore, real HGT events are expected to be nonuniform. In this section, we test whether a pattern of domain-dependent biased HGTs can be detected.

We study a collection of gene trees that was first constructed and studied in Puigbò et al. (2009), based on a set of 100 species (41 archaea and 59 bacteria). In this article, we focus on a collection of 123 NUTs, that is, gene trees with at least 90 taxa that are of particular interest because of their relatively high stability (Puigbò et al., 2010). We divided the plurality quartets that the NUTs induce into three disjoint sets: quartets with four archaea, quartets with four bacteria, and quartets with two archaea and two bacteria. For brevity, we refer to these groups of quartets as a4b0, a0b4, and a2b2, respectively. For simplicity, quartets with three archaea and one bacterium or with one archaeon and three bacteria are ignored. It is noteworthy that genes that evolve with no HGT events also induce a perfect separation between the archaea and the bacteria. Moreover, intra-domain HGTs (involving two archaea or two bacteria) cannot violate this archaea–bacteria separation since they do not involve the transfer of genetic information between the two domains. Hence, we expect the plurality scores of a2b2 quartets that are less than 100% to reflect inter-domain HGTs, involving one archaeon and one bacterium. Similarly, plurality scores of a4b0 quartets and a0b4 quartets are likely to reflect intra-archaea and intra-bacteria HGTs, respectively. Therefore, our goal was to compute the MPSs of the three quartet sets separately and to test the significance of the differences between them.

In Table 2, we present the number of quartets and the MPSs of the three quartet sets above. The results show that a0b4 quartets have the lowest MPS, a4b0 quartets have a higher MPS, and a2b2 quartets have the highest MPS. As the MPS is inversely correlated with the rate of HGT (see previous section), this is indicative of a relatively high rate of intra-bacteria HGTs compared with intra-archaea HGTs, and an inter-domain HGT rate, which is smaller than both intra-domain HGT rates.

Table 2.

Information Regarding Real Data Quartets

Quartet set	No. of quartets	MPS
a0b4	455126	0.57
a2b2	1403020	0.87
a4b0	101270	0.73

The table presents the information relevant to the three sets of real data quartets tested. It includes the type of quartet set, the number of quartets in each set, and the computed MPSs.

Our null hypothesis is that the differences between the computed MPSs are not significant. In accordance with Corollary 1, we test this hypothesis based on inequality (10). The results are presented in Table 3. Three pairs of quartet sets were evaluated: a4b0-a2b2; a4b0-a0b4; a2b2-a0b4, where each row in Table 3 corresponds to one pair. As in Corollary 1, when comparing two sets of quartets, we define \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A = \left\{ {{Y_1} , {Y_2} , \ldots , {Y_k}} \right\} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B = \left\{ {{Z_1} , {Z_2} , \ldots , {Z_m}} \right\} $$ \end{document} to be the random variables representing the plurality scores of the quartets of the first and the second set, respectively. The parameter t, representing the difference between the MPSs, was computed based on Table 2. As in the proof of Lemma 3.1, we construct a dependency graph for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \cup B$$ \end{document} in which two quartets are connected by a branch if and only if they have at least one species in common. The corresponding values of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ \Delta }} \left( {{ \rm{ \Gamma }} \left( {A , B} \right) } \right)$$ \end{document} for each row (i.e., the maximum degree of the dependency graph thus constructed) were found in a direct computation using a script that we wrote.

Table 3.

Probability Estimations of the Differences Between the Real Data Mean Plurality Scores

A	B	k	m	t	Δ(Γ(A,B))	Probability estimation
a0b4 quartets	a2b2 quartets	455126	1403020	0.3	299390	0.63
a0b4 quartets	a4b0 quartets	455126	101270	0.16	114070	0.92
a2b2 quartets	a4b0 quartets	1403020	101270	0.14	298718	0.97

The table presents the information needed to estimate the significance of the differences between the computed real data MPSs. A and B represent the compared quartet sets, k and m represent the number of elements in A and B, respectively, (corresponding to Table 2), t represents the difference between the relevant MPSs, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ \Delta }} \left( {{ \rm{ \Gamma }} \left( {A , B} \right) } \right)$$ \end{document} is the maximum degree of the constructed dependency graph of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A \cup B$$ \end{document} , and the resulting probability estimation is based on the right-hand side of inequality (10).

Finally, we assume \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\mathbb{E} \bar Y = \mathbb{E} \bar Z$$ \end{document} (as implied by the null hypothesis) and set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a = 1 / 3 , b = 1$$ \end{document} (since every plurality scores is bounded from below and above by 1/3 and 1). Plugging all of these into inequality (10), we get the probability estimations of the differences in the MPSs shown in Table 3. As Table 3 shows, the probabilities of the differences between the computed MPSs are no greater than 63% or more. Thus, the null hypothesis is not rejected in any of the cases pertaining to real data that we study. This is partly related to the size of the species set, as we explain in the following section.

4. Discussion and Conclusion

Our study focuses on measuring the overall agreement within a set of quartet trees. In the first part of this work, we proved a lemma that formed the basis on which a statistical test for comparing different sets of quartets was developed, and in the second part, we applied the newly developed theory to several sets of quartets, constructed using either real or simulated data. We note that the two applications of the theory differ slightly: In the simulated data study, the set of taxa was fixed and 10 disjoint collections of gene trees were investigated, whereas in the real data study, the genes set was fixed and three disjoint sets of quartets were investigated. Thus, the simulated data application deals with how HGT impacts different sets of genes, whereas the real data application deals with how HGT impacts different sets of quartets (and indirectly, different sets of species). We found that the test we devised was sufficient to reject the null hypothesis of identical MPSs in some of the simulated data comparisons. However, the null hypothesis was not rejected in the cases that involved real data quartets.

The difference in size between the real and simulated species sets ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n = 100$$ \end{document} versus \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n = 1000$$ \end{document} ) is one of the reasons why the null hypothesis was not rejected in the real data case. Indeed, we remark that asymptotically, the probability of a difference of t between two MPSs is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ \;exp \;}} \left( { - O \left( {n{t^2}} \right) } \right)$$ \end{document} . This implies that if the number of species n is reduced by a factor of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\alpha$$ \end{document} , the difference t should be multiplied by a factor of roughly \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\sqrt \alpha$$ \end{document} to achieve the same estimation of the probability. Thus, a difference of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$t \approx 0.3$$ \end{document} was found to be significant in a simulation study (with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n = 1000$$ \end{document} ) but not in a real data study (with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$n = 100$$ \end{document} ). We regard this as a disadvantage of our theory. The last comment notwithstanding, we believe that this work is appealing primarily since it shows, using novel mathematical tools, how statistical methods can be applied to a multitude of quartets, despite their mutual dependencies. As such, it is the first of its kind to the best of our knowledge.

It is noteworthy that the real data trees differ from the simulated ones in another significant way. Specifically, while in the simulated gene trees, one can ensure every species is represented in every tree, and when analyzing real data, this is clearly not the case. The real data gene trees vary in size, as some of the species are absent from some of the trees. Although in our study we found that any real data quartet was sampled at least 50 times (i.e., present in at least 50 gene trees), which we believe is enough for a reliable estimation of its plurality score, this phenomenon has a potentially deleterious effect on our computations: It can result in quartets that are sampled a small number of times and are thus assigned unreliable plurality scores. In the future, we plan to develop a theory that takes under consideration the number of gene trees each quartet is found in, or equivalently, the number of “votes” each quartet receives. Since increasing the number of votes is also likely to improve the accuracy of the assigned plurality score, we hope that by incorporating these data into the theory, we will be able to discard unreliable quartets and establish more powerful statistical tests.

Footnotes

Acknowledgments

The authors wish to acknowledge the Israel Science Foundation (ISF) for its kind support in performing this research. We thank Michael Cwikel for fruitful discussions concerning the proof of Corollary 1.

Author Disclosure Statement

The authors declare that no competing financial interests exist.

References

Allman

E.S.

, Degnan

J.H.

, and Rhodes

J.A.

2011. Identifying the rooted species tree from the distribution of unrooted gene trees under the coalescent. J. Math. Biol. 62, 833–862.

Avni

, and Snir

2017. Toxic genes present a unique phylogenetic signature. Mol. Phylogenet. Evol. 116, 141–148.

Beiko

R.G.

, Harlow

T.J.

, and Ragan

M.A.

2005. Highways of gene sharing in prokaryotes. Proc. Natl. Acad. Sci. U. S. A. 102, 14332–14337.

Bininda-Emonds

O.R.P.

, Gittleman

J.L.

, and Steel

M.A.

2002. The (super)tree of life: Procedures, problems, and prospects. Annu. Rev. Ecol. Syst. 33, 265–289.

Creevey

C.J.

, and McInerney

J.O.

2005. Clann: Investigating phylogenetic information through supertree analyses. Bioinformatics, 21, 390–392.

Davidson

, Vachaspati

, Mirarab

, et al. 2015. Phylogenomic species tree estimation in the presence of incomplete lineage sorting and horizontal gene transfer. BMC Genomics, 16, S1.

Dewhirst

F.E.

, Shen

, Scimeca

M.S.

, et al. 2005. Discordant 16S and 23S rRNA gene phylogenies for the genus Helicobacter: Implications for phylogenetic inference and systematics. J. Bacteriol. 187, 6106–6118.

Doolittle

W.F.

1999. Phylogenetic classification and the universal tree. Science, 284, 2124–2129.

Galtier

, and Daubin

2008. Dealing with incongruence in phylogenomic analyses. Philos. Trans. R. Soc. Lond. B. Biol. Sci. 363, 4023–4029.

10.

Hoeffding

1963. Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58, 13–30.

11.

Holland

, Conner

, Huber

, et al. 2007. Imputing supertrees and supernetworks from quartets. Syst. Biol. 56, 57–67.

12.

Janson

2004. Large deviations for sums of partly dependent random variables. Random Struct. Algorithms, 24, 234–248.

13.

Maddison

W.P.

1997. Gene trees in species trees. Syst. Biol. 46, 523–536.

14.

Mao

, Williams

, Zhaxybayeva

, et al. 2012. Quartet decomposition server: A platform for analyzing phylogenetic trees. BMC Bioinformatics, 13, 123.

15.

Nakamura

, Itoh

, Matsuda

, et al. 2004. Biased biological functions of horizontally transferred genes in prokaryotic genomes. Nat. Genet. 36, 760–766.

16.

Ochman

, Lawrence

J.G.

, and Groisman

E.A.

2000. Lateral gene transfer and the nature of bacterial innovation. Nature, 405, 299–304.

17.

Popa

, Hazkani-Covo

, Landan

, et al. 2011. Directed networks reveal genomic barriers and DNA repair bypasses to lateral gene transfer among prokaryotes. Genome Res. 21, 599–609.

18.

Puigbò

, Wolf

, and Koonin

2009. Search for a ‘tree of life’ in the thicket of the phylogenetic forest. J. Biol. 8, 59.

19.

Puigbò

, Wolf

, and Koonin

2010. The tree and net components of prokaryote evolution. Genome Biol. Evol. 2, 745–756.

20.

Roch

, and Snir

2012. Recovering the tree-like trend of evolution despite extensive lateral genetic transfer: A probabilistic analysis. In RECOMB. 224–238. Chor

(ed). Springer, Berlin-Heidelberg.

21.

Schouls

L.M.

, Schot

C.S.

, and Jacobs

J.A.

2003. Horizontal transfer of segments of the 16S rRNA genes between species of the Streptococcus anginosus group. J. Bacteriol. 185, 7241–7246.

22.

Skippington

, and Ragan

2012. Phylogeny rather than ecology or lifestyle biases the construction of Escherichia coli-Shigella genetic exchange communities. Open Biol. 2, 120112.

23.

Snir

, and Rao

2010. Quartets maxcut: A divide and conquer quartets algorithm. IEEE/ACM Trans. Comput. Biol. Bioinform. 7, 704–718.

24.

Solís-Lemus

, and Ané

2016. Inferring phylogenetic networks with maximum pseudolikelihood under incomplete lineage sorting. PLoS Genet. 12, 1–21.

25.

Sorek

, Zhu

, Creevey

C.J.

, et al. 2007. Genome-wide experimental determination of barriers to horizontal gene transfer. Science, 318, 1449–1452.

26.

Steel

1992. The complexity of reconstructing trees from qualitative characters and subtress. J. Classif. 9, 91–116.

27.

Stenz

N.W.M.

, Larget

, Baum

D.A.

, et al. 2015. Exploring tree-like and non-tree-like patterns using genome sequences: An example using the inbreeding plant species arabidopsis thaliana (l.) heynh. Syst. Biol. 64, 809–823.

28.

Thomas

C.M.

, and Nielsen

K.M.

2005. Mechanisms of, and barriers to, horizontal gene transfer between bacteria. Nat. Rev. Microbiol. 3, 711–721.

29.

Treangen

T.J.

, and Rocha

E.P.C.

2011. Horizontal transfer, not duplication, drives the expansion of protein families in prokaryotes. PLoS Genet. 7, 1–12.

30.

van Berkum

, Terefework

, Paulin

, et al. 2003. Discordant phylogenies within the rrn loci of rhizobia. J. Bacteriol. 185, 2988–2998.

31.

Wellner

, Lurie

M.N.

, and Gophna

2007. Complexity, connectivity, and duplicability as barriers to lateral gene transfer. Genome Biol. 8, R156.

32.

Yang

, Grünewald

, Xu

, and Wan

X.-F.

2014. Quartet-based methods to reconstruct phylogenetic networks. BMC Syst. Biol. 8, 21.

33.

Yap

W.H.

, Zhang

, and Wang

1999. Distinct types of rrna operons exist in the genome of the Actinomycete Thermomonospora chromogena and evidence for horizontal transfer of an entire rRNA operon. J. Bacteriol. 181, 5201–5209.

34.

Yule

1924. A mathematical theory of evolution based on the conclusions of Dr. J. C. Willis, F. R. S. Philos. Trans. R. Soc. Lond. B. Biol. Sci. 213, 21–87.

35.

Zhaxybayeva

, Gogarten

J.P.

, Charlebois

R.L.

, et al. 2006. Phylogenetic analyses of cyanobacterial genomes: Quantification of horizontal gene transfer events. Genome Res. 16, 1099–1108.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.13 MB