pH-dependent CLE peptide perception permits phloem differentiation in Arabidopsis roots.

The plant vasculature delivers phloem sap to the growth apices of sink organs, the meristems, via the interconnected sieve elements of the protophloem.1,2,3 In the A. thaliana root meristem, the stem cells form two files of protophloem sieve elements (PPSEs), whose timely differentiation requires a set of positive genetic regulators. In corresponding loss-of-function mutants, signaling of secreted CLAVATA3/EMBRYO SURROUNDING REGION 45 (CLE45) peptide through the BARELY ANY MERISTEM 3 (BAM3) receptor is hyperactive and interferes with PPSE differentiation. This can be mimicked by an external CLE45 application to wild type. Because developing PPSEs express CLE45-BAM3 pathway components from early on until terminal differentiation, it remains unclear how they escape the autocrine inhibitory CLE45 signal. Here, we report that the wild type becomes insensitive to CLE45 treatment on neutral to alkaline pH media, as well as upon simultaneous treatment with a specific proton pump inhibitor at a standard pH of 5.7. We find that these observations can be explained by neither pH-dependent CLE45 uptake nor pH-dependent CLE45 charge. Moreover, pH-dependent perception specifically requires the CLE45 R4 residue and is not observed for the redundant PPSE-specific CLE25 and CLE26 peptides. Finally, pH-dependent CLE45 response in developing PPSEs as opposed to pH-independent response in neighboring cell files indicates that late-developing PPSEs can no longer sense CLE45. This is consistent with an apoplastic acidic to alkaline pH gradient we observed along developing PPSE cell files. In summary, we conclude that developing PPSEs self-organize their transition to differentiation by desensitizing themselves against autocrine CLE45 signaling through an apoplastic pH increase.

The Transcriptional Regulator Prdm1 Is Essential for the Early Development of the Sensory Whisker Follicle and Is Linked to the Beta-Catenin First Dermal Signal.

Prdm1 mutant mice are one of the rare mutant strains that do not develop whisker hair follicles while still displaying a pelage. Here, we show that Prdm1 is expressed at the earliest stage of whisker development in clusters of mesenchymal cells before placode formation. Its conditional knockout in the murine soma leads to the loss of expression of Bmp2, Shh, Bmp4, Krt17, Edar, and Gli1, though leaving the ß-catenin-driven first dermal signal intact. Furthermore, we show that Prdm1 expressing cells not only act as a signaling center but also as a multipotent progenitor population contributing to the several lineages of the adult whisker. We confirm by genetic ablation experiments that the absence of macro vibrissae reverberates on the organization of nerve wiring in the mystacial pads and leads to the reorganization of the barrel cortex. We demonstrate that Lef1 acts upstream of Prdm1 and identify a primate-specific deletion of a Lef1 enhancer named Leaf. This loss may have been significant in the evolutionary process, leading to the progressive defunctionalization and disappearance of vibrissae in primates.

Mapping and engineering of auxin-induced plasma membrane dissociation in BRX family proteins.

Angiosperms have evolved the phloem for the long-distance transport of metabolites. The complex process of phloem development involves genes that only occur in vascular plant lineages. For example, in Arabidopsis thaliana, the BREVIS RADIX (BRX) gene is required for continuous root protophloem differentiation, together with PROTEIN KINASE ASSOCIATED WITH BRX (PAX). BRX and its BRX-LIKE (BRXL) homologs are composed of four highly conserved domains including the signature tandem BRX domains that are separated by variable spacers. Nevertheless, BRX family proteins have functionally diverged. For instance, BRXL2 can only partially replace BRX in the root protophloem. This divergence is reflected in physiologically relevant differences in protein behavior, such as auxin-induced plasma membrane dissociation of BRX, which is not observed for BRXL2. Here we dissected the differential functions of BRX family proteins using a set of amino acid substitutions and domain swaps. Our data suggest that the plasma membrane-associated tandem BRX domains are both necessary and sufficient to convey the biological outputs of BRX function and therefore constitute an important regulatory entity. Moreover, PAX target phosphosites in the linker between the two BRX domains mediate the auxin-induced plasma membrane dissociation. Engineering these sites into BRXL2 renders this modified protein auxin-responsive and thereby increases its biological activity in the root protophloem context.

Local auxin competition explains fragmented differentiation patterns.

