MUSA: a parameter free algorithm for the identification of biologically significant motifs

Comparative Analysis of DNA Motif Discovery Algorithms: A Systemic Review

Background:

Bioinformatics is an interdisciplinary field that combines biology and information technology to study how to deal with the biological data. The DNA motif discovery problem is the main challenge of genome biology and its importance is directly proportional to increasing sequencing technologies which produce large amounts of data. DNA motif is a repeated portion of DNA sequences of major biological interest with important structural and functional features. Motif discovery plays a vital role in the antibody-biomarker identification which is useful for diagnosis of disease and to identify Transcription Factor Binding Sites (TFBSs) that help in learning the mechanisms for regulation of gene expression. Recently, scientists discovered that the TFs have a mutation rate five times higher than the flanking sequences, so motif discovery also has a crucial role in cancer discovery.

Methods:

Over the past decades, many attempts use different algorithms to design fast and accurate motif discovery tools. These algorithms are generally classified into consensus or probabilistic approach.

Results:

Many of DNA motif discovery algorithms are time-consuming and easily trapped in a local optimum.

Conclusion:

Nature-inspired algorithms and many of combinatorial algorithms are recently proposed to overcome the problems of consensus and probabilistic approaches. This paper presents a general classification of motif discovery algorithms with new sub-categories. It also presents a summary comparison between them.

Predicting Gene and Genomic Regulation in Saccharomyces cerevisiae, using the YEASTRACT Database: A Step-by-Step Guided Analysis

Transcriptional regulation is one of the key steps in the control of gene expression, with huge impact on the survival, adaptation, and fitness of all organisms. However, it is becoming increasingly clear that transcriptional regulation is far more complex than initially foreseen. In model organisms such as the yeast Saccharomyces cerevisiae evidence has been piling up showing that the expression of each gene can be controlled by several transcription factors, in the close dependency of the environmental conditions. Furthermore, transcription factors work in intricate networks, being themselves regulated at the transcriptional, post-transcriptional, and post-translational levels, working in cooperation or antagonism in the promoters of their target genes.In this chapter, a step-by-step guide using the YEASTRACT database is provided, for the prediction and ranking of the transcription factors required for the regulation of the expression a single gene and of a genome-wide response. These analyses are illustrated with the regulation of the PDR18 gene and of the transcriptome-wide changes induced upon exposure to the herbicide 2,4-Dichlorophenoxyacetic acid (2,4-D), respectively. The newest potentialities of this information system are explored, and the various results obtained in the dependency of the querying criteria are discussed in terms of the knowledge gathered on the biological responses considered as case studies.

Transcriptional profiling of Arabidopsis root hairs and pollen defines an apical cell growth signature

BACKGROUND

Current views on the control of cell development are anchored on the notion that phenotypes are defined by networks of transcriptional activity. The large amounts of information brought about by transcriptomics should allow the definition of these networks through the analysis of cell-specific transcriptional signatures. Here we test this principle by applying an analogue to comparative anatomy at the cellular level, searching for conserved transcriptional signatures, or conserved small gene-regulatory networks (GRNs) on root hairs (RH) and pollen tubes (PT), two filamentous apical growing cells that are a striking example of conservation of structure and function in plants.

RESULTS

We developed a new method for isolation of growing and mature root hair cells, analysed their transcriptome by microarray analysis, and further compared it with pollen and other single cell transcriptomics data. Principal component analysis shows a statistical relation between the datasets of RHs and PTs which is suggestive of a common transcriptional profile pattern for the apical growing cells in a plant, with overlapping profiles and clear similarities at the level of small GTPases, vesicle-mediated transport and various specific metabolic responses. Furthermore, cis-regulatory element analysis of co-regulated genes between RHs and PTs revealed conserved binding sequences that are likely required for the expression of genes comprising the apical signature. This included a significant occurrence of motifs associated to a defined transcriptional response upon anaerobiosis.

CONCLUSIONS

Our results suggest that maintaining apical growth mechanisms synchronized with energy yielding might require a combinatorial network of transcriptional regulation. We propose that this study should constitute the foundation for further genetic and physiological dissection of the mechanisms underlying apical growth of plant cells.

Models incorporating chromatin modification data identify functionally important p53 binding sites

