CiteULike: Ema's library [273 articles]

Investigating selection on viruses: a statistical alignment approach

Saskia de Groot — 2008-07-11T02:48:26-00:00

BMC Bioinformatics, Vol. 9 (10 July 2008), 304.

The Ascent of the Abundant: How Mutational Networks Constrain Evolution

Matthew Cowperthwaite — 2008-07-19T10:33:34-00:00

PLoS Comput Biol, Vol. 4, No. 7. (18 July 2008), e1000110.

Evolution by natural selection is fundamentally shaped by the fitness landscapes in which it occurs. Yet fitness landscapes are vast and complex, and thus we know relatively little about the long-range constraints they impose on evolutionary dynamics. Here, we exhaustively survey the structural landscapes of RNA molecules of lengths 12 to 18 nucleotides, and develop a network model to describe the relationship between sequence and structure. We find that phenotype abundance—the number of genotypes producing a particular phenotype—varies in a predictable manner and critically influences evolutionary dynamics. A study of naturally occurring functional RNA molecules using a new structural statistic suggests that these molecules are biased toward abundant phenotypes. This supports an “ascent of the abundant” hypothesis, in which evolution yields abundant phenotypes even when they are not the most fit.

Memory Switches in Chemical Reaction Space

Naren Ramakrishnan — 2008-07-19T10:33:19-00:00

PLoS Comput Biol, Vol. 4, No. 7. (18 July 2008), e1000122.

Just as complex electronic circuits are built from simple Boolean gates, diverse biological functions, including signal transduction, differentiation, and stress response, frequently use biochemical switches as a functional module. A relatively small number of such switches have been described in the literature, and these exhibit considerable diversity in chemical topology. We asked if biochemical switches are indeed rare and if there are common chemical motifs and family relationships among such switches. We performed a systematic exploration of chemical reaction space by generating all possible stoichiometrically valid chemical configurations up to 3 molecules and 6 reactions and up to 4 molecules and 3 reactions. We used Monte Carlo sampling of parameter space for each such configuration to generate specific models and checked each model for switching properties. We found nearly 4,500 reaction topologies, or about 10% of our tested configurations, that demonstrate switching behavior. Commonly accepted topological features such as feedback were poor predictors of bistability, and we identified new reaction motifs that were likely to be found in switches. Furthermore, the discovered switches were related in that most of the larger configurations were derived from smaller ones by addition of one or more reactions. To explore even larger configurations, we developed two tools: the “bistabilizer,” which converts almost-bistable systems into bistable ones, and frequent motif mining, which helps rank untested configurations. Both of these tools increased the coverage of our library of bistable systems. Thus, our systematic exploration of chemical reaction space has produced a valuable resource for investigating the key signaling motif of bistability.

Dynamics of Genome Rearrangement in Bacterial Populations

Aaron Darling — 2008-07-19T10:32:45-00:00

PLoS Genet, Vol. 4, No. 7. (18 July 2008), e1000128.

Genome structure variation has profound impacts on phenotype in organisms ranging from microbes to humans, yet little is known about how natural selection acts on genome arrangement. Pathogenic bacteria such as Yersinia pestis, which causes bubonic and pneumonic plague, often exhibit a high degree of genomic rearrangement. The recent availability of several Yersinia genomes offers an unprecedented opportunity to study the evolution of genome structure and arrangement. We introduce a set of statistical methods to study patterns of rearrangement in circular chromosomes and apply them to the Yersinia. We constructed a multiple alignment of eight Yersinia genomes using Mauve software to identify 78 conserved segments that are internally free from genome rearrangement. Based on the alignment, we applied Bayesian statistical methods to infer the phylogenetic inversion history of Yersinia. The sampling of genome arrangement reconstructions contains seven parsimonious tree topologies, each having different histories of 79 inversions. Topologies with a greater number of inversions also exist, but were sampled less frequently. The inversion phylogenies agree with results suggested by SNP patterns. We then analyzed reconstructed inversion histories to identify patterns of rearrangement. We confirm an over-representation of “symmetric inversions”—inversions with endpoints that are equally distant from the origin of chromosomal replication. Ancestral genome arrangements demonstrate moderate preference for replichore balance in Yersinia. We found that all inversions are shorter than expected under a neutral model, whereas inversions acting within a single replichore are much shorter than expected. We also found evidence for a canonical configuration of the origin and terminus of replication. Finally, breakpoint reuse analysis reveals that inversions with endpoints proximal to the origin of DNA replication are nearly three times more frequent. Our findings represent the first characterization of genome arrangement evolution in a bacterial population evolving outside laboratory conditions. Insight into the process of genomic rearrangement may further the understanding of pathogen population dynamics and selection on the architecture of circular bacterial chromosomes.

RNA-seq: An assessment of technical reproducibility and comparison with gene expression arrays

John Marioni — 2008-06-11T20:56:53-00:00

Genome Res. (11 June 2008), gr.079558.108.

Ultra high-throughput sequencing is emerging as an attractive alternative to microarrays for genotyping, analysis of methylation patterns and identification of transcription factor binding sites. Here, we describe an application of the Illumina sequencing platform to study mRNA expression levels. Our goals were to estimate technical variance associated with Illumina sequencing in this context and to compare its ability to identify differentially expressed genes with existing array technologies. To do so, we estimated gene expression differences between liver and kidney RNA samples using multiple sequencing replicates, and compared the sequencing data to results obtained from Affymetrix arrays using the same RNA samples. We find that the Illumina sequencing data are highly replicable, with relatively little technical variation, and so, for many purposes, it may suffice to sequence each mRNA sample only once (i.e., using one lane). The information in a single lane of Illumina sequencing data appears comparable to that in a single array in enabling identification of differentially expressed genes, while allowing for additional analyses such as detection of low-expressed genes, alternative splice variants, and novel transcripts. Based on our observations, we propose an empirical protocol and a statistical framework for the analysis of gene expression using ultra high-throughput sequencing technology. 10.1101/gr.079558.108

Tuning gene expression to changing environments: from rapid responses to evolutionary adaptation.

Luis López-Maury — 2008-07-03T12:20:07-00:00

Nature reviews. Genetics (1 July 2008)