Trajectories of cellular ontogeny are tightly controlled and often involve feedback-regulated molecular antagonism. For example, sieve element differentiation along developing protophloem cell files of Arabidopsis roots requires two antagonistic regulators of auxin efflux. Paradoxically, loss-of-function in either regulator triggers similar, seemingly stochastic differentiation failures of individual sieve element precursors. Here we show that these patterning defects are distinct and non-random. They can be explained by auxin-dependent bistability that emerges from competition for auxin between neighboring cells. This bistability depends on the presence of an auxin influx facilitator, and can be triggered by either flux enhancement or repression. Our results uncover a hitherto overlooked aspect of auxin uptake, and highlight the contributions of local auxin influx, efflux and biosynthesis to protophloem formation. Moreover, the combined experimental-modeling approach suggests that without auxin efflux homeostasis, auxin influx interferes with coordinated differentiation.

Local and Systemic Effects of Brassinosteroid Perception in Developing Phloem.

The plant vasculature is an essential adaptation to terrestrial growth. Its phloem component permits efficient transfer of photosynthates between source and sink organs but also transports signals that systemically coordinate physiology and development. Here, we provide evidence that developing phloem orchestrates cellular behavior of adjacent tissues in the growth apices of plants, the meristems. Arabidopsis thaliana plants that lack the three receptor kinases BRASSINOSTEROID INSENSITIVE 1 (BRI1), BRI1-LIKE 1 (BRL1), and BRL3 ("bri3" mutants) can no longer sense brassinosteroid phytohormones and display severe dwarfism as well as patterning and differentiation defects, including disturbed phloem development. We found that, despite the ubiquitous expression of brassinosteroid receptors in growing plant tissues, exclusive expression of the BRI1 receptor in developing phloem is sufficient to systemically correct cellular growth and patterning defects that underlie the bri3 phenotype. Although this effect is brassinosteroid-dependent, it cannot be reproduced with dominant versions of known downstream effectors of BRI1 signaling and therefore possibly involves a non-canonical signaling output. Interestingly, the rescue of bri3 by phloem-specific BRI1 expression is associated with antagonism toward phloem-specific CLAVATA3/EMBRYO SURROUNDING REGION-RELATED 45 (CLE45) peptide signaling in roots. Hyperactive CLE45 signaling causes phloem sieve element differentiation defects, and consistently, knockout of CLE45 perception in bri3 background restores proper phloem development. However, bri3 dwarfism is retained in such lines. Our results thus reveal local and systemic effects of brassinosteroid perception in the phloem: whereas it locally antagonizes CLE45 signaling to permit phloem differentiation, it systemically instructs plant organ formation via a phloem-derived, non-cell-autonomous signal.

Sequence-Based Synteny Analysis of Multiple Large Genomes.

Current methods for synteny analysis provide only limited support to study large genomes at the sequence level. In this chapter, we describe a pipeline based on existing tools that, applied in a suitable fashion, enables synteny analysis of large genomic datasets. We give a hands-on description of each step of the pipeline using four avian genomes for data. We also provide integration scripts that simplify the conversion and setup of data between the different tools in the pipeline.

New Genome Similarity Measures based on Conserved Gene Adjacencies.

Many important questions in molecular biology, evolution, and biomedicine can be addressed by comparative genomic approaches. One of the basic tasks when comparing genomes is the definition of measures of similarity (or dissimilarity) between two genomes, for example, to elucidate the phylogenetic relationships between species. The power of different genome comparison methods varies with the underlying formal model of a genome. The simplest models impose the strong restriction that each genome under study must contain the same genes, each in exactly one copy. More realistic models allow several copies of a gene in a genome. One speaks of gene families, and comparative genomic methods that allow this kind of input are called gene family-based. The most powerful-but also most complex-models avoid this preprocessing of the input data and instead integrate the family assignment within the comparative analysis. Such methods are called gene family-free. In this article, we study an intermediate approach between family-based and family-free genomic similarity measures. Introducing this simpler model, called gene connections, we focus on the combinatorial aspects of gene family-free genome comparison. While in most cases, the computational costs to the general family-free case are the same, we also find an instance where the gene connections model has lower complexity. Within the gene connections model, we define three variants of genomic similarity measures that have different expression powers. We give polynomial-time algorithms for two of them, while we show NP-hardness for the third, most powerful one. We also generalize the measures and algorithms to make them more robust against recent local disruptions in gene order. Our theoretical findings are supported by experimental results, proving the applicability and performance of our newly defined similarity measures.

NEMo: An Evolutionary Model With Modularity for PPI Networks.

