The Unconstrained Diameters of the Duplication-Loss Cost and the Loss Cost.

Tree reconciliation costs are a popular choice to account for the discordance between the evolutionary history of a gene family (i.e., a gene tree), and the species tree through which this family has evolved. This discordance is accounted for by the minimum number of postulated evolutionary events necessary for reconciling the two trees. Such events include gene duplication, loss, and deep coalescence, and are used to define different types of tree reconciliation costs. For example, the duplication-loss cost for a gene tree and species tree accounts for the minimum number of gene duplications and losses necessary to reconcile these trees. Fundamental to the understanding of how gene trees and species trees relate to each other are the diameters of tree reconciliation costs. While such diameters have been well-researched, still absent from these studies are the unconstrained diameters for two of the classic tree reconciliation costs, namely the duplication-loss cost and the loss cost. Here, we show the essential mathematical properties of these diameters and provide efficient solutions for computing them. Finally, we analyze the distributions of these diameters using simulated datasets.

Minimizing genomic duplication episodes.

BACKGROUND: The genomic duplication study is fundamental to understand the process of evolution. In evolutionary molecular biology, many approaches focus on discovering the occurrences of gene duplications and multiple gene duplication episodes and their locations in the Tree of Life. To reconstruct such episodes, one can cluster single gene duplications inferred by reconciling a set of gene trees with a species tree. RESULTS: We propose an efficient quadratic time algorithm to solve the problem of genomic duplication clustering, in which input gene trees are rooted, episode locations are restricted to preserve the minimal number of single gene duplications, clustering rules are described by minimum episodes method, and the goal is based on the recently introduced new approach to minimize the maximal number of duplication episodes on a single path, called here the MP score. Based on our theoretical results, we show new algorithmic relationships between the MP score and the minimum episodes (ME) score, defined as the minimal number of duplication episodes. CONCLUSIONS: Our evaluation analysis on three empirical datasets demonstrates, that under the model in which the minimal number of duplications is preserved, the duplication clusterings with minimal MP score support the clusterings with the minimal total number of duplication episodes. AVAILABILITY: The software is available at https://bitbucket.org/pgor17/rmp.

Learning signaling networks from combinatorial perturbations by exploiting siRNA off-target effects.

MOTIVATION: Perturbation experiments constitute the central means to study cellular networks. Several confounding factors complicate computational modeling of signaling networks from this data. First, the technique of RNA interference (RNAi), designed and commonly used to knock-down specific genes, suffers from off-target effects. As a result, each experiment is a combinatorial perturbation of multiple genes. Second, the perturbations propagate along unknown connections in the signaling network. Once the signal is blocked by perturbation, proteins downstream of the targeted proteins also become inactivated. Finally, all perturbed network members, either directly targeted by the experiment, or by propagation in the network, contribute to the observed effect, either in a positive or negative manner. One of the key questions of computational inference of signaling networks from such data are, how many and what combinations of perturbations are required to uniquely and accurately infer the model? RESULTS: Here, we introduce an enhanced version of linear effects models (LEMs), which extends the original by accounting for both negative and positive contributions of the perturbed network proteins to the observed phenotype. We prove that the enhanced LEMs are identified from data measured under perturbations of all single, pairs and triplets of network proteins. For small networks of up to five nodes, only perturbations of single and pairs of proteins are required for identifiability. Extensive simulations demonstrate that enhanced LEMs achieve excellent accuracy of parameter estimation and network structure learning, outperforming the previous version on realistic data. LEMs applied to Bartonella henselae infection RNAi screening data identified known interactions between eight nodes of the infection network, confirming high specificity of our model and suggested one new interaction. AVAILABILITY AND IMPLEMENTATION: https://github.com/EwaSzczurek/LEM. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Contribution of NtZIP1-Like to the Regulation of Zn Homeostasis.