Organisms are constantly exposed to a wide range of environmental changes, including both short-term changes during their lifetime and longer-term changes across generations. Stress-related gene expression programmes, characterized by distinct transcriptional mechanisms and high levels of noise in their expression patterns, need to be balanced with growth-related gene expression programmes. A range of recent studies give fascinating insight into cellular strategies for keeping gene expression in tune with physiological needs dictated by the environment, promoting adaptation to both short- and long-term environmental changes. Not only do organisms show great resilience to external challenges, but emerging data suggest that they also exploit these challenges to fuel phenotypic variation and evolutionary innovation.

A Global View of Gene Activity and Alternative Splicing by Deep Sequencing of the Human Transcriptome

Marc Sultan — 2008-07-03T22:17:09-00:00

Science (3 July 2008), 1160342.

The functional complexity of the human transcriptome is not yet fully elucidated. We report a high-throughput sequence of the human transcriptome from a human embryonic kidney and a B cell line. Shotgun sequencing of transcripts was used to generate randomly distributed reads. Of these, 50% mapped to unique genomic location, of which 80% corresponded to known exons. We found that 66% of the polyadenylated transcriptome mapped to known genes and 34% to non-annotated genomic regions. Based on known transcripts, RNAseq can detect 25% more genes than microarrays. A global survey of mRNA splicing events identified 94,241 splice junctions, of which 4,096 are novel, and showed that exon skipping is the most prevalent form of alternative splicing. 10.1126/science.1160342

Genome-wide transcription and the implications for genomic organization.

Philipp Kapranov — 2007-05-10T13:57:03-00:00

Nat Rev Genet (8 May 2007)

Recent evidence of genome-wide transcription in several species indicates that the amount of transcription that occurs cannot be entirely accounted for by current sets of genome-wide annotations. Evidence indicates that most of both strands of the human genome might be transcribed, implying extensive overlap of transcriptional units and regulatory elements. These observations suggest that genomic architecture is not colinear, but is instead interleaved and modular, and that the same genomic sequences are multifunctional: that is, used for multiple independently regulated transcripts and as regulatory regions. What are the implications and consequences of such an interleaved genomic architecture in terms of increased information content, transcriptional complexity, evolution and disease states?

Energetics of the protein-DNA-water interaction

Francesca Spyrakis — 2007-01-12T00:43:08-00:00

BMC Structural Biology, Vol. 7 (10 January 2007), 4.

The Generation of Promoter-Mediated Transcriptional Noise in Bacteria

Namiko Mitarai — 2008-07-11T23:04:13-00:00

PLoS Comput Biol, Vol. 4, No. 7. (11 July 2008), e1000109.

Noise in the expression of a gene produces fluctuations in the concentration of the gene product. These fluctuations can interfere with optimal function or can be exploited to generate beneficial diversity between cells; gene expression noise is therefore expected to be subject to evolutionary pressure. Shifts between modes of high and low rates of transcription initiation at a promoter appear to contribute to this noise both in eukaryotes and prokaryotes. However, models invoked for eukaryotic promoter noise such as stable activation scaffolds or persistent nucleosome alterations seem unlikely to apply to prokaryotic promoters. We consider the relative importance of the steps required for transcription initiation. The 3-step transcription initiation model of McClure is extended into a mathematical model that can be used to predict consequences of additional promoter properties. We show in principle that the transcriptional bursting observed at an E. coli promoter by Golding et al. (2005) can be explained by stimulation of initiation by the negative supercoiling behind a transcribing RNA polymerase (RNAP) or by the formation of moribund or dead-end RNAP-promoter complexes. Both mechanisms are tunable by the alteration of promoter kinetics and therefore allow the optimization of promoter mediated noise.

Evolution of Evolvability in Gene Regulatory Networks

Anton Crombach — 2008-07-11T23:04:19-00:00

PLoS Comput Biol, Vol. 4, No. 7. (11 July 2008), e1000112.

Gene regulatory networks are perhaps the most important organizational level in the cell where signals from the cell state and the outside environment are integrated in terms of activation and inhibition of genes. For the last decade, the study of such networks has been fueled by large-scale experiments and renewed attention from the theoretical field. Different models have been proposed to, for instance, investigate expression dynamics, explain the network topology we observe in bacteria and yeast, and for the analysis of evolvability and robustness of such networks. Yet how these gene regulatory networks evolve and become evolvable remains an open question. An individual-oriented evolutionary model is used to shed light on this matter. Each individual has a genome from which its gene regulatory network is derived. Mutations, such as gene duplications and deletions, alter the genome, while the resulting network determines the gene expression pattern and hence fitness. With this protocol we let a population of individuals evolve under Darwinian selection in an environment that changes through time. Our work demonstrates that long-term evolution of complex gene regulatory networks in a changing environment can lead to a striking increase in the efficiency of generating beneficial mutations. We show that the population evolves towards genotype-phenotype mappings that allow for an orchestrated network-wide change in the gene expression pattern, requiring only a few specific gene indels. The genes involved are hubs of the networks, or directly influencing the hubs. Moreover, throughout the evolutionary trajectory the networks maintain their mutational robustness. In other words, evolution in an alternating environment leads to a network that is sensitive to a small class of beneficial mutations, while the majority of mutations remain neutral: an example of evolution of evolvability.

Probing the Extent of Randomness in Protein Interaction Networks

Joseph Ivanic — 2008-07-11T23:04:22-00:00

PLoS Comput Biol, Vol. 4, No. 7. (11 July 2008), e1000114.

Protein–protein interaction (PPI) networks are commonly explored for the identification of distinctive biological traits, such as pathways, modules, and functional motifs. In this respect, understanding the underlying network structure is vital to assess the significance of any discovered features. We recently demonstrated that PPI networks show degree-weighted behavior, whereby the probability of interaction between two proteins is generally proportional to the product of their numbers of interacting partners or degrees. It was surmised that degree-weighted behavior is a characteristic of randomness. We expand upon these findings by developing a random, degree-weighted, network model and show that eight PPI networks determined from single high-throughput (HT) experiments have global and local properties that are consistent with this model. The apparent random connectivity in HT PPI networks is counter-intuitive with respect to their observed degree distributions; however, we resolve this discrepancy by introducing a non-network-based model for the evolution of protein degrees or “binding affinities.” This mechanism is based on duplication and random mutation, for which the degree distribution converges to a steady state that is identical to one obtained by averaging over the eight HT PPI networks. The results imply that the degrees and connectivities incorporated in HT PPI networks are characteristic of unbiased interactions between proteins that have varying individual binding affinities. These findings corroborate the observation that curated and high-confidence PPI networks are distinct from HT PPI networks and not consistent with a random connectivity. These results provide an avenue to discern indiscriminate organizations in biological networks and suggest caution in the analysis of curated and high-confidence networks.