Modeling the evolution of biological networks is a major challenge. Biological networks are usually represented as graphs; evolutionary events not only include addition and removal of vertices and edges but also duplication of vertices and their associated edges. Since duplication is viewed as a primary driver of genomic evolution, recent work has focused on duplication-based models. Missing from these models is any embodiment of modularity, a widely accepted attribute of biological networks. Some models spontaneously generate modular structures, but none is known to maintain and evolve them. We describe network evolution with modularity (NEMo), a new model that embodies modularity. NEMo allows modules to appear and disappear and to fission and to merge, all driven by the underlying edge-level events using a duplication-based process. We also introduce measures to compare biological networks in terms of their modular structure; we present comparisons between NEMo and existing duplication-based models and run our measuring tools on both generated and published networks.

On Computing Breakpoint Distances for Genomes with Duplicate Genes.

A fundamental problem in comparative genomics is to compute the distance between two genomes in terms of its higher level organization (given by genes or syntenic blocks). For two genomes without duplicate genes, we can easily define (and almost always efficiently compute) a variety of distance measures, but the problem is NP-hard under most models when genomes contain duplicate genes. To tackle duplicate genes, three formulations (exemplar, maximum matching, and any matching) have been proposed, all of which aim to build a matching between homologous genes so as to minimize some distance measure. Of the many distance measures, the breakpoint distance (the number of nonconserved adjacencies) was the first one to be studied and remains of significant interest because of its simplicity and model-free property. The three breakpoint distance problems corresponding to the three formulations have been widely studied. Although we provided last year a solution for the exemplar problem that runs very fast on full genomes, computing optimal solutions for the other two problems has remained challenging. In this article, we describe very fast, exact algorithms for these two problems. Our algorithms rely on a compact integer-linear program that we further simplify by developing an algorithm to remove variables, based on new results on the structure of adjacencies and matchings. Through extensive experiments using both simulations and biological data sets, we show that our algorithms run very fast (in seconds) on mammalian genomes and scale well beyond. We also apply these algorithms (as well as the classic orthology tool MSOAR) to create orthology assignment, then compare their quality in terms of both accuracy and coverage. We find that our algorithm for the "any matching" formulation significantly outperforms other methods in terms of accuracy while achieving nearly maximum coverage.

A Fast and Exact Algorithm for the Exemplar Breakpoint Distance.

A fundamental problem in comparative genomics is to compute the distance between two genomes. For two genomes without duplicate genes, we can easily compute a variety of distance measures in linear time, but the problem is NP-hard under most models when genomes contain duplicate genes. Sankoff proposed the use of exemplars to tackle the problem of duplicate genes and gene families: each gene family is represented by a single gene (the exemplar for that family), chosen so as to optimize some metric. Unfortunately, choosing exemplars is itself an NP-hard problem. In this article, we propose a very fast and exact algorithm to compute the exemplar breakpoint distance, based on new insights in the underlying structure of genome rearrangements and exemplars. We evaluate the performance of our algorithm on simulation data and compare its performance to the best effort to date (a divide-and-conquer approach), showing that our algorithm runs much faster and scales much better. We also devise a new algorithm for the intermediate breakpoint distance problem, which can then be applied to assign orthologs. We compare our algorithm with the state-of-the-art method MSOAR by assigning orthologs among five well annotated mammalian genomes, showing that our algorithm runs much faster and is slightly more accurate than MSOAR.

A maximum-likelihood approach for building cell-type trees by lifting.

BACKGROUND: In cell differentiation, a less specialized cell differentiates into a more specialized one, even though all cells in one organism have (almost) the same genome. Epigenetic factors such as histone modifications are known to play a significant role in cell differentiation. We previously introduce cell-type trees to represent the differentiation of cells into more specialized types, a representation that partakes of both ontogeny and phylogeny. RESULTS: We propose a maximum-likelihood (ML) approach to build cell-type trees and show that this ML approach outperforms our earlier distance-based and parsimony-based approaches. We then study the reconstruction of ancestral cell types; since both ancestral and derived cell types can coexist in adult organisms, we propose a lifting algorithm to infer internal nodes. We present results on our lifting algorithm obtained both through simulations and on real datasets. CONCLUSIONS: We show that our ML-based approach outperforms previously proposed techniques such as distance-based and parsimony-based methods. We show our lifting-based approach works well on both simulated and real data.

Comparing genomes with rearrangements and segmental duplications.