Tobacco has frequently been suggested as a candidate plant species for use in phytoremediation of metal contaminated soil but knowledge on the regulation of its metal-homeostasis is still in the infancy. To identify new tobacco metal transport genes that are involved in Zn homeostasis a bioinformatics study using the tobacco genome information together with expression analysis was performed. Ten new tobacco metal transport genes from the ZIP, NRAMP, MTP, and MRP/ABCC families were identified with expression levels in leaves that were modified by exposure to Zn excess. Following exposure to high Zn there was upregulation of NtZIP11-like, NtNRAMP3, three isoforms of NtMTP2, three MRP/ABCC genes (NtMRP5-like, NtMRP10-like, and NtMRP14 like) and downregulation of NtZIP1-like and NtZIP4. This suggests their involvement in several processes governing the response to Zn-related stress and in the efficiency of Zn accumulation (uptake, sequestration, and redistribution). Further detailed analysis of NtZIP1-like provided evidence that it is localized at the plasma membrane and is involved in Zn but not Fe and Cd transport. NtZIP1-like is expressed in the roots and shoots, and is regulated developmentally and in a tissue-specific manner. It is highly upregulated by Zn deficiency in the leaves and the root basal region but not in the root apical zone (region of maturation and absorption containing root hairs). Thus NtZIP1-like is unlikely to be responsible for Zn uptake by the root apical region but rather in the uptake by root cells within the already mature basal zone. It is downregulated by Zn excess suggesting it is involved in a mechanism to protect the root and leaf cells from accumulating excess Zn.

FastBill: An Improved Tool for Prediction of Cis-Regulatory Modules.

Here, we provide a new software tool, called FastBill, for prediction of evolutionarily conserved cis-regulatory modules. It improves on the previous version of our program, called Billboard, by improving the statistical significance calculation. It is also faster than the original Billboard, allowing for large-scale analyses, including multiple informant species. We illustrate the utility of FastBill by performing a large-scale computational experiment of enhancer prediction in the promoter area of more than 150 Drosophila melanogaster genes that possess annotated experimentally verified enhancers. FastBill is written in Python and is freely available for download as a standalone tool.

Romulus: robust multi-state identification of transcription factor binding sites from DNase-seq data.

MOTIVATION: Computational prediction of transcription factor (TF) binding sites in the genome remains a challenging task. Here, we present Romulus, a novel computational method for identifying individual TF binding sites from genome sequence information and cell-type-specific experimental data, such as DNase-seq. It combines the strengths of previous approaches, and improves robustness by reducing the number of free parameters in the model by an order of magnitude. RESULTS: We show that Romulus significantly outperforms existing methods across three sources of DNase-seq data, by assessing the performance of these tools against ChIP-seq profiles. The difference was particularly significant when applied to binding site prediction for low-information-content motifs. Our method is capable of inferring multiple binding modes for a single TF, which differ in their DNase I cut profile. Finally, using the model learned by Romulus and ChIP-seq data, we introduce Binding in Closed Chromatin (BCC) as a quantitative measure of TF pioneer factor activity. Uniquely, our measure quantifies a defining feature of pioneer factors, namely their ability to bind closed chromatin. AVAILABILITY AND IMPLEMENTATION: Romulus is freely available as an R package at http://github.com/ajank/Romulus CONTACT: ajank@mimuw.edu.pl SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Enhanceosome transcription factors preferentially dimerize with high mobility group proteins.