Unraveling Protein Networks with Power Graph Analysis

Loïc Royer — 2008-07-11T23:03:28-00:00

PLoS Comput Biol, Vol. 4, No. 7. (11 July 2008), e1000108.

Networks play a crucial role in computational biology, yet their analysis and representation is still an open problem. Power Graph Analysis is a lossless transformation of biological networks into a compact, less redundant representation, exploiting the abundance of cliques and bicliques as elementary topological motifs. We demonstrate with five examples the advantages of Power Graph Analysis. Investigating protein-protein interaction networks, we show how the catalytic subunits of the casein kinase II complex are distinguishable from the regulatory subunits, how interaction profiles and sequence phylogeny of SH3 domains correlate, and how false positive interactions among high-throughput interactions are spotted. Additionally, we demonstrate the generality of Power Graph Analysis by applying it to two other types of networks. We show how power graphs induce a clustering of both transcription factors and target genes in bipartite transcription networks, and how the erosion of a phosphatase domain in type 22 non-receptor tyrosine phosphatases is detected. We apply Power Graph Analysis to high-throughput protein interaction networks and show that up to 85% (56% on average) of the information is redundant. Experimental networks are more compressible than rewired ones of same degree distribution, indicating that experimental networks are rich in cliques and bicliques. Power Graphs are a novel representation of networks, which reduces network complexity by explicitly representing re-occurring network motifs. Power Graphs compress up to 85% of the edges in protein interaction networks and are applicable to all types of networks such as protein interactions, regulatory networks, or homology networks.

[duplicate] Local Function Conservation in Sequence and Structure Space

Nils Weinhold — 2008-07-07T22:26:46-00:00

PLoS Comput Biol, Vol. 4, No. 7. (4 July 2008), e1000105.