MOTIVATION: Large-scale evolutionary events such as genomic rearrange.ments and segmental duplications form an important part of the evolution of genomes and are widely studied from both biological and computational perspectives. A basic computational problem is to infer these events in the evolutionary history for given modern genomes, a task for which many algorithms have been proposed under various constraints. Algorithms that can handle both rearrangements and content-modifying events such as duplications and losses remain few and limited in their applicability. RESULTS: We study the comparison of two genomes under a model including general rearrangements (through double-cut-and-join) and segmental duplications. We formulate the comparison as an optimization problem and describe an exact algorithm to solve it by using an integer linear program. We also devise a sufficient condition and an efficient algorithm to identify optimal substructures, which can simplify the problem while preserving optimality. Using the optimal substructures with the integer linear program (ILP) formulation yields a practical and exact algorithm to solve the problem. We then apply our algorithm to assign in-paralogs and orthologs (a necessary step in handling duplications) and compare its performance with that of the state-of-the-art method MSOAR, using both simulations and real data. On simulated datasets, our method outperforms MSOAR by a significant margin, and on five well-annotated species, MSOAR achieves high accuracy, yet our method performs slightly better on each of the 10 pairwise comparisons. AVAILABILITY AND IMPLEMENTATION: http://lcbb.epfl.ch/softwares/coser.

An Exact Algorithm to Compute the Double-Cut-and-Join Distance for Genomes with Duplicate Genes.

Computing the edit distance between two genomes is a basic problem in the study of genome evolution. The double-cut-and-join (DCJ) model has formed the basis for most algorithmic research on rearrangements over the last few years. The edit distance under the DCJ model can be computed in linear time for genomes without duplicate genes, while the problem becomes NP-hard in the presence of duplicate genes. In this article, we propose an integer linear programming (ILP) formulation to compute the DCJ distance between two genomes with duplicate genes. We also provide an efficient preprocessing approach to simplify the ILP formulation while preserving optimality. Comparison on simulated genomes demonstrates that our method outperforms MSOAR in computing the edit distance, especially when the genomes contain long duplicated segments. We also apply our method to assign orthologous gene pairs among human, mouse, and rat genomes, where once again our method outperforms MSOAR.

Study of cell differentiation by phylogenetic analysis using histone modification data.

BACKGROUND: In cell differentiation, a cell of a less specialized type becomes one of a more specialized type, even though all cells have the same genome. Transcription factors and epigenetic marks like histone modifications can play a significant role in the differentiation process. RESULTS: In this paper, we present a simple analysis of cell types and differentiation paths using phylogenetic inference based on ChIP-Seq histone modification data. We precisely defined the notion of cell-type trees and provided a procedure of building such trees. We propose new data representation techniques and distance measures for ChIP-Seq data and use these together with standard phylogenetic inference methods to build biologically meaningful cell-type trees that indicate how diverse types of cells are related. We demonstrate our approach on various kinds of histone modifications for various cell types, also using the datasets to explore various issues surrounding replicate data, variability between cells of the same type, and robustness. We use the results to get some interesting biological findings like important patterns of histone modification changes during cell differentiation process. CONCLUSIONS: We introduced and studied the novel problem of inferring cell type trees from histone modification data. The promising results we obtain point the way to a new approach to the study of cell differentiation. We also discuss how cell-type trees can be used to study the evolution of cell types.

Evaluating synteny for improved comparative studies.

MOTIVATION: Comparative genomics aims to understand the structure and function of genomes by translating knowledge gained about some genomes to the object of study. Early approaches used pairwise comparisons, but today researchers are attempting to leverage the larger potential of multi-way comparisons. Comparative genomics relies on the structuring of genomes into syntenic blocks: blocks of sequence that exhibit conserved features across the genomes. Syntenic blocs are required for complex computations to scale to the billions of nucleotides present in many genomes; they enable comparisons across broad ranges of genomes because they filter out much of the individual variability; they highlight candidate regions for in-depth studies; and they facilitate whole-genome comparisons through visualization tools. However, the concept of syntenic block remains loosely defined. Tools for the identification of syntenic blocks yield quite different results, thereby preventing a systematic assessment of the next steps in an analysis. Current tools do not include measurable quality objectives and thus cannot be benchmarked against themselves. Comparisons among tools have also been neglected-what few results are given use superficial measures unrelated to quality or consistency. RESULTS: We present a theoretical model as well as an experimental basis for comparing syntenic blocks and thus also for improving or designing tools for the identification of syntenic blocks. We illustrate the application of the model and the measures by applying them to syntenic blocks produced by three different contemporary tools (DRIMM-Synteny, i-ADHoRe and Cyntenator) on a dataset of eight yeast genomes. Our findings highlight the need for a well founded, systematic approach to the decomposition of genomes into syntenic blocks. Our experiments demonstrate widely divergent results among these tools, throwing into question the robustness of the basic approach in comparative genomics. We have taken the first step towards a formal approach to the construction of syntenic blocks by developing a simple quality criterion based on sound evolutionary principles.