BACKGROUND: The enhanceosome is an enhancer located upstream of the human interferon ß gene, bound by transcription factor (TF) complex of extremely rigid structure. Within these rigid constraints, even a slight change of distances between transcription factor binding sites (TFBS) results in loss of functionality of the enhanceosome. We hypothesized that smaller subunits of the enhanceosome may entail TF complex formation in other regulatory regions. RESULTS: In order to verify this hypothesis we systematically searched for dimerization preferences of the TFs that have TFBS in the enhanceosome. For this we utilized our recently developed tool, TACO. We performed this computational experiment in a cell-type-specific manner by utilizing cell-type-specific DNase-seq data for 105 human cell types. We also used 20 TRANSFAC motifs comprising not only the usual TFs constituting the enhanceosome but also the architectural proteins of High Mobility Group I(Y) (HMG I). A similar experiment used 42 DNase-seq data sets for mouse cell types. We found 137 statistically significant dimer predictions in the human genome, and 37 predictions in the mouse genome, that matched the positioning on the enhanceosome with ±2 bp tolerance. To characterize these predicted TF dimers, we performed functional analysis (Gene Ontology enrichment) for sets of genes which were in the neighbourhood of predicted dimer instances. A notable feature of these instances is that (1) most of them are located in introns of genes, (2) they are enriched in regulatory states, and (3) those instances that are located near transcription start sites are enriched for inclusion in computationally predicted enhancers. We also investigated similarity of dimer predictions between human and mouse. CONCLUSIONS: It follows from our experiments that, except for homodimer formed by IRF proteins, the rest of the dimers were formed exclusively between one of the transcriptional activators (ATF-2/c-Jun and IRF) and a HMG I protein. NF- κB did not participate in forming dimers with other proteins. Dimers predicted in mouse were fully contained in those predicted in human, with exactly the same spacing and orientation. Intriguingly, in most of the cases the enhanceosome motifs have 1 bp wider spacing than the corresponding dimers predicted genome-wide, which is likely caused by the overall 3D structure constraints of the enhanceosome-bound complex.

A Specialized Histone H1 Variant Is Required for Adaptive Responses to Complex Abiotic Stress and Related DNA Methylation in Arabidopsis.

Linker (H1) histones play critical roles in chromatin compaction in higher eukaryotes. They are also the most variable of the histones, with numerous nonallelic variants cooccurring in the same cell. Plants contain a distinct subclass of minor H1 variants that are induced by drought and abscisic acid and have been implicated in mediating adaptive responses to stress. However, how these variants facilitate adaptation remains poorly understood. Here, we show that the single Arabidopsis (Arabidopsis thaliana) stress-inducible variant H1.3 occurs in plants in two separate and most likely autonomous pools: a constitutive guard cell-specific pool and a facultative environmentally controlled pool localized in other tissues. Physiological and transcriptomic analyses of h1.3 null mutants demonstrate that H1.3 is required for both proper stomatal functioning under normal growth conditions and adaptive developmental responses to combined light and water deficiency. Using fluorescence recovery after photobleaching analysis, we show that H1.3 has superfast chromatin dynamics, and in contrast to the main Arabidopsis H1 variants H1.1 and H1.2, it has no stable bound fraction. The results of global occupancy studies demonstrate that, while H1.3 has the same overall binding properties as the main H1 variants, including predominant heterochromatin localization, it differs from them in its preferences for chromatin regions with epigenetic signatures of active and repressed transcription. We also show that H1.3 is required for a substantial part of DNA methylation associated with environmental stress, suggesting that the likely mechanism underlying H1.3 function may be the facilitation of chromatin accessibility by direct competition with the main H1 variants.

eCAMBer: efficient support for large-scale comparative analysis of multiple bacterial strains.

BACKGROUND: Inconsistencies are often observed in the genome annotations of bacterial strains. Moreover, these inconsistencies are often not reflected by sequence discrepancies, but are caused by wrongly annotated gene starts as well as mis-identified gene presence. Thus, tools are needed for improving annotation consistency and accuracy among sets of bacterial strain genomes. RESULTS: We have developed eCAMBer, a tool for efficiently supporting comparative analysis of multiple bacterial strains within the same species. eCAMBer is a highly optimized revision of our earlier tool, CAMBer, scaling it up for significantly larger datasets comprising hundreds of bacterial strains. eCAMBer works in two phases. First, it transfers gene annotations among all considered bacterial strains. In this phase, it also identifies homologous gene families and annotation inconsistencies. Second, eCAMBer, tries to improve the quality of annotations by resolving the gene start inconsistencies and filtering out gene families arising from annotation errors propagated in the previous phase. CONCLUSIONS: [corrected] eCAMBer efficiently identifies and resolves annotation inconsistencies among closely related bacterial genomes. It outperforms other competing tools both in terms of running time and accuracy of produced annotations. Software, user manual, and case study results are available at the project website: http://bioputer.mimuw.edu.pl/ecamber.