We assess the variability of protein function in protein sequence and structure space. Various regions in this space exhibit considerable difference in the local conservation of molecular function. We analyze and capture local function conservation by means of logistic curves. Based on this analysis, we propose a method for predicting molecular function of a query protein with known structure but unknown function. The prediction method is rigorously assessed and compared with a previously published function predictor. Furthermore, we apply the method to 500 functionally unannotated PDB structures and discuss selected examples. The proposed approach provides a simple yet consistent statistical model for the complex relations between protein sequence, structure, and function. The GOdot method is available online (http://godot.bioinf.mpi-inf.mpg.de).

Local Function Conservation in Sequence and Structure Space

Nils Weinhold — 2008-07-07T08:38:23-00:00

Quantitative Predictions of Peptide Binding to Any HLA-DR Molecule of Known Sequence: NetMHCIIpan

Morten Nielsen — 2008-07-07T22:07:55-00:00

PLoS Comput Biol, Vol. 4, No. 7. (4 July 2008), e1000107.

CD4 positive T helper cells control many aspects of specific immunity. These cells are specific for peptides derived from protein antigens and presented by molecules of the extremely polymorphic major histocompatibility complex (MHC) class II system. The identification of peptides that bind to MHC class II molecules is therefore of pivotal importance for rational discovery of immune epitopes. HLA-DR is a prominent example of a human MHC class II. Here, we present a method, NetMHCIIpan, that allows for pan-specific predictions of peptide binding to any HLA-DR molecule of known sequence. The method is derived from a large compilation of quantitative HLA-DR binding events covering 14 of the more than 500 known HLA-DR alleles. Taking both peptide and HLA sequence information into account, the method can generalize and predict peptide binding also for HLA-DR molecules where experimental data is absent. Validation of the method includes identification of endogenously derived HLA class II ligands, cross-validation, leave-one-molecule-out, and binding motif identification for hitherto uncharacterized HLA-DR molecules. The validation shows that the method can successfully predict binding for HLA-DR molecules—even in the absence of specific data for the particular molecule in question. Moreover, when compared to TEPITOPE, currently the only other publicly available prediction method aiming at providing broad HLA-DR allelic coverage, NetMHCIIpan performs equivalently for alleles included in the training of TEPITOPE while outperforming TEPITOPE on novel alleles. We propose that the method can be used to identify those hitherto uncharacterized alleles, which should be addressed experimentally in future updates of the method to cover the polymorphism of HLA-DR most efficiently. We thus conclude that the presented method meets the challenge of keeping up with the MHC polymorphism discovery rate and that it can be used to sample the MHC “space,” enabling a highly efficient iterative process for improving MHC class II binding predictions.

Colored extrinsic fluctuations and stochastic gene expression

Vahid Shahrezaei — 2008-05-06T20:09:01-00:00

Mol Syst Biol, Vol. 4 (6 May 2008)

Recursive construction of perfect DNA molecules from imperfect oligonucleotides.

G Linshiz — 2008-05-13T08:13:38-00:00

Molecular systems biology, Vol. 4 (2008)

Making faultless complex objects from potentially faulty building blocks is a fundamental challenge in computer engineering, nanotechnology and synthetic biology. Here, we show for the first time how recursion can be used to address this challenge and demonstrate a recursive procedure that constructs error-free DNA molecules and their libraries from error-prone oligonucleotides. Divide and Conquer (D&C), the quintessential recursive problem-solving technique, is applied in silico to divide the target DNA sequence into overlapping oligonucleotides short enough to be synthesized directly, albeit with errors; error-prone oligonucleotides are recursively combined in vitro, forming error-prone DNA molecules; error-free fragments of these molecules are then identified, extracted and used as new, typically longer and more accurate, inputs to another iteration of the recursive construction procedure; the entire process repeats until an error-free target molecule is formed. Our recursive construction procedure surpasses existing methods for de novo DNA synthesis in speed, precision, amenability to automation, ease of combining synthetic and natural DNA fragments, and ability to construct designer DNA libraries. It thus provides a novel and robust foundation for the design and construction of synthetic biological molecules and organisms.

Recurrent design patterns in the feedback regulation of the mammalian signalling network

Stefan Legewie — 2008-05-07T15:02:04-00:00

Mol Syst Biol, Vol. 4 (6 May 2008)

Large-scale phosphorylation mapping reveals the extent of tyrosine phosphorylation in Arabidopsis

Naoyuki Sugiyama — 2008-05-06T22:38:46-00:00

Mol Syst Biol, Vol. 4 (6 May 2008)

Intronic Alternative Splicing Regulators Identified by Comparative Genomics in Nematodes

Jennifer Kabat — 2008-06-30T13:44:16-00:00

PLoS Comput Biol, Vol. 2, No. 7. (14 July 2006), e86.

Many alternative splicing events are regulated by pentameric and hexameric intronic sequences that serve as binding sites for splicing regulatory factors. We hypothesized that intronic elements that regulate alternative splicing are under selective pressure for evolutionary conservation. Using a Wobble Aware Bulk Aligner genomic alignment of Caenorhabditis elegans and Caenorhabditis briggsae, we identified 147 alternatively spliced cassette exons that exhibit short regions of high nucleotide conservation in the introns flanking the alternative exon. In vivo experiments on the alternatively spliced let-2 gene confirm that these conserved regions can be important for alternative splicing regulation. Conserved intronic element sequences were collected into a dataset and the occurrence of each pentamer and hexamer motif was counted. We compared the frequency of pentamers and hexamers in the conserved intronic elements to a dataset of all C. elegans intron sequences in order to identify short intronic motifs that are more likely to be associated with alternative splicing. High-scoring motifs were examined for upstream or downstream preferences in introns surrounding alternative exons. Many of the high- scoring nematode pentamer and hexamer motifs correspond to known mammalian splicing regulatory sequences, such as (T)GCATG, indicating that the mechanism of alternative splicing regulation is well conserved in metazoans. A comparison of the analysis of the conserved intronic elements, and analysis of the entire introns flanking these same exons, reveals that focusing on intronic conservation can increase the sensitivity of detecting putative splicing regulatory motifs. This approach also identified novel sequences whose role in splicing is under investigation and has allowed us to take a step forward in defining a catalog of splicing regulatory elements for an organism. In vivo experiments confirm that one novel high-scoring sequence from our analysis, (T)CTATC, is important for alternative splicing regulation of the unc-52 gene.

Transcription in Mycoplasma pneumoniae.

J Weiner — 2008-06-23T02:49:08-00:00

Nucleic acids research, Vol. 28, No. 22. (15 November 2000), pp. 4488-4496.

Very little is understood of the structure of mycoplasma promoters, and this limits interpretation of genomic sequence data in these species. In this study the transcriptional start points of 22 genes of Mycoplasma pneumoniae were identified and the regions 5' to the start point compared. Although a strong consensus -10 region could be seen, there was only a weak consensus in the -35 region. A high proportion of transcripts had heterogeneous 5'-ends and characterisation of the sequence of the 5'-ends of two transcripts established that the heterogeneity was derived from initiation of transcription at reduced levels between 1 and 4 bases 5' to the major starting point. In addition to this apparently unique feature, a high proportion of transcripts lacked a 5' untranslated leader region that could contain a ribosomal binding site. Such leaderless transcripts are seen rarely in other bacterial species. Although the promoter regions for a number of members of lipoprotein multigene families were examined, no obvious explanation for regulation of expression was apparent. Using the data from this study an improved matrix for prediction of M.pneumoniae promoters was derived. Application of this matrix to the sequences immediately 3' and 5' to each predicted start codon in the genome suggested that most M. pneumoniae transcriptional start points were likely to occur between 5 and 30 bases 5' to the start codon.

Regulation of Signal Duration and the Statistical Dynamics of Kinase Activation by Scaffold Proteins

Jason Locasale — 2008-06-27T19:10:47-00:00

PLoS Comput Biol, Vol. 4, No. 6. (27 June 2008), e1000099.

Scaffolding proteins that direct the assembly of multiple kinases into a spatially localized signaling complex are often essential for the maintenance of an appropriate biological response. Although scaffolds are widely believed to have dramatic effects on the dynamics of signal propagation, the mechanisms that underlie these consequences are not well understood. Here, Monte Carlo simulations of a model kinase cascade are used to investigate how the temporal characteristics of signaling cascades can be influenced by the presence of scaffold proteins. Specifically, we examine the effects of spatially localizing kinase components on a scaffold on signaling dynamics. The simulations indicate that a major effect that scaffolds exert on the dynamics of cell signaling is to control how the activation of protein kinases is distributed over time. Scaffolds can influence the timing of kinase activation by allowing for kinases to become activated over a broad range of times, thus allowing for signaling at both early and late times. Scaffold concentrations that result in optimal signal amplitude also result in the broadest distributions of times over which kinases are activated. These calculations provide insights into one mechanism that describes how the duration of a signal can potentially be regulated in a scaffold mediated protein kinase cascade. Our results illustrate another complexity in the broad array of control properties that emerge from the physical effects of spatially localizing components of kinase cascades on scaffold proteins.

Why are

Vladimir Uversky — 2008-03-19T08:50:49-00:00

Protein folding: Chaperone embrace

Francesca Cesari — 2008-06-24T05:43:35-00:00

Nature Reviews Molecular Cell Biology, Vol. 9, No. 7. (18 June 2008), pp. 497-497.

Alternative splicing and genome complexity.

D Brett — 2005-11-18T09:17:22-00:00

Nat Genet, Vol. 30, No. 1. (January 2002), pp. 29-30.

Alternative splicing of mRNA allows many gene products with different functions to be produced from a single coding sequence. It has recently been proposed as a mechanism by which higher-order diversity is generated. Here we show, using large-scale expressed sequence tag (EST) analysis, that among seven different eukaryotes the amount of alternative splicing is comparable, with no large differences between humans and other animals.

Global variation in copy number in the human genome

Richard Redon — 2006-11-22T18:14:00-00:00

Nature, Vol. 444, No. 7118. (23 November 2006), pp. 444-454.

Large-Scale Copy Number Polymorphism in the Human Genome

Jonathan Sebat — 2005-03-01T18:53:00-00:00

Science, Vol. 305, No. 5683. (23 July 2004), pp. 525-528.

The extent to which large duplications and deletions contribute to human genetic variation and diversity is unknown. Here, we show that large-scale copy number polymorphisms (CNPs) (about 100 kilobases and greater) contribute substantially to genomic variation between normal humans. Representational oligonucleotide microarray analysis of 20 individuals revealed a total of 221 copy number differences representing 76 unique CNPs. On average, individuals differed by 11 CNPs, and the average length of a CNP interval was 465 kilobases. We observed copy number variation of 70 different genes within CNP intervals, including genes involved in neurological function, regulation of cell growth, regulation of metabolism, and several genes known to be associated with disease.

Detection of large-scale variation in the human genome.

AJ Iafrate — 2006-09-11T16:13:20-00:00

Nat Genet, Vol. 36, No. 9. (September 2004), pp. 949-951.

We identified 255 loci across the human genome that contain genomic imbalances among unrelated individuals. Twenty-four variants are present in > 10% of the individuals that we examined. Half of these regions overlap with genes, and many coincide with segmental duplications or gaps in the human genome assembly. This previously unappreciated heterogeneity may underlie certain human phenotypic variation and susceptibility to disease and argues for a more dynamic human genome structure.

A Coarse-Grained Biophysical Model of E. coli and Its Application to Perturbation of the rRNA Operon Copy Number

Arbel Tadmor — 2008-06-23T16:29:50-00:00

PLoS Comput Biol, Vol. 4, No. 5. (2 May 2008), e1000038.

We propose a biophysical model of Escherichia coli that predicts growth rate and an effective cellular composition from an effective, coarse-grained representation of its genome. We assume that E. coli is in a state of balanced exponential steady-state growth, growing in a temporally and spatially constant environment, rich in resources. We apply this model to a series of past measurements, where the growth rate and rRNA-to-protein ratio have been measured for seven E. coli strains with an rRNA operon copy number ranging from one to seven (the wild-type copy number). These experiments show that growth rate markedly decreases for strains with fewer than six copies. Using the model, we were able to reproduce these measurements. We show that the model that best fits these data suggests that the volume fraction of macromolecules inside E. coli is not fixed when the rRNA operon copy number is varied. Moreover, the model predicts that increasing the copy number beyond seven results in a cytoplasm densely packed with ribosomes and proteins. Assuming that under such overcrowded conditions prolonged diffusion times tend to weaken binding affinities, the model predicts that growth rate will not increase substantially beyond the wild-type growth rate, as indicated by other experiments. Our model therefore suggests that changing the rRNA operon copy number of wild-type E. coli cells growing in a constant rich environment does not substantially increase their growth rate. Other observations regarding strains with an altered rRNA operon copy number, such as nucleoid compaction and the rRNA operon feedback response, appear to be qualitatively consistent with this model. In addition, we discuss possible design principles suggested by the model and propose further experiments to test its validity.

Discovering sequence motifs with arbitrary insertions and deletions.

MC Frith — 2008-05-08T14:33:21-00:00

PLoS computational biology, Vol. 4, No. 4. (April 2008)

BIOLOGY IS ENCODED IN MOLECULAR SEQUENCES: deciphering this encoding remains a grand scientific challenge. Functional regions of DNA, RNA, and protein sequences often exhibit characteristic but subtle motifs; thus, computational discovery of motifs in sequences is a fundamental and much-studied problem. However, most current algorithms do not allow for insertions or deletions (indels) within motifs, and the few that do have other limitations. We present a method, GLAM2 (Gapped Local Alignment of Motifs), for discovering motifs allowing indels in a fully general manner, and a companion method GLAM2SCAN for searching sequence databases using such motifs. glam2 is a generalization of the gapless Gibbs sampling algorithm. It re-discovers variable-width protein motifs from the PROSITE database significantly more accurately than the alternative methods PRATT and SAM-T2K. Furthermore, it usefully refines protein motifs from the ELM database: in some cases, the refined motifs make orders of magnitude fewer overpredictions than the original ELM regular expressions. GLAM2 performs respectably on the BAliBASE multiple alignment benchmark, and may be superior to leading multiple alignment methods for "motif-like" alignments with N- and C-terminal extensions. Finally, we demonstrate the use of GLAM2 to discover protein kinase substrate motifs and a gapped DNA motif for the LIM-only transcriptional regulatory complex: using GLAM2SCAN, we identify promising targets for the latter. GLAM2 is especially promising for short protein motifs, and it should improve our ability to identify the protein cleavage sites, interaction sites, post-translational modification attachment sites, etc., that underlie much of biology. It may be equally useful for arbitrarily gapped motifs in DNA and RNA, although fewer examples of such motifs are known at present. GLAM2 is public domain software, available for download at http://bioinformatics.org.au/glam2.

The Energy Landscapes of Repeat-Containing Proteins: Topology, Cooperativity, and the Folding Funnels of One-Dimensional Architectures

Diego Ferreiro — 2008-06-23T16:29:21-00:00

PLoS Comput Biol, Vol. 4, No. 5. (16 May 2008), e1000070.

Repeat-proteins are made up of near repetitions of 20– to 40–amino acid stretches. These polypeptides usually fold up into non-globular, elongated architectures that are stabilized by the interactions within each repeat and those between adjacent repeats, but that lack contacts between residues distant in sequence. The inherent symmetries both in primary sequence and three-dimensional structure are reflected in a folding landscape that may be analyzed as a quasi–one-dimensional problem. We present a general description of repeat-protein energy landscapes based on a formal Ising-like treatment of the elementary interaction energetics in and between foldons, whose collective ensemble are treated as spin variables. The overall folding properties of a complete “domain” (the stability and cooperativity of the repeating array) can be derived from this microscopic description. The one-dimensional nature of the model implies there are simple relations for the experimental observables: folding free-energy (ΔGwater) and the cooperativity of denaturation (m-value), which do not ordinarily apply for globular proteins. We show how the parameters for the “coarse-grained” description in terms of foldon spin variables can be extracted from more detailed folding simulations on perfectly funneled landscapes. To illustrate the ideas, we present a case-study of a family of tetratricopeptide (TPR) repeat proteins and quantitatively relate the results to the experimentally observed folding transitions. Based on the dramatic effect that single point mutations exert on the experimentally observed folding behavior, we speculate that natural repeat proteins are “poised” at particular ratios of inter- and intra-element interaction energetics that allow them to readily undergo structural transitions in physiologically relevant conditions, which may be intrinsically related to their biological functions.

Sequence Similarity Network Reveals Common Ancestry of Multidomain Proteins

Nan Song — 2008-06-18T13:54:41-00:00

PLoS Comput Biol, Vol. 4, No. 5. (16 May 2008), e1000063.

We address the problem of homology identification in complex multidomain families with varied domain architectures. The challenge is to distinguish sequence pairs that share common ancestry from pairs that share an inserted domain but are otherwise unrelated. This distinction is essential for accuracy in gene annotation, function prediction, and comparative genomics. There are two major obstacles to multidomain homology identification: lack of a formal definition and lack of curated benchmarks for evaluating the performance of new methods. We offer preliminary solutions to both problems: 1) an extension of the traditional model of homology to include domain insertions; and 2) a manually curated benchmark of well-studied families in mouse and human. We further present Neighborhood Correlation, a novel method that exploits the local structure of the sequence similarity network to identify homologs with great accuracy based on the observation that gene duplication and domain shuffling leave distinct patterns in the sequence similarity network. In a rigorous, empirical comparison using our curated data, Neighborhood Correlation outperforms sequence similarity, alignment length, and domain architecture comparison. Neighborhood Correlation is well suited for automated, genome-scale analyses. It is easy to compute, does not require explicit knowledge of domain architecture, and classifies both single and multidomain homologs with high accuracy. Homolog predictions obtained with our method, as well as our manually curated benchmark and a web-based visualization tool for exploratory analysis of the network neighborhood structure, are available at http://www.neighborhoodcorrelation.org. Our work represents a departure from the prevailing view that the concept of homology cannot be applied to genes that have undergone domain shuffling. In contrast to current approaches that either focus on the homology of individual domains or consider only families with identical domain architectures, we show that homology can be rationally defined for multidomain families with diverse architectures by considering the genomic context of the genes that encode them. Our study demonstrates the utility of mining network structure for evolutionary information, suggesting this is a fertile approach for investigating evolutionary processes in the post-genomic era.