Genome-wide prediction of transcription factor binding sites is notoriously difficult. We have developed and applied a logistic regression approach for prediction of binding sites for the p53 transcription factor that incorporates sequence information and chromatin modification data. We tested this by comparison of predicted sites with known binding sites defined by chromatin immunoprecipitation (ChIP), by the location of predictions relative to genes, by the function of nearby genes and by analysis of gene expression data after p53 activation. We compared the predictions made by our novel model with predictions based only on matches to a sequence position weight matrix (PWM). In whole genome assays, the fraction of known sites identified by the two models was similar, suggesting that there was little to be gained from including chromatin modification data. In contrast, there were highly significant and biologically relevant differences between the two models in the location of the predicted binding sites relative to genes, in the function of nearby genes and in the responsiveness of nearby genes to p53 activation. We propose that these contradictory results can be explained by PWM and ChIP data reflecting primarily biophysical properties of protein–DNA interactions, whereas chromatin modification data capture biologically important functional information.

Computational approaches, databases and tools for in silico motif discovery

Motifs are the biologically significant fragments of nucleotide or peptide sequences in a specific pattern. Motifs are categorized as structural motifs and sequence motifs. These are discovered by phylogenetic studies of similar genes across species. Structural motifs are formed by three dimensional arrangements of amino acids consisting of two or more α helices or β strands whereas sequence motifs are formed by the nucleotide fragments appearing in the exons of a gene. The arrangement of residues in structural motifs may not be continuous while it is continuous in sequence motifs. Sequence motifs may encode to the structural motifs. The algorithms used for motif discovery are important part of the bio-computational studies. The purpose of motif discovery is to identify patterns in biopolymer (nucleotide or protein) sequences to understand the structure and function of the molecules and their evolutionary aspects. The main aim of this paper is to provide systematic compilation of a review on different approaches, databases and tools used in motif discovery.

Direct vs 2-stage approaches to structured motif finding

Background

The notion of DNA motif is a mathematical abstraction used to model regions of the DNA (known as Transcription Factor Binding Sites, or TFBSs) that are bound by a given Transcription Factor to regulate gene expression or repression. In turn, DNA structured motifs are a mathematical counterpart that models sets of TFBSs that work in concert in the gene regulations processes of higher eukaryotic organisms. Typically, a structured motif is composed of an ordered set of isolated (or simple) motifs, separated by a variable, but somewhat constrained number of “irrelevant” base-pairs. Discovering structured motifs in a set of DNA sequences is a computationally hard problem that has been addressed by a number of authors using either a direct approach, or via the preliminary identification and successive combination of simple motifs.

Results

We describe a computational tool, named SISMA, for the de-novo discovery of structured motifs in a set of DNA sequences. SISMA is an exact, enumerative algorithm, meaning that it finds all the motifs conforming to the specifications. It does so in two stages: first it discovers all the possible component simple motifs, then combines them in a way that respects the given constraints. We developed SISMA mainly with the aim of understanding the potential benefits of such a 2-stage approach w.r.t. direct methods. In fact, no 2-stage software was available for the general problem of structured motif discovery, but only a few tools that solved restricted versions of the problem. We evaluated SISMA against other published tools on a comprehensive benchmark made of both synthetic and real biological datasets. In a significant number of cases, SISMA outperformed the competitors, exhibiting a good performance also in most of the cases in which it was inferior.

Conclusions

A reflection on the results obtained lead us to conclude that a 2-stage approach can be implemented with many advantages over direct approaches. Some of these have to do with greater modularity, ease of parallelization, and the possibility to perform adaptive searches of structured motifs. As another consideration, we noted that most hard instances for SISMA were easy to detect in advance. In these cases one may initially opt for a direct method; or, as a viable alternative in most laboratories, one could run both direct and 2-stage tools in parallel, halting the computations when the first halts.

Yeast IME2 functions early in meiosis upstream of cell cycle-regulated SBF and MBF targets

Background

In Saccharomyces cerevisiae, the G1 cyclin/cyclin-dependent kinase (CDK) complexes Cln1,-2,-3/Cdk1 promote S phase entry during the mitotic cell cycle but do not function during meiosis. It has been proposed that the meiosis-specific protein kinase Ime2, which is required for normal timing of pre-meiotic DNA replication, is equivalent to Cln1,-2/Cdk1. These two CDK complexes directly catalyze phosphorylation of the B-type cyclin/CDK inhibitor Sic1 during the cell cycle to enable its destruction. As a result, Clb5,-6/Cdk1 become activated and facilitate initiation of DNA replication. While Ime2 is required for Sic1 destruction during meiosis, evidence now suggests that Ime2 does not directly catalyze Sic1 phosphorylation to target it for destabilization as Cln1,-2/Cdk1 do during the cell cycle.

Methodology/Principal Findings

We demonstrated that Sic1 is eventually degraded in meiotic cells lacking the IME2 gene (ime2Δ), supporting an indirect role of Ime2 in Sic1 destruction. We further examined global RNA expression comparing wild type and ime2Δ cells. Analysis of these expression data has provided evidence that Ime2 is required early in meiosis for normal transcription of many genes that are also periodically expressed during late G1 of the cell cycle.

