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.

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.

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.

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.

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.

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.

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.

Inferring transcript phylogenies.

Alternative splicing, an unknown mechanism 20 years ago, is now recognized as a major mechanism for proteome and transcriptome diversity, particularly in mammals­some researchers conjecture that up to 90% of human genes are alternatively spliced. Despite much research on exon and intron evolution, little is known about the evolution of transcripts. In this paper, we present a model of transcript evolution and an associated algorithm to reconstruct transcript phylogenies. The evolution of the gene structure­exons and introns­is used as basis for the reconstruction of transcript phylogenies. We apply our model and reconstruction algorithm on two well-studied genes, MAG and PAX6, obtaining results consistent with current knowledge and thereby providing evidence that a phylogenetic analysis of transcripts is feasible and likely to be informative.

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.

FluReF, an automated flu virus reassortment finder based on phylogenetic trees.

BACKGROUND: Reassortments are events in the evolution of the genome of influenza (flu), whereby segments of the genome are exchanged between different strains. As reassortments have been implicated in major human pandemics of the last century, their identification has become a health priority. While such identification can be done "by hand" on a small dataset, researchers and health authorities are building up enormous databases of genomic sequences for every flu strain, so that it is imperative to develop automated identification methods. However, current methods are limited to pairwise segment comparisons. RESULTS: We present FluReF, a fully automated flu virus reassortment finder. FluReF is inspired by the visual approach to reassortment identification and uses the reconstructed phylogenetic trees of the individual segments and of the full genome. We also present a simple flu evolution simulator, based on the current, source-sink, hypothesis for flu cycles. On synthetic datasets produced by our simulator, FluReF, tuned for a 0% false positive rate, yielded false negative rates of less than 10%. FluReF corroborated two new reassortments identified by visual analysis of 75 Human H3N2 New York flu strains from 2005-2008 and gave partial verification of reassortments found using another bioinformatics method. METHODS: FluReF finds reassortments by a bottom-up search of the full-genome and segment-based phylogenetic trees for candidate clades--groups of one or more sampled viruses that are separated from the other variants from the same season. Candidate clades in each tree are tested to guarantee confidence values, using the lengths of key edges as well as other tree parameters; clades with reassortments must have validated incongruencies among segment trees. CONCLUSIONS: FluReF demonstrates robustness of prediction for geographically and temporally expanded datasets, and is not limited to finding reassortments with previously collected sequences. The complete source code is available from http://lcbb.epfl.ch/software.html.

Estimating true evolutionary distances under rearrangements, duplications, and losses.

BACKGROUND: The rapidly increasing availability of whole-genome sequences has enabled the study of whole-genome evolution. Evolutionary mechanisms based on genome rearrangements have attracted much attention and given rise to many models; somewhat independently, the mechanisms of gene duplication and loss have seen much work. However, the two are not independent and thus require a unified treatment, which remains missing to date. Moreover, existing rearrangement models do not fit the dichotomy between most prokaryotic genomes (one circular chromosome) and most eukaryotic genomes (multiple linear chromosomes). RESULTS: To handle rearrangements, gene duplications and losses, we propose a new evolutionary model and the corresponding method for estimating true evolutionary distance. Our model, inspired from the DCJ model, is simple and the first to respect the prokaryotic/eukaryotic structural dichotomy. Experimental results on a wide variety of genome structures demonstrate the very high accuracy and robustness of our distance estimator. CONCLUSION: We give the first robust, statistically based, estimate of genomic pairwise distances based on rearrangements, duplications and losses, under a model that respects the structural dichotomy between prokaryotic and eukaryotic genomes. Accurate and robust estimates in true evolutionary distances should translate into much better phylogenetic reconstructions as well as more accurate genomic alignments, while our new model of genome rearrangements provides another refinement in simplicity and verisimilitude.

Heuristics for the inversion median problem.

BACKGROUND: The study of genome rearrangements has become a mainstay of phylogenetics and comparative genomics. Fundamental in such a study is the median problem: given three genomes find a fourth that minimizes the sum of the evolutionary distances between itself and the given three. Many exact algorithms and heuristics have been developed for the inversion median problem, of which the best known is MGR. RESULTS: We present a unifying framework for median heuristics, which enables us to clarify existing strategies and to place them in a partial ordering. Analysis of this framework leads to a new insight: the best strategies continue to refer to the input data rather than reducing the problem to smaller instances. Using this insight, we develop a new heuristic for inversion medians that uses input data to the end of its computation and leverages our previous work with DCJ medians. Finally, we present the results of extensive experimentation showing that our new heuristic outperforms all others in accuracy and, especially, in running time: the heuristic typically returns solutions within 1% of optimal and runs in seconds to minutes even on genomes with 25'000 genes--in contrast, MGR can take days on instances of 200 genes and cannot be used beyond 1'000 genes. CONCLUSION: Finding good rearrangement medians, in particular inversion medians, had long been regarded as the computational bottleneck in whole-genome studies. Our new heuristic for inversion medians, ASM, which dominates all others in our framework, puts that issue to rest by providing near-optimal solutions within seconds to minutes on even the largest genomes.

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.

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.