TACO: a general-purpose tool for predicting cell-type-specific transcription factor dimers.

BACKGROUND: Cooperative binding of transcription factor (TF) dimers to DNA is increasingly recognized as a major contributor to binding specificity. However, it is likely that the set of known TF dimers is highly incomplete, given that they were discovered using ad hoc approaches, or through computational analyses of limited datasets. RESULTS: Here, we present TACO (Transcription factor Association from Complex Overrepresentation), a general-purpose standalone software tool that takes as input any genome-wide set of regulatory elements and predicts cell-type-specific TF dimers based on enrichment of motif complexes. TACO is the first tool that can accommodate motif complexes composed of overlapping motifs, a characteristic feature of many known TF dimers. Our method comprehensively outperforms existing tools when benchmarked on a reference set of 29 known dimers. We demonstrate the utility and consistency of TACO by applying it to 152 DNase-seq datasets and 94 ChIP-seq datasets. CONCLUSIONS: Based on these results, we uncover a general principle governing the structure of TF-TF-DNA ternary complexes, namely that the flexibility of the complex is correlated with, and most likely a consequence of, inter-motif spacing.

GWAMAR: genome-wide assessment of mutations associated with drug resistance in bacteria.

BACKGROUND: Development of drug resistance in bacteria causes antibiotic therapies to be less effective and more costly. Moreover, our understanding of the process remains incomplete. One promising approach to improve our understanding of how resistance is being acquired is to use whole-genome comparative approaches for detection of drug resistance-associated mutations. RESULTS: We present GWAMAR, a tool we have developed for detecting of drug resistance-associated mutations in bacteria through comparative analysis of whole-genome sequences. The pipeline of GWAMAR comprises several steps. First, for a set of closely related bacterial genomes, it employs eCAMBer to identify homologous gene families. Second, based on multiple alignments of the gene families, it identifies mutations among the strains of interest. Third, it calculates several statistics to identify which mutations are the most associated with drug resistance. CONCLUSIONS: Based on our analysis of two large datasets retrieved from publicly available data for M. tuberculosis, we identified a set of novel putative drug resistance-associated mutations. As a part of this work, we present also an application of our tool to detect putative compensatory mutations.

Unrooted tree reconciliation: a unified approach.

Tree comparison functions are widely used in phylogenetics for comparing evolutionary trees. Unrooted trees can be compared with rooted trees by identifying all rootings of the unrooted tree that minimize some provided comparison function between two rooted trees. The plateau property is satisfied by the provided function, if all optimal rootings form a subtree, or plateau, in the unrooted tree, from which the rootings along every path toward a leaf have monotonically increasing costs. This property is sufficient for the linear-time identification of all optimal rootings and rooting costs. However, the plateau property has only been proven for a few rooted comparison functions, requiring individual proofs for each function without benefitting from inherent structural features of such functions. Here, we introduce the consistency condition that is sufficient for a general function to satisfy the plateau property. For consistent functions, we introduce general linear-time solutions that identify optimal rootings and all rooting costs. Further, we identify novel relationships between consistent functions in terms of plateaus, especially the plateau of the well-studied duplication-loss function is part of a plateau of every other consistent function. We introduce a novel approach for identifying consistent cost functions by defining a formal language of Boolean costs. Formulas in this language can be interpreted as cost functions. Finally, we demonstrate the performance of our general linear-time solutions in practice using empirical and simulation studies.

A probabilistic model of neutral and selective dynamics of protein network evolution.

