Cyanobacteria belonging to the genus Nostoc comprise free-living strains and also facultative plant symbionts. Symbiotic strains can enter into symbiosis with taxonomically diverse range of host plants. Little is known about genomic changes associated with evolutionary transition of Nostoc from free-living to plant symbiont. Here, we compared the genomes derived from 11 symbiotic Nostoc strains isolated from different host plants and infer phylogenetic relationships between strains. Phylogenetic reconstructions of 89 Nostocales showed that symbiotic Nostoc strains with a broad host range, entering epiphytic and intracellular or extracellular endophytic interactions, form a monophyletic clade indicating a common evolutionary history. A polyphyletic origin was found for Nostoc strains which enter only extracellular symbioses, and inference of transfer events implied that this trait was likely acquired several times in the evolution of the Nostocales. Symbiotic Nostoc strains showed enriched functions in transport and metabolism of organic sulfur, chemotaxis and motility, as well as the uptake of phosphate, branched-chain amino acids, and ammonium. The genomes of the intracellular clade differ from that of other Nostoc strains, with a gain/enrichment of genes encoding proteins to generate l-methionine from sulfite and pathways for the degradation of the plant metabolites vanillin and vanillate, and of the macromolecule xylan present in plant cell walls. These compounds could function as C-sources for members of the intracellular clade. Molecular clock analysis indicated that the intracellular clade emerged ca. 600 Ma, suggesting that intracellular Nostoc symbioses predate the origin of land plants and the emergence of their extant hosts.

Dinitrogen (N₂)-fixation by cyanobacteria in symbiosis with feathermosses is the primary pathway of biological nitrogen (N) input into boreal forests. Despite its significance, little is known about the cyanobacterial gene repertoire and regulatory rewiring needed for the establishment and maintenance of the symbiosis. To determine gene acquisitions and regulatory changes allowing cyanobacteria to form and maintain this symbiosis, we compared genomically closely related symbiotic-competent and -incompetent Nostoc strains using a proteogenomics approach and an experimental set up allowing for controlled chemical and physical contact between partners. Thirty-two gene families were found only in the genomes of symbiotic strains, including some never before associated with cyanobacterial symbiosis. We identified conserved orthologs that were differentially expressed in symbiotic strains, including protein families involved in chemotaxis and motility, NO regulation, sulfate/phosphate transport, and glycosyl-modifying and oxidative stress-mediating exoenzymes. The physical moss-cyanobacteria epiphytic symbiosis is distinct from other cyanobacteria-plant symbioses, with Nostoc retaining motility, and lacking modulation of N₂-fixation, photosynthesis, GS-GOGAT cycle and heterocyst formation. The results expand our knowledge base of plant-cyanobacterial symbioses, provide a model of information and material exchange in this ecologically significant symbiosis, and suggest new currencies, namely nitric oxide and aliphatic sulfonates, may be involved in establishing and maintaining the cyanobacteria-feathermoss symbiosis.