Conclusions/Significance

Our results place Ime2 at a position in the early meiotic pathway that lies upstream of the position occupied by Cln1,-2/Cdk1 in the analogous cell cycle pathway. Thus, Ime2 may functionally resemble Cln3/Cdk1 in promoting S phase entry, or it could play a role even further upstream in the corresponding meiotic cascade.

2D electrophoresis-based expression proteomics: a microbiologist's perspective

Quantitative proteomics based on 2D electrophoresis (2-DE) coupled with peptide mass fingerprinting is still one of the most widely used quantitative proteomics approaches in microbiology research. Our view on the exploitation of this global expression analysis technique and its contribution and potential to push forward the field of molecular microbial physiology towards a molecular systems microbiology perspective is discussed in this article. The advances registered in 2-DE-based quantitative proteomic analysis leading to increased protein resolution, sensitivity and accuracy, and the promising use of 2-DE to gain insights into post-translational modifications at a proteome-wide level (considering all the proteins/protein forms expressed by the genome) are focused on. Given the progress made in this field, it is foreseen that the 2-DE-based approach to quantitative proteomics will continue to be a fundamental tool for microbiologists working at a genome-wide scale. Guidelines are also provided for the exploitation of expression proteomics data, based on useful computational tools, and for the integration of these data with other genome-wide expression information. The advantages and limitations of a complete 2-DE-based expression proteomics analysis, envisaging the quantification of the global changes occurring in the proteome of a given cell depending on environmental or genetic manipulations, are discussed from the microbiologist's perspective. Particular focus is given to the emerging field of toxicoproteomics, a new systems toxicity approach that offers a powerful tool to directly monitor the earliest stages of the toxicological response by identifying critical proteins and pathways that are affected by, and respond to, a chemical stress. The experimental design and the bioinformatics analysis of data used in our laboratory to gain mechanistic insights through expression proteomics into the responses of the eukaryotic model Saccharomyces cerevisiae or of Pseudomonas strains to environmental toxicants are presented as case studies.

Functional gene expression profiling in yeast implicates translational dysfunction in mutant huntingtin toxicity

Huntington disease (HD) is a neurodegenerative disorder caused by the expansion of a polyglutamine tract in the huntingtin (htt) protein. To uncover candidate therapeutic targets and networks involved in pathogenesis, we integrated gene expression profiling and functional genetic screening to identify genes critical for mutant htt toxicity in yeast. Using mRNA profiling, we have identified genes differentially expressed in wild-type yeast in response to mutant htt toxicity as well as in three toxicity suppressor strains: bna4Δ, mbf1Δ, and ume1Δ. BNA4 encodes the yeast homolog of kynurenine 3-monooxygenase, a promising drug target for HD. Intriguingly, despite playing diverse cellular roles, these three suppressors share common differentially expressed genes involved in stress response, translation elongation, and mitochondrial transport. We then systematically tested the ability of the differentially expressed genes to suppress mutant htt toxicity when overexpressed and have thereby identified 12 novel suppressors, including genes that play a role in stress response, Golgi to endosome transport, and rRNA processing. Integrating the mRNA profiling data and the genetic screening data, we have generated a robust network that shows enrichment in genes involved in rRNA processing and ribosome biogenesis. Strikingly, these observations implicate dysfunction of translation in the pathology of HD. Recent work has shown that regulation of translation is critical for life span extension in Drosophila and that manipulation of this process is protective in Parkinson disease models. In total, these observations suggest that pharmacological manipulation of translation may have therapeutic value in HD.

YEASTRACT-DISCOVERER: new tools to improve the analysis of transcriptional regulatory associations in Saccharomyces cerevisiae

The Yeast search for transcriptional regulators and consensus tracking (YEASTRACT) information system (www.yeastract.com) was developed to support the analysis of transcription regulatory associations in Saccharomyces cerevisiae. Last updated in September 2007, this database contains over 30 990 regulatory associations between Transcription Factors (TFs) and target genes and includes 284 specific DNA binding sites for 108 characterized TFs. Computational tools are also provided to facilitate the exploitation of the gathered data when solving a number of biological questions, in particular the ones that involve the analysis of global gene expression results. In this new release, YEASTRACT includes DISCOVERER, a set of computational tools that can be used to identify complex motifs over-represented in the promoter regions of co-regulated genes. The motifs identified are then clustered in families, represented by a position weight matrix and are automatically compared with the known transcription factor binding sites described in YEASTRACT. Additionally, in this new release, it is possible to generate graphic depictions of transcriptional regulatory networks for documented or potential regulatory associations between TFs and target genes. The visual display of these networks of interactions is instrumental in functional studies. Tutorials are available on the system to exemplify the use of all the available tools.