Dynamic analysis of integrated signaling, metabolic, and regulatory networks.

J Min Lee — 2008-05-18T17:51:35-00:00

PLoS computational biology, Vol. 4, No. 5. (May 2008)

Extracellular cues affect signaling, metabolic, and regulatory processes to elicit cellular responses. Although intracellular signaling, metabolic, and regulatory networks are highly integrated, previous analyses have largely focused on independent processes (e.g., metabolism) without considering the interplay that exists among them. However, there is evidence that many diseases arise from multifunctional components with roles throughout signaling, metabolic, and regulatory networks. Therefore, in this study, we propose a flux balance analysis (FBA)-based strategy, referred to as integrated dynamic FBA (idFBA), that dynamically simulates cellular phenotypes arising from integrated networks. The idFBA framework requires an integrated stoichiometric reconstruction of signaling, metabolic, and regulatory processes. It assumes quasi-steady-state conditions for "fast" reactions and incorporates "slow" reactions into the stoichiometric formalism in a time-delayed manner. To assess the efficacy of idFBA, we developed a prototypic integrated system comprising signaling, metabolic, and regulatory processes with network features characteristic of actual systems and incorporated kinetic parameters based on typical time scales observed in literature. idFBA was applied to the prototypic system, which was evaluated for different environments and gene regulatory rules. In addition, we applied the idFBA framework in a similar manner to a representative module of the single-cell eukaryotic organism Saccharomyces cerevisiae. Ultimately, idFBA facilitated quantitative, dynamic analysis of systemic effects of extracellular cues on cellular phenotypes and generated comparable time-course predictions when contrasted with an equivalent kinetic model. Since idFBA solves a linear programming problem and does not require an exhaustive list of detailed kinetic parameters, it may be efficiently scaled to integrated intracellular systems that incorporate signaling, metabolic, and regulatory processes at the genome scale, such as the S. cerevisiae system presented here.

