divided classifications into two characters: (i) association (host-associated or environmental) and (ii) type of host interaction (parasitic, mutualistic, commensal). Ancestral states were inferred by using parsimony [Mesquite 2.74 (Maddison and Maddison, 2010)]. When two equally parsimonious ancestral state reconstructions were found, we noted the ambiguity and listed a minimum estimate of transitions (Fig. 2.1).
To compare the relative frequencies of host-association origins among different bacterial lineages, we estimated the rate of origins over evolutionary time for each phylum and the complete tree. Rates were calculated by dividing the total number of origins of host association in a lineage by an adjusted sum of the taxon’s branch length. The adjusted sum included only branches on which transitions from an environmental lifestyle to host association could occur (i.e., summed branch length of the taxon minus host-associated descendant branches of previously accounted origins and individual branches on which host association has been lost). The unit of branch length is the expected number of amino acid substitutions per site.
For focal symbiont taxa, we analyzed phylogenies containing the lineages of interest to assess whether host association originated from parasitic ancestors or free-living ancestors and to search for evidence of mutualism breakdown. Ancestral states for symbiotic lineage and evidence of mutualism breakdown were inferred by using parsimony on the available phylogenies (Normand et al., 1996; Turner et al., 1999; Nishiguchi and Nair, 2003; Sawada et al., 2003; Ruby et al., 2005; Svenning et al., 2005; Kaltenpoth et al., 2006, 2009; Kikuchi et al., 2007, 2011; Münchhoff et al., 2007; Williams et al., 2007, 2010; Sachs et al., 2009, 2010a; Mueller et al., 2010).