Comparative approaches in genomics have long relied on rigorous mathematical models of sequence evolution. Such models provide the basis for formulating and solving well-defined computational problems, in turn yielding key insights into the evolutionary processes acting on the genome. Analogous model-based approaches for analyzing biological networks are still under development. Here we describe a model-based approach for estimating the probability of network rewiring events during evolution. Our method builds on the standard duplication-and-divergence model and incorporates phylogenetic analysis to guide the comparison of protein networks across species. We apply our algorithm to study the evolution of functional modules and unconstrained network regions in seven available eukaryotic interactomes. Based on this analysis we identify a map of co-functioning protein families whose members participate in strongly conserved interactions and form major complexes and pathways in the eukaryotic cell. The proposed approach provides principled means for inferring the probability of network rewiring events, enabling insights into the conservation and divergence of protein interactions and the formation of functional modules in protein networks.

Comprehensive prediction in 78 human cell lines reveals rigidity and compactness of transcription factor dimers.

The binding of transcription factors (TFs) to their specific motifs in genomic regulatory regions is commonly studied in isolation. However, in order to elucidate the mechanisms of transcriptional regulation, it is essential to determine which TFs bind DNA cooperatively as dimers and to infer the precise nature of these interactions. So far, only a small number of such dimeric complexes are known. Here, we present an algorithm for predicting cell-type-specific TF-TF dimerization on DNA on a large scale, using DNase I hypersensitivity data from 78 human cell lines. We represented the universe of possible TF complexes by their corresponding motif complexes, and analyzed their occurrence at cell-type-specific DNase I hypersensitive sites. Based on ∼1.4 billion tests for motif complex enrichment, we predicted 603 highly significant cell-type-specific TF dimers, the vast majority of which are novel. Our predictions included 76% (19/25) of the known dimeric complexes and showed significant overlap with an experimental database of protein-protein interactions. They were also independently supported by evolutionary conservation, as well as quantitative variation in DNase I digestion patterns. Notably, the known and predicted TF dimers were almost always highly compact and rigidly spaced, suggesting that TFs dimerize in close proximity to their partners, which results in strict constraints on the structure of the DNA-bound complex. Overall, our results indicate that chromatin openness profiles are highly predictive of cell-type-specific TF-TF interactions. Moreover, cooperative TF dimerization seems to be a widespread phenomenon, with multiple TF complexes predicted in most cell types.

An approach to identifying drug resistance associated mutations in bacterial strains.

BACKGROUND: Drug resistance in bacterial pathogens is an increasing problem, which stimulates research. However, our understanding of drug resistance mechanisms remains incomplete. Fortunately, the fast-growing number of fully sequenced bacterial strains now enables us to develop new methods to identify mutations associated with drug resistance. RESULTS: We present a new comparative approach to identify genes and mutations that are likely to be associated with drug resistance mechanisms. In order to test the approach, we collected genotype and phenotype data of 100 fully sequenced strains of S. aureus and 10 commonly used drugs. Then, applying the method, we re-discovered the most common genetic determinants of drug resistance and identified some novel putative associations. CONCLUSIONS: Firstly, the collected data may help other researchers to develop and verify similar techniques. Secondly, the proposed method is successful in identifying drug resistance determinants. Thirdly, the in-silico identified genetic mutations, which are putatively involved in drug resistance mechanisms, may increase our understanding of the drug resistance mechanisms.

CAMBerVis: visualization software to support comparative analysis of multiple bacterial strains.

MOTIVATION: A number of inconsistencies in genome annotations are documented among bacterial strains. Visualization of the differences may help biologists to make correct decisions in spurious cases. RESULTS: We have developed a visualization tool, CAMBerVis, to support comparative analysis of multiple bacterial strains. The software manages simultaneous visualization of multiple bacterial genomes, enabling visual analysis focused on genome structure annotations. AVAILABILITY: The CAMBerVis software is freely available at the project website: http://bioputer.mimuw.edu.pl/camber. Input datasets for Mycobacterium tuberculosis and Staphylocacus aureus are integrated with the software as examples. CONTACT: m.wozniak@mimuw.edu.pl SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