Uncovering Interactions in the Frequency Domain

Shuixia Guo — 2008-06-06T15:48:35-00:00

PLoS Comput Biol, Vol. 4, No. 5. (30 May 2008), e1000087.

Oscillatory activity plays a critical role in regulating biological processes at levels ranging from subcellular, cellular, and network to the whole organism, and often involves a large number of interacting elements. We shed light on this issue by introducing a novel approach called partial Granger causality to reliably reveal interaction patterns in multivariate data with exogenous inputs and latent variables in the frequency domain. The method is extensively tested with toy models, and successfully applied to experimental datasets, including (1) gene microarray data of HeLa cell cycle; (2) in vivo multi-electrode array (MEA) local field potentials (LFPs) recorded from the inferotemporal cortex of a sheep; and (3) in vivo LFPs recorded from distributed sites in the right hemisphere of a macaque monkey.

A Probabilistic Model of Local Sequence Alignment That Simplifies Statistical Significance Estimation

Sean Eddy — 2008-06-23T15:55:36-00:00

PLoS Comput Biol, Vol. 4, No. 5. (30 May 2008), e1000069.

Sequence database searches require accurate estimation of the statistical significance of scores. Optimal local sequence alignment scores follow Gumbel distributions, but determining an important parameter of the distribution (λ) requires time-consuming computational simulation. Moreover, optimal alignment scores are less powerful than probabilistic scores that integrate over alignment uncertainty (“Forward” scores), but the expected distribution of Forward scores remains unknown. Here, I conjecture that both expected score distributions have simple, predictable forms when full probabilistic modeling methods are used. For a probabilistic model of local sequence alignment, optimal alignment bit scores (“Viterbi” scores) are Gumbel-distributed with constant λ = log 2, and the high scoring tail of Forward scores is exponential with the same constant λ. Simulation studies support these conjectures over a wide range of profile/sequence comparisons, using 9,318 profile-hidden Markov models from the Pfam database. This enables efficient and accurate determination of expectation values (E-values) for both Viterbi and Forward scores for probabilistic local alignments.