Probabilistic partitioning methods to find significant patterns in ChIP-Seq data.

MOTIVATION: We have witnessed an enormous increase in ChIP-Seq data for histone modifications in the past few years. Discovering significant patterns in these data is an important problem for understanding biological mechanisms. RESULTS: We propose probabilistic partitioning methods to discover significant patterns in ChIP-Seq data. Our methods take into account signal magnitude, shape, strand orientation and shifts. We compare our methods with some current methods and demonstrate significant improvements, especially with sparse data. Besides pattern discovery and classification, probabilistic partitioning can serve other purposes in ChIP-Seq data analysis. Specifically, we exemplify its merits in the context of peak finding and partitioning of nucleosome positioning patterns in human promoters. AVAILABILITY AND IMPLEMENTATION: The software and code are available in the supplementary material. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Maximum likelihood phylogenetic reconstruction from high-resolution whole-genome data and a tree of 68 eukaryotes.

The rapid accumulation of whole-genome data has renewed interest in the study of the evolution of genomic architecture, under such events as rearrangements, duplications, losses. Comparative genomics, evolutionary biology, and cancer research all require tools to elucidate the mechanisms, history, and consequences of those evolutionary events, while phylogenetics could use whole-genome data to enhance its picture of the Tree of Life. Current approaches in the area of phylogenetic analysis are limited to very small collections of closely related genomes using low-resolution data (typically a few hundred syntenic blocks); moreover, these approaches typically do not include duplication and loss events. We describe a maximum likelihood (ML) approach for phylogenetic analysis that takes into account genome rearrangements as well as duplications, insertions, and losses. Our approach can handle high-resolution genomes (with 40,000 or more markers) and can use in the same analysis genomes with very different numbers of markers. Because our approach uses a standard ML reconstruction program (RAxML), it scales up to large trees. We present the results of extensive testing on both simulated and real data showing that our approach returns very accurate results very quickly. In particular, we analyze a dataset of 68 high-resolution eukaryotic genomes, with from 3,000 to 42,000 genes, from the eGOB database; the analysis, including bootstrapping, takes just 3 hours on a desktop system and returns a tree in agreement with all well supported branches, while also suggesting resolutions for some disputed placements.

Sorting genomes with rearrangements and segmental duplications through trajectory graphs.

We study the problem of sorting genomes under an evolutionary model that includes genomic rearrangements and segmental duplications. We propose an iterative algorithm to improve any initial evolutionary trajectory between two genomes in terms of parsimony. Our algorithm is based on a new graphical model, the trajectory graph, which models not only the final states of two genomes but also an existing evolutionary trajectory between them. We show that redundant rearrangements in the trajectory correspond to certain cycles in the trajectory graph, and prove that our algorithm converges to an optimal trajectory for any initial trajectory involving only rearrangements.

A transcript perspective on evolution.

Alternative splicing is now recognized as a major mechanism for transcriptome and proteome diversity in higher eukaryotes, yet its evolution is poorly understood. Most studies focus on the evolution of exons and introns at the gene level, while only few consider the evolution of transcripts. In this paper, we present a framework for transcript phylogenies where ancestral transcripts evolve along the gene tree by gains, losses, and mutation. We demonstrate the usefulness of our method on a set of 805 genes and two different topics. First, we improve a method for transcriptome reconstruction from ESTs (ASPic), then we study the evolution of function in transcripts. The use of transcript phylogenies allows us to double the precision of ASPic, whereas results on the functional study reveal that conserved transcripts are more likely to share protein domains than functional sites. These studies validate our framework for the study of evolution in large collections of organisms from the perspective of transcripts; for this purpose, we developed and provide a new tool, TrEvoR.

TIBA: a tool for phylogeny inference from rearrangement data with bootstrap analysis.

TIBA is a tool to reconstruct phylogenetic trees from rearrangement data that consist of ordered lists of synteny blocks (or genes), where each synteny block is shared with all of its homologues in the input genomes. The evolution of these synteny blocks, through rearrangement operations, is modelled by the uniform Double-Cut-and-Join model. Using a true distance estimate under this model and simple distance-based methods, TIBA reconstructs a phylogeny of the input genomes. Unlike any previous tool for inferring phylogenies from rearrangement data, TIBA uses novel methods of robustness estimation to provide support values for the edges in the inferred tree.