CAMBer: an approach to support comparative analysis of multiple bacterial strains.

BACKGROUND: There is a large amount of inconsistency in gene structure annotations of bacterial strains. This inconsistency is a frustrating impedance to effective comparative genomic analysis of bacterial strains in promising applications such as gaining insights into bacterial drug resistance. RESULTS: Here, we propose CAMBer as an approach to support comparative analysis of multiple bacterial strains. CAMBer produces what we called multigene families. Each multigene family reveals genes that are in one-to-one correspondence in the bacterial strains, thereby permitting their annotations to be integrated. We present results of our method applied to three human pathogens: Escherichia coli, Mycobacterium tuberculosis and Staphylococcus aureus. CONCLUSIONS: As a result, more accurate and more comprehensive annotations of the bacterial strains can be produced.

Rhythmic diel pattern of gene expression in juvenile maize leaf.

BACKGROUND: Numerous biochemical and physiological parameters of living organisms follow a circadian rhythm. Although such rhythmic behavior is particularly pronounced in plants, which are strictly dependent on the daily photoperiod, data on the molecular aspects of the diurnal cycle in plants is scarce and mostly concerns the model species Arabidopsis thaliana. Here we studied the leaf transcriptome in seedlings of maize, an important C4 crop only distantly related to A. thaliana, throughout a cycle of 10 h darkness and 14 h light to look for rhythmic patterns of gene expression. RESULTS: Using DNA microarrays comprising ca. 43,000 maize-specific probes we found that ca. 12% of all genes showed clear-cut diel rhythms of expression. Cluster analysis identified 35 groups containing from four to ca. 1,000 genes, each comprising genes of similar expression patterns. Perhaps unexpectedly, the most pronounced and most common (concerning the highest number of genes) expression maxima were observed towards and during the dark phase. Using Gene Ontology classification several meaningful functional associations were found among genes showing similar diel expression patterns, including massive induction of expression of genes related to gene expression, translation, protein modification and folding at dusk and night. Additionally, we found a clear-cut tendency among genes belonging to individual clusters to share defined transcription factor-binding sequences. CONCLUSIONS: Co-expressed genes belonging to individual clusters are likely to be regulated by common mechanisms. The nocturnal phase of the diurnal cycle involves gross induction of fundamental biochemical processes and should be studied more thoroughly than was appreciated in most earlier physiological studies. Although some general mechanisms responsible for the diel regulation of gene expression might be shared among plants, details of the diurnal regulation of gene expression seem to differ between taxa.

Deregulation upon DNA damage revealed by joint analysis of context-specific perturbation data.

BACKGROUND: Deregulation between two different cell populations manifests itself in changing gene expression patterns and changing regulatory interactions. Accumulating knowledge about biological networks creates an opportunity to study these changes in their cellular context. RESULTS: We analyze re-wiring of regulatory networks based on cell population-specific perturbation data and knowledge about signaling pathways and their target genes. We quantify deregulation by merging regulatory signal from the two cell populations into one score. This joint approach, called JODA, proves advantageous over separate analysis of the cell populations and analysis without incorporation of knowledge. JODA is implemented and freely available in a Bioconductor package 'joda'. CONCLUSIONS: Using JODA, we show wide-spread re-wiring of gene regulatory networks upon neocarzinostatin-induced DNA damage in Human cells. We recover 645 deregulated genes in thirteen functional clusters performing the rich program of response to damage. We find that the clusters contain many previously characterized neocarzinostatin target genes. We investigate connectivity between those genes, explaining their cooperation in performing the common functions. We review genes with the most extreme deregulation scores, reporting their involvement in response to DNA damage. Finally, we investigate the indirect impact of the ATM pathway on the deregulated genes, and build a hypothetical hierarchy of direct regulation. These results prove that JODA is a step forward to a systems level, mechanistic understanding of changes in gene regulation between different cell populations.