CSMET: Comparative Genomic Motif Detection via Multi-Resolution Phylogenetic Shadowing

Pradipta Ray — 2008-06-07T18:41:30-00:00

PLoS Comput Biol, Vol. 4, No. 6. (6 June 2008), e1000090.

Functional turnover of transcription factor binding sites (TFBSs), such as whole-motif loss or gain, are common events during genome evolution. Conventional probabilistic phylogenetic shadowing methods model the evolution of genomes only at nucleotide level, and lack the ability to capture the evolutionary dynamics of functional turnover of aligned sequence entities. As a result, comparative genomic search of non-conserved motifs across evolutionarily related taxa remains a difficult challenge, especially in higher eukaryotes, where the cis-regulatory regions containing motifs can be long and divergent; existing methods rely heavily on specialized pattern-driven heuristic search or sampling algorithms, which can be difficult to generalize and hard to interpret based on phylogenetic principles. We propose a new method: Conditional Shadowing via Multi-resolution Evolutionary Trees, or CSMET, which uses a context-dependent probabilistic graphical model that allows aligned sites from different taxa in a multiple alignment to be modeled by either a background or an appropriate motif phylogeny conditioning on the functional specifications of each taxon. The functional specifications themselves are the output of a phylogeny which models the evolution not of individual nucleotides, but of the overall functionality (e.g., functional retention or loss) of the aligned sequence segments over lineages. Combining this method with a hidden Markov model that autocorrelates evolutionary rates on successive sites in the genome, CSMET offers a principled way to take into consideration lineage-specific evolution of TFBSs during motif detection, and a readily computable analytical form of the posterior distribution of motifs under TFBS turnover. On both simulated and real Drosophila cis-regulatory modules, CSMET outperforms other state-of-the-art comparative genomic motif finders.

Conformational proofreading: the impact of conformational changes on the specificity of molecular recognition.

Y Savir — 2008-06-04T20:11:10-00:00

PLoS ONE, Vol. 2, No. 5. (2007)

To perform recognition, molecules must locate and specifically bind their targets within a noisy biochemical environment with many look-alikes. Molecular recognition processes, especially the induced-fit mechanism, are known to involve conformational changes. This raises a basic question: Does molecular recognition gain any advantage by such conformational changes? By introducing a simple statistical-mechanics approach, we study the effect of conformation and flexibility on the quality of recognition processes. Our model relates specificity to the conformation of the participant molecules and thus suggests a possible answer: Optimal specificity is achieved when the ligand is slightly off target; that is, a conformational mismatch between the ligand and its main target improves the selectivity of the process. This indicates that deformations upon binding serve as a conformational proofreading mechanism, which may be selected for via evolution.

Parallel techniques for physically based simulation on multi-core processor architectures

Bernhard Thomaszewski — 2008-06-16T08:45:12-00:00

Computers & Graphics, Vol. 32, No. 1. (February 2008), pp. 25-40.

As multi-core processor systems become more and more widespread, the demand for efficient parallel algorithms also propagates into the field of computer graphics. This is especially true for physically based simulation, which is notorious for expensive numerical methods. In this work, we explore possibilities for accelerating physically based simulation algorithms on multi-core architectures. Two components of physically based simulation represent a great potential for bottlenecks in parallelisation: implicit time integration and collision handling. From the parallelisation point of view these two components are substantially different. Implicit time integration can be treated efficiently using static problem decomposition. The linear system arising in this context is solved using a data-parallel preconditioned conjugate gradient algorithm. The collision handling stage, however, requires a different approach, due to its dynamic structure. This stage is handled using multi-threaded programming with fully dynamic task decomposition. In particular, we propose a new task splitting approach based on a reasonable estimation of work, which analyses previous simulation steps. Altogether, the combination of different parallelisation techniques leads to a concise and yet versatile framework for highly efficient physical simulation.

Inferring nonneutral evolution from human-chimp-mouse orthologous gene trios.

AG Clark — 2006-05-24T23:42:14-00:00

Science, Vol. 302, No. 5652. (12 December 2003), pp. 1960-1963.

Even though human and chimpanzee gene sequences are nearly 99% identical, sequence comparisons can nevertheless be highly informative in identifying biologically important changes that have occurred since our ancestral lineages diverged. We analyzed alignments of 7645 chimpanzee gene sequences to their human and mouse orthologs. These three-species sequence alignments allowed us to identify genes undergoing natural selection along the human and chimp lineage by fitting models that include parameters specifying rates of synonymous and nonsynonymous nucleotide substitution. This evolutionary approach revealed an informative set of genes with significantly different patterns of substitution on the human lineage compared with the chimpanzee and mouse lineages. Partitions of genes into inferred biological classes identified accelerated evolution in several functional classes, including olfaction and nuclear transport. In addition to suggesting adaptive physiological differences between chimps and humans, human-accelerated genes are significantly more likely to underlie major known Mendelian disorders.

Comparative conservation analysis of the human mitotic phosphoproteome

Rainer Malik — 2008-04-29T20:32:26-00:00

Bioinformatics (20 April 2008), btn197.

Motivation: A key challenge in phosphoproteomic studies is to distinguish functionally relevant phosphorylation sites from potentially "silent" phosphorylation. Considering that relevant phosphorylation sites are expected to be better conserved during evolution than overall Serine, Threonine, and Tyrosine (S/T/Y) residues, we asked whether this can be directly demonstrated through statistic analysis, using a large experimental dataset. Results: Analyzing phosphoproteomic data derived from the human mitotic spindle apparatus, we found that 95.2 % of 1744 phosphorylation sites are conserved in at least one of six other vertebrate species. Using a new score, termed CZ-Score, we demonstrate that phosphorylation sites are significantly better conserved than other S/T/Y sites, a conclusion validated from several kinase consensus motifs. Most importantly, phosphorylation sites with experimentally verified biological functions were significantly better conserved than other phosphorylation sites, indicating that analysis utilizing evolutionary conservation may constitute a powerful basis for the development of improved phosphorylation site predictors. Contact: malik@biochem.mpg.de 10.1093/bioinformatics/btn197

Positive selection drives a correlation between nonsynonymous/ synonymous divergence and functional divergence.

Jacob A Tennessen — 2008-05-01T10:54:48-00:00