A survey of DNA motif finding algorithms

BACKGROUND

Unraveling the mechanisms that regulate gene expression is a major challenge in biology. An important task in this challenge is to identify regulatory elements, especially the binding sites in deoxyribonucleic acid (DNA) for transcription factors. These binding sites are short DNA segments that are called motifs. Recent advances in genome sequence availability and in high-throughput gene expression analysis technologies have allowed for the development of computational methods for motif finding. As a result, a large number of motif finding algorithms have been implemented and applied to various motif models over the past decade. This survey reviews the latest developments in DNA motif finding algorithms.

RESULTS

Earlier algorithms use promoter sequences of coregulated genes from single genome and search for statistically overrepresented motifs. Recent algorithms are designed to use phylogenetic footprinting or orthologous sequences and also an integrated approach where promoter sequences of coregulated genes and phylogenetic footprinting are used. All the algorithms studied have been reported to correctly detect the motifs that have been previously detected by laboratory experimental approaches, and some algorithms were able to find novel motifs. However, most of these motif finding algorithms have been shown to work successfully in yeast and other lower organisms, but perform significantly worse in higher organisms.

CONCLUSION

Despite considerable efforts to date, DNA motif finding remains a complex challenge for biologists and computer scientists. Researchers have taken many different approaches in developing motif discovery tools and the progress made in this area of research is very encouraging. Performance comparison of different motif finding tools and identification of the best tools have proven to be a difficult task because tools are designed based on algorithms and motif models that are diverse and complex and our incomplete understanding of the biology of regulatory mechanism does not always provide adequate evaluation of underlying algorithms over motif models.

Mechanistic Insights Into the Global Response to Phenol in the Phenol-biodegrading StrainPseudomonassp. M1 Revealed by Quantitative Proteomics

Quantitative proteomics was used to gain insights into the global adaptive response to phenol in the phenol-biodegrading strain Pseudomonas sp. M1 when an alternative carbon source (pyruvate or succinate) is present. A phylogenetic analysis indicated Pseudomonas citronellolis as the closest species to the environmental strain M1, while P. aeruginosa is the closest species with the genome sequence available. After two-dimensional gel electrophoresis (2-DE) separation, protein identification by MS/MS ion search allowed the assignment of 87 out of 136 selected protein spots, 56 of which matched P. aeruginosa proteins present in databases. Coordinate induction of six enzymes of the phenol catabolic pathway in cells grown in pyruvate and phenol was revealed by expression proteomics. When succinate was the alternative carbon source (C-source), these catabolic proteins were not expressed. The global response of Pseudomonas sp. M1 to phenol-induced stress involved, among others, proteins of the energy metabolism, stress response proteins, and transport proteins. Quantitative and/or qualitative differences were registered in M1 response to different phenol concentrations or to identical phenol concentrations when cells were grown in pyruvate or succinate medium. They were attributed to differences observed in the specific growth rate, in the expression of phenol catabolism, and in resistance to phenol of Pseudomonas sp. M1 grown under different conditions.

GAPWM: a genetic algorithm method for optimizing a position weight matrix

MOTIVATION

Position weight matrices (PMWs) are simple models commonly used in motif-finding algorithms to identify short functional elements, such as cis-regulatory motifs, on genes. When few experimentally verified motifs are available, estimation of the PWM may be poor. The resultant PWM may not reliably discriminate a true motif from a false one. While experimentally identifying such motifs remains time-consuming and expensive, low-resolution binding data from techniques such as ChIP-on-chip and ChIP-PET have become available. We propose a novel but simple method to improve a poorly estimated PWM using ChIP data.

METHODOLOGY

Starting from an existing PWM, a set of ChIP sequences, and a set of background sequences, our method, GAPWM, derives an improved PWM via a genetic algorithm that maximizes the area under the receiver operating characteristic (ROC) curve. GAPWM can easily incorporate prior information such as base conservation. We tested our method on two PMWs (Oct4/Sox2 and p53) using three recently published ChIP data sets (human Oct4, mouse Oct4 and human p53).

RESULTS

GAPWM substantially increased the sensitivity/specificity of a poorly estimated PWM and further improved the quality of a good PWM. Furthermore, it still functioned when the starting PWM contained a major error. The ROC performance of GAPWM compared favorably with that of MEME and others. With increasing availability of ChIP data, our method provides an alternative for obtaining high-quality PWMs for genome-wide identification of transcription factor binding sites.

AVAILABILITY

The C source code and all data used in this report are available at http://dir.niehs.nih.gov/dirbb/gapwm.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.