Inversion-based genomic signatures.

BACKGROUND: Reconstructing complete ancestral genomes (at least in terms of their gene inventory and arrangement) is attracting much interest due to the rapidly increasing availability of whole genome sequences. While modest successes have been reported for mammalian and even vertebrate genomes, more divergent groups continue to pose a stiff challenge, mostly because current models of genomic evolution support too many choices. RESULTS: We describe a novel type of genomic signature based on rearrangements that characterizes evolutionary changes that must be common to all minimal rearrangement scenarios; by focusing on global patterns of rearrangements, such signatures bypass individual variations and sharply restrict the search space. We present the results of extensive simulation studies demonstrating that these signatures can be used to reconstruct accurate ancestral genomes and phylogenies even for widely divergent collections. CONCLUSION: Focusing on genome triples rather than genomes pairs unleashes the full power of evolutionary analysis. Our genomic signature captures shared evolutionary events and thus can form the basis of a robust analysis and reconstruction of evolutionary history.

Maximum independent sets of commuting and noninterfering inversions.

BACKGROUND: Given three signed permutations, an inversion median is a fourth permutation that minimizes the sum of the pairwise inversion distances between it and the three others. This problem is NP-hard as well as hard to approximate. Yet median-based approaches to phylogenetic reconstruction have been shown to be among the most accurate, especially in the presence of long branches. Most existing approaches have used heuristics that attempt to find a longest sequence of inversions from one of the three permutations that, at each step in the sequence, moves closer to the other two permutations; yet very little is known about the quality of solutions returned by such approaches. RESULTS: Recently, Arndt and Tang took a step towards finding longer such sequences by using sets of commuting inversions. In this paper, we formalize the problem of finding such sequences of inversions with what we call signatures and provide algorithms to find maximum cardinality sets of commuting and noninterfering inversions. CONCLUSION: Our results offer a framework in which to study the inversion median problem, faster algorithms to obtain good medians, and an approach to study characteristic events along an evolutionary path.

Estimating true evolutionary distances under the DCJ model.

MOTIVATION: Modern techniques can yield the ordering and strandedness of genes on each chromosome of a genome; such data already exists for hundreds of organisms. The evolutionary mechanisms through which the set of the genes of an organism is altered and reordered are of great interest to systematists, evolutionary biologists, comparative genomicists and biomedical researchers. Perhaps the most basic concept in this area is that of evolutionary distance between two genomes: under a given model of genomic evolution, how many events most likely took place to account for the difference between the two genomes? RESULTS: We present a method to estimate the true evolutionary distance between two genomes under the 'double-cut-and-join' (DCJ) model of genome rearrangement, a model under which a single multichromosomal operation accounts for all genomic rearrangement events: inversion, transposition, translocation, block interchange and chromosomal fusion and fission. Our method relies on a simple structural characterization of a genome pair and is both analytically and computationally tractable. We provide analytical results to describe the asymptotic behavior of genomes under the DCJ model, as well as experimental results on a wide variety of genome structures to exemplify the very high accuracy (and low variance) of our estimator. Our results provide a tool for accurate phylogenetic reconstruction from multichromosomal gene rearrangement data as well as a theoretical basis for refinements of the DCJ model to account for biological constraints. AVAILABILITY: All of our software is available in source form under GPL at http://lcbb.epfl.ch.

Gene rearrangement analysis and ancestral order inference from chloroplast genomes with inverted repeat.

BACKGROUND: Genome evolution is shaped not only by nucleotide substitutions, but also by structural changes including gene and genome duplications, insertions, deletions and gene order rearrangements. The most popular methods for reconstructing phylogeny from genome rearrangements include GRAPPA and MGR. However these methods are limited to cases where equal gene content or few deletions can be assumed. Since conserved duplicated regions are present in many chloroplast genomes, the inference of inverted repeats is needed in chloroplast phylogeny analysis and ancestral genome reconstruction. RESULTS: We extend GRAPPA and develop a new method GRAPPA-IR to handle chloroplast genomes. A test of GRAPPA-IR using divergent chloroplast genomes from land plants and green algae recovers the phylogeny congruent with prior studies, while analysis that do not consider IR structure fail to obtain the accepted topology. Our extensive simulation study also confirms that GRAPPA has better accuracy then the existing methods. CONCLUSIONS: Tests on a biological and simulated dataset show GRAPPA-IR can accurately recover the genome phylogeny as well as ancestral gene orders. Close analysis of the ancestral genome structure suggests that genome rearrangement in chloroplasts is probably limited by inverted repeats with a conserved core region. In addition, the boundaries of inverted repeats are hot spots for gene duplications or deletions. The new GRAPPA-IR is available from http://phylo.cse.sc.edu.