Bioinformatics (Oxford, England) (28 April 2008)

MOTIVATION: Functional divergence among proteins is often assumed to be strongly influenced by natural selection, as inferred from the ratio of nonsynonymous nucleotide divergence (d(N)) to synonymous nucleotide divergence (d(S)). That is, the more a mutation changes protein function, the more likely it is to be either selected against or selectively favored, and because the d(N)/d(S) ratio is a measure of natural selection, this ratio can be used to predict the degree of functional divergence (d(F)). However, these hypotheses have rarely been experimentally tested. RESULTS: I present a novel method to address this issue, and demonstrate that divergence in bacteria-killing activity among animal antimicrobial peptides is positively correlated with the log of the d(N)/d(S) ratio. The primary cause of this pattern appears to be that positively selected substitutions change protein function more than neutral substitutions do. Thus, the d(N)/d(S) ratio is an accurate estimator of adaptive functional divergence. CONTACT: tennessj@science.oregonstate.edu SUPPLEMENTARY INFORMATION: Supplementary data, including GenBank Accession numbers, are available at Bioinformatics Online.

Distinguishing protein-coding and noncoding genes in the human genome

Michele Clamp — 2007-11-26T23:07:17-00:00

Proceedings of the National Academy of Sciences (26 November 2007), 0709013104.

Although the Human Genome Project was completed 4 years ago, the catalog of human protein-coding genes remains a matter of controversy. Current catalogs list a total of approx24,500 putative protein-coding genes. It is broadly suspected that a large fraction of these entries are functionally meaningless ORFs present by chance in RNA transcripts, because they show no evidence of evolutionary conservation with mouse or dog. However, there is currently no scientific justification for excluding ORFs simply because they fail to show evolutionary conservation: the alternative hypothesis is that most of these ORFs are actually valid human genes that reflect gene innovation in the primate lineage or gene loss in the other lineages. Here, we reject this hypothesis by carefully analyzing the nonconserved ORFsspecifically, their properties in other primates. We show that the vast majority of these ORFs are random occurrences. The analysis yields, as a by-product, a major revision of the current human catalogs, cutting the number of protein-coding genes to approx20,500. Specifically, it suggests that nonconserved ORFs should be added to the human gene catalog only if there is clear evidence of an encoded protein. It also provides a principled methodology for evaluating future proposed additions to the human gene catalog. Finally, the results indicate that there has been relatively little true innovation in mammalian protein-coding genes. 10.1073/pnas.0709013104

The MARTINI Coarse-Grained Force Field: Extension to Proteins

Luca Monticelli — 2008-04-16T13:18:43-00:00

J. Chem. Theory Comput. (16 April 2008)

Abstract: Many biologically interesting phenomena occur on a time scale that is too long to be studied by atomistic simulations. These phenomena include the dynamics of large proteins and self-assembly of biological materials. Coarse-grained (CG) molecular modeling allows computer simulations to be run on length and time scales that are 23 orders of magnitude larger compared to atomistic simulations, providing a bridge between the atomistic and the mesoscopic scale. We developed a new CG model for proteins as an extension of the MARTINI force field. Here, we validate the model for its use in peptide-bilayer systems. In order to validate the model, we calculated the potential of mean force for each amino acid as a function of its distance from the center of a dioleoylphosphatidylcholine (DOPC) lipid bilayer. We then compared amino acid association constants, the partitioning of a series of model pentapeptides, the partitioning and orientation of WALP23 in DOPC lipid bilayers and a series of KALP peptides in dimyristoylphosphatidylcholine and dipalmitoylphosphatidylcholine (DPPC) bilayers. A comparison with results obtained from atomistic models shows good agreement in all of the tests performed. We also performed a systematic investigation of the partitioning of five series of polyalanineleucine peptides (with different lengths and compositions) in DPPC bilayers. As expected, the fraction of peptides partitioned at the interface increased with decreasing peptide length and decreasing leucine content, demonstrating that the CG model is capable of discriminating partitioning behavior arising from subtle differences in the amino acid composition. Finally, we simulated the concentration-dependent formation of transmembrane pores by magainin, an antimicrobial peptide. In line with atomistic simulation studies, disordered toroidal pores are formed. In conclusion, the model is computationally efficient and effectively reproduces peptidelipid interactions and the partitioning of amino acids and peptides in lipid bilayers.

Comparative genome assembly.

M Pop — 2007-03-07T04:40:34-00:00

Brief Bioinform, Vol. 5, No. 3. (September 2004), pp. 237-248.

One of the most complex and computationally intensive tasks of genome sequence analysis is genome assembly. Even today, few centres have the resources, in both software and hardware, to assemble a genome from the thousands or millions of individual sequences generated in a whole-genome shotgun sequencing project. With the rapid growth in the number of sequenced genomes has come an increase in the number of organisms for which two or more closely related species have been sequenced. This has created the possibility of building a comparative genome assembly algorithm, which can assemble a newly sequenced genome by mapping it onto a reference genome. We describe here a novel algorithm for comparative genome assembly that can accurately assemble a typical bacterial genome in less than four minutes on a standard desktop computer. The software is available as part of the open-source AMOS project.

PLoS Computational Biology: An Introduction to Bioinformatics for Glycomics Research

2008-06-04T13:12:46-00:00

PLoS Computational Biology: Uncovering Interactions in the Frequency Domain

2008-06-04T13:11:18-00:00

PLoS Computational Biology: A Probabilistic Model of Local Sequence Alignment That Simplifies Statistical Significance Estimation

2008-06-02T08:22:15-00:00

De novo repeat classification and fragment assembly.

PA Pevzner — 2005-01-18T20:02:34-00:00

Genome Res, Vol. 14, No. 9. (September 2004), pp. 1786-1796.

Repetitive sequences make up a significant fraction of almost any genome, and an important and still open question in bioinformatics is how to represent all repeats in DNA sequences. We propose a new approach to repeat classification that represents all repeats in a genome as a mosaic of sub-repeats. Our key algorithmic idea also leads to new approaches to multiple alignment and fragment assembly. In particular, we show that our FragmentGluer assembler improves on Phrap and ARACHNE in assembly of BACs and bacterial genomes.

PLoS Computational Biology: Quasispecies Made Simple

2008-05-21T21:29:50-00:00