PubMed Health⌕ Search

Biomedical subjects

Martin Tompa

Publications and source records attributed to Martin Tompa.

17 recordsLinked to original sources

Mis-translation of a computationally designed protein yields an exceptionally stable homodimer: implications for protein engineering and evolution.

We recently used computational protein design to create an extremely stable, globular protein, Top7, with a sequence and fold not observed previously in nature. Since Top7 was created in the absence of genetic selection, it provides a rare opportunity to investigate aspects of the cellular protein production and surveillance machinery that are subject to natural selection. Here we show that a portion of the Top7 protein corresponding to the final 49 C-terminal residues is efficiently mis-translated and accumulates at high levels in Escherichia coli. We used circular dichroism, size-exclusion chromatography, small-angle X-ray scattering, analytical ultra-centrifugation, and NMR spectroscopy to show that the resulting C-terminal fragment (CFr) protein adopts a compact, extremely stable, homo-dimeric structure. Based on the solution structure, we engineered an even more stable variant of CFr by disulfide-induced covalent circularisation that should be an excellent platform for design of novel functions. The accumulation of high levels of CFr exposes the high error rate of the protein translation machinery. The rarity of correspondingly stable fragments in natural proteins coupled with the observation that high quality ribosome binding sites are found to occur within E. coli protein-coding regions significantly less often than expected by random chance implies a stringent evolutionary pressure against protein sub-fragments that can independently fold into stable structures. The symmetric self-association between two identical mis-translated CFr sub-domains to generate an extremely stable structure parallels a mechanism for natural protein-fold evolution by modular recombination of protein sub-structures.

Amino Acid Sequence↗

MicroFootPrinter: a tool for phylogenetic footprinting in prokaryotic genomes.

Phylogenetic footprinting is a method for the discovery of regulatory elements in a set of homologous regulatory regions, usually collected from multiple species. It does so by identifying the most conserved motifs in those homologous regions. This note describes web software that has been designed specifically for this purpose in prokaryotic genomes, making use of the phylogenetic relationships among the homologous sequences in order to make more accurate predictions. The software is called MicroFootPrinter and is available at http://bio.cs.washington.edu/software.html.

Genome, Archaeal↗

Analysis of computational approaches for motif discovery.

Recently, we performed an assessment of 13 popular computational tools for discovery of transcription factor binding sites (M. Tompa, N. Li, et al., "Assessing Computational Tools for the Discovery of Transcription Factor Binding Sites", Nature Biotechnology, Jan. 2005). This paper contains follow-up analysis of the assessment results, and raises and discusses some important issues concerning the state of the art in motif discovery methods: 1. We categorize the objective functions used by existing tools, and design experiments to evaluate whether any of these objective functions is the right one to optimize. 2. We examine various features of the data sets that were used in the assessment, such as sequence length and motif degeneracy, and identify which features make data sets hard for current motif discovery tools. 3. We identify an important feature that has not yet been used by existing tools and propose a new objective function that incorporates this feature.

Journal Article↗

Assessing computational tools for the discovery of transcription factor binding sites.

The prediction of regulatory elements is a problem where computational methods offer great hope. Over the past few years, numerous tools have become available for this task. The purpose of the current assessment is twofold: to provide some guidance to users regarding the accuracy of currently available tools in various settings, and to provide a benchmark of data sets for assessing future tools.

Amino Acid Motifs↗

Discovery of regulatory elements in vertebrates through comparative genomics.

We have analyzed issues of reliability in studies in which comparative genomic approaches have been applied to the discovery of regulatory elements at a genome-wide level in vertebrates. We point out some potential problems with such studies, including difficulties in accurately identifying orthologous promoter regions. Many of these subtle analytical problems have become apparent only when studying the more complex vertebrate genomes. By determining motif reliability, we compared existing tools when applied to the discovery of vertebrate regulatory elements. We then used a statistical clustering method to produce a computational catalog of high quality putative regulatory elements from vertebrates, some of which are widely conserved among vertebrates and many of which are novel regulatory elements. The results provide a glimpse into the wealth of information that comparative genomics can yield and suggest the need for further improvement of genome-wide comparative computational techniques.

Algorithms↗

Statistics of local multiple alignments.

SUMMARY: BLAST statistics have been shown to be extremely useful for searching for significant similarity hits, for amino acid and nucleotide sequences. Although these statistics are well understood for pairwise comparisons, there has been little success developing statistical scores for multiple alignments. In particular, there is no score for multiple alignment that is well founded and treated as a standard. We extend the BLAST theory to multiple alignments. Following some simple assumptions, we present and justify a significance score for multiple segments of a local multiple alignment. We demonstrate its usefulness in distinguishing high and moderate quality multiple alignments from low quality ones, with supporting experiments on orthologous vertebrate promoter sequences.

Algorithms↗

PhyME: a probabilistic algorithm for finding motifs in sets of orthologous sequences.

BACKGROUND: This paper addresses the problem of discovering transcription factor binding sites in heterogeneous sequence data, which includes regulatory sequences of one or more genes, as well as their orthologs in other species. RESULTS: We propose an algorithm that integrates two important aspects of a motif's significance - overrepresentation and cross-species conservation - into one probabilistic score. The algorithm allows the input orthologous sequences to be related by any user-specified phylogenetic tree. It is based on the Expectation-Maximization technique, and scales well with the number of species and the length of input sequences. We evaluate the algorithm on synthetic data, and also present results for data sets from yeast, fly, and human. CONCLUSIONS: The results demonstrate that the new approach improves motif discovery by exploiting multiple species information.

Algorithms↗

Evolutionarily conserved sequence elements that positively regulate IFN-gamma expression in T cells.

Our understanding of mechanisms by which the expression of IFN-gamma is regulated is limited. Herein, we identify two evolutionarily conserved noncoding sequence elements (IFNgCNS1 and IFNg CNS2) located approximately 5 kb upstream and approximately 18 kb downstream of the initiation codon of the murine Ifng gene. When linked to the murine Ifng gene (-3.4 to +5.6 kb) and transiently transfected into EL-4 cells, these elements clearly enhanced IFN-gamma expression in response to ionomycin and phorbol 12-myristate 13-acetate and weakly enhanced expression in response to T-bet. A DNase I hypersensitive site and extragenic transcripts at IFNgCNS2 correlated positively with the capacity of primary T cell subsets to produce IFN-gamma. Transcriptionally favorable histone modifications in the Ifng promoter, intronic regions, IFNgCNS2, and, although less pronounced, IFNgCNS1 increased as naïve T cells differentiated into IFN-gamma-producing effector CD8+ and T helper (TH) 1 T cells, but not into TH2 T cells. Like IFN-gamma expression, these histone modifications were T-bet-dependent in CD4+ cells, but not CD8+ T cells. These findings define two distal regulatory elements associated with T cell subset-specific IFN-gamma expression.

Animals↗

FootPrinter: A program designed for phylogenetic footprinting.

Phylogenetic footprinting is a method for the discovery of regulatory elements in a set of homologous regulatory regions, usually collected from multiple species. It does so by identifying the best conserved motifs in those homologous regions. This note describes web software that has been designed specifically for this purpose, making use of the phylogenetic relationships among the homologous sequences in order to make more accurate predictions. The software is called FootPrinter and is available at http://bio.cs.washington.edu/software.html.

Algorithms↗

YMF: A program for discovery of novel transcription factor binding sites by statistical overrepresentation.

A fundamental challenge facing biologists is to identify DNA binding sites for unknown regulatory factors, given a collection of genes believed to be coregulated. The program YMF identifies good candidates for such binding sites by searching for statistically overrepresented motifs. More specifically, YMF enumerates all motifs in the search space and is guaranteed to produce those motifs with greatest z-scores. This note describes the YMF web software, available at http://bio.cs.washington.edu/software.html.

Algorithms↗

Rv3133c/dosR is a transcription factor that mediates the hypoxic response of Mycobacterium tuberculosis.

Unlike many pathogens that are overtly harmful to their hosts, Mycobacterium tuberculosis can persist for years within humans in a clinically latent state. Latency is often linked to hypoxic conditions within the host. Among M. tuberculosis genes induced by hypoxia is a putative transcription factor, Rv3133c/DosR. We performed targeted disruption of this locus followed by transcriptome analysis of wild-type and mutant bacilli. Nearly all the genes powerfully regulated by hypoxia require Rv3133c/DosR for their induction. Computer analysis identified a consensus motif, a variant of which is located upstream of nearly all M. tuberculosis genes rapidly induced by hypoxia. Further, Rv3133c/DosR binds to the two copies of this motif upstream of the hypoxic response gene alpha-crystallin. Mutations within the binding sites abolish both Rv3133c/DosR binding as well as hypoxic induction of a downstream reporter gene. Also, mutation experiments with Rv3133c/DosR confirmed sequence-based predictions that the C-terminus is responsible for DNA binding and that the aspartate at position 54 is essential for function. Together, these results demonstrate that Rv3133c/DosR is a transcription factor of the two-component response regulator class, and that it is the primary mediator of a hypoxic signal within M. tuberculosis.

Aspartic Acid↗

Discovery of novel transcription factor binding sites by statistical overrepresentation.

Understanding the complex and varied mechanisms that regulate gene expression is an important and challenging problem. A fundamental sub-problem is to identify DNA binding sites for unknown regulatory factors, given a collection of genes believed to be co-regulated. We discuss a computational method that identifies good candidates for such binding sites. Unlike local search techniques such as expectation maximization and Gibbs samplers that may not reach a global optimum, the method discussed enumerates all motifs in the search space, and is guaranteed to produce the motifs with greatest z-scores. We discuss the results of validation experiments in which this algorithm was used to identify candidate binding sites in several well studied regulons of Saccharomyces cerevisiae, where the most prominent transcription factor binding sites are largely known. We then discuss the results on gene families in the functional and mutant phenotype catalogs of S.cerevisiae, where the algorithm suggests many promising novel transcription factor binding sites. The program is available at http://bio.cs.washington.edu/software.html.

Algorithms↗

Quality control in manufacturing oligo arrays: a combinatorial design approach.

The advent of the DNA microarray technology has brought with it the exciting possibility of simultaneously observing the expression levels of all genes in an organism. One such microarray technology, called "oligo arrays," manufactures short single strands of DNA (called probes) onto a glass surface using photolithography. An altered or missed step in such a manufacturing protocol can adversely affect all probes using this failed step and is in general impossible to disentangle from experimental variation when using such a defective array. The idea of designing special quality control probes to detect a failed step was first formulated by Hubbell and Pevzner (1999). We consider an alternative formulation of this problem and use a combinatorial design approach to solve it. Our results improve over prior work in guaranteeing coverage of all protocol steps and in being able to tolerate a greater number of unreliable probe intensities.

Combinatorial Chemistry Techniques↗

Algorithms for phylogenetic footprinting.

Phylogenetic footprinting is a technique that identifies regulatory elements by finding unusually well conserved regions in a set of orthologous noncoding DNA sequences from multiple species. We introduce a new motif-finding problem, the Substring Parsimony Problem, which is a formalization of the ideas behind phylogenetic footprinting, and we present an exact dynamic programming algorithm to solve it. We then present a number of algorithmic optimizations that allow our program to run quickly on most biologically interesting datasets. We show how to handle data sets in which only an unknown subset of the sequences contains the regulatory element. Finally, we describe how to empirically assess the statistical significance of the motifs found. Each technique is implemented and successfully identifies a number of known binding sites, as well as several highly conserved but uncharacterized regions. The program is available at http://bio.cs.washington.edu/software.html.

Algorithms↗

Finding motifs using random projections.

The DNA motif discovery problem abstracts the task of discovering short, conserved sites in genomic DNA. Pevzner and Sze recently described a precise combinatorial formulation of motif discovery that motivates the following algorithmic challenge: find twenty planted occurrences of a motif of length fifteen in roughly twelve kilobases of genomic sequence, where each occurrence of the motif differs from its consensus in four randomly chosen positions. Such "subtle" motifs, though statistically highly significant, expose a weakness in existing motif-finding algorithms, which typically fail to discover them. Pevzner and Sze introduced new algorithms to solve their (15,4)-motif challenge, but these methods do not scale efficiently to more difficult problems in the same family, such as the (14,4)-, (16,5)-, and (18,6)-motif problems. We introduce a novel motif-discovery algorithm, PROJECTION, designed to enhance the performance of existing motif finders using random projections of the input's substrings. Experiments on synthetic data demonstrate that PROJECTION remedies the weakness observed in existing algorithms, typically solving the difficult (14,4)-, (16,5)-, and (18,6)-motif problems. Our algorithm is robust to nonuniform background sequence distributions and scales to larger amounts of sequence than that specified in the original challenge. A probabilistic estimate suggests that related motif-finding problems that PROJECTION fails to solve are in all likelihood inherently intractable. We also test the performance of our algorithm on realistic biological examples, including transcription factor binding sites in eukaryotes and ribosome binding sites in prokaryotes.

Algorithms↗

Construction of optimal quality control for oligo arrays.

MOTIVATION: Oligo arrays are important experimental tools for the high throughput measurement of gene expression levels. During production of oligo arrays, it is important to identify any faulty manufacturing step. RESULTS: We describe a practical algorithm for the construction of optimal quality control designs that identify any faulty manufacturing step. The algorithm uses hillclimbing, a search technique from combinatorial optimization. We also present the results of using this algorithm on all practical quality control design sizes. AVAILABILITY: On request from the authors.

Algorithms↗

Discovery of regulatory elements by a computational method for phylogenetic footprinting.

Phylogenetic footprinting is a method for the discovery of regulatory elements in a set of orthologous regulatory regions from multiple species. It does so by identifying the best conserved motifs in those orthologous regions. We describe a computer algorithm designed specifically for this purpose, making use of the phylogenetic relationships among the sequences under study to make more accurate predictions. The program is guaranteed to report all sets of motifs with the lowest parsimony scores, calculated with respect to the phylogenetic tree relating the input species. We report the results of this algorithm on several data sets of interest. A large number of known functional binding sites are identified by our method, but we also find several highly conserved motifs for which no function is yet known.

Algorithms↗