Genomic variants influence phenotypes and organismal fitness, with their effects shaped by genomic context. In 3' untranslated regions, variants can alter phenotypes by influencing RNA-protein binding and subsequent post-transcriptional gene regulation. Here, we investigate how indel variants impact RNA-protein interactions from outside the binding site, through changes in RNA secondary structure. Our findings reveal that indels can significantly affect protein binding affinities over distances spanning tens of nucleotides, with longer indels exerting greater effects until saturation. Crucially, we find evidence that this effect is constrained by purifying selection. Naturally observed indel polymorphisms cause smaller changes in binding affinity than synthetic indels, and this signal of selection is more pronounced near HuR binding sites. We also find that the sequence context of HuR binding sites shows greater resilience to indel mutations compared to randomly selected sites. These results demonstrate that indel polymorphisms outside the binding site can modulate RNA-protein interactions through structural effects, and that purifying selection acts to filter out variants that disrupt critical interactions.

MOTIVATION: RNA-binding proteins are fundamental to many cellular processes. Double-stranded RNA-binding proteins (dsRBPs) in particular are crucial for RNA interference, mRNA elongation, A-to-I editing, host defense, splicing and a multitude of other important mechanisms. Since dsRBPs require double-stranded RNA to bind, their binding affinity depends on the competition among all possible secondary structures of the target RNA molecule. Here, we introduce a quantitative model that allows calculation of the effective affinity of dsRBPs to any RNA given a principal affinity and the sequence of the RNA, while fully taking into account the entire secondary structure ensemble of the RNA. RESULTS: We implement our model within the ViennaRNA folding package while maintaining its O(N3) time complexity. We validate our quantitative model by comparing with experimentally determined binding affinities and stoichiometries for transactivation response element RNA-binding protein (TRBP). We also find that the change in dsRBP binding affinity purely due to the presence of alternative RNA structures can be many orders of magnitude and that the predicted affinity of TRBP for pre-miRNA-like constructs correlates with experimentally measured processing rates. AVAILABILITY AND IMPLEMENTATION: Our modified version of the ViennaRNA package is available for download at http://bioserv.mps.ohio-state.edu/dsRBPBind, is free to use for research and educational purposes, and utilizes simple get/set methods for footprint size, concentration, cooperativity, principal dissociation constant and overlap.

Single nucleotide polymorphisms are widely associated with disease, but the ways in which they cause altered phenotypes are often unclear, especially when they appear in non-coding regions. One way in which non-coding polymorphisms could cause disease is by affecting crucial RNA-protein interactions. While it is clear that changing a protein binding motif will alter protein binding, it has been shown that single nucleotide polymorphisms can affect RNA secondary structure, and here we show that single nucleotide polymorphisms can affect RNA-protein interactions from outside binding motifs through altered RNA secondary structure. By using a modified version of the Vienna Package and PAR-CLIP data for HuR (ELAVL1) in humans we characterize the genome-wide effect of single nucleotide polymorphisms on HuR binding and show that they can have a many-fold effect on the affinity of HuR binding to RNA transcripts from tens of bases away. We also find some evidence that the effect of single nucleotide polymorphisms on protein binding might be under selection, with the non-reference alleles tending to make it harder for a protein to bind.

MOTIVATION: Ribosome profiling has been widely used to study translation in a genome-wide fashion. It requires deep sequencing of ribosome protected mRNA fragments followed by mapping of fragments to the reference genome. For applications such as identification of ribosome pausing sites, it is not enough to map a fragment to a given gene, but the exact position of the ribosome represented by the fragment must be identified for each mRNA fragment. The assignment of the correct ribosome position is complicated by the broad length distribution of the ribosome protected fragments caused by the known sequence bias of micrococcal nuclease (MNase), the most widely used nuclease for digesting mRNAs in bacteria. Available mapping algorithms suffer from either MNase bias or low accuracy in characterizing the ribosome pausing kinetics. RESULTS: In this paper, we introduce a new computational method for mapping the ribosome protected fragments to ribosome locations. We first develop a mathematical model of the interplay between MNase digestion and ribosome protection of the mRNAs. We then use the model to reconstruct the ribosome occupancy profile on a per gene level. We demonstrate that our method has the capability of mitigating the sequence bias introduced by MNase and accurately locating ribosome pausing sites at codon resolution. We believe that our method can be broadly applied to ribosome profiling studies on bacteria where codon resolution is necessary. AVAILABILITY AND IMPLEMENTATION: Source code implementing our approach can be downloaded under GPL3 license at http://bioserv.mps.ohio-state.edu/RiboProP. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Protein pulldown using Methyl-CpG binding domain (MBD) proteins followed by high-throughput sequencing is a common method to determine DNA methylation. Algorithms have been developed to estimate absolute methylation level from read coverage generated by affinity enrichment-based techniques, but the most accurate one for MBD-seq data requires additional data from an SssI-treated Control experiment. RESULTS: Using our previous characterizations of Methyl-CpG/MBD2 binding in the context of an MBD pulldown experiment, we build a model of expected MBD pulldown reads as drawn from SssI-treated DNA. We use the program BayMeth to evaluate the effectiveness of this model by substituting calculated SssI Control data for the observed SssI Control data. By comparing methylation predictions against those from an RRBS data set, we find that BayMeth run with our modeled SssI Control data performs better than BayMeth run with observed SssI Control data, on both 100 bp and 10 bp windows. Adapting the model to an external data set solely by changing the average fragment length, our calculated data still informs the BayMeth program to a similar level as observed data in predicting methylation state on a pulldown data set with matching WGBS estimates. CONCLUSION: In both internal and external MBD pulldown data sets tested in this study, BayMeth used with our modeled pulldown coverage performs better than BayMeth run without the inclusion of any estimate of SssI Control pulldown, and is comparable to - and in some cases better than - using observed SssI Control data with the BayMeth program. Thus, our MBD pulldown alignment model can improve methylation predictions without the need to perform additional control experiments.

DNA methylation is a well-established epigenetic mark, whose pattern throughout the genome, especially in the promoter or CpG islands, may be modified in a cell at a disease stage. Recently developed probabilistic approaches allow distributing methylation signals at nucleotide resolution from MethylCap-seq data. Standard statistical methods for detecting differential methylation suffer from 'curse of dimensionality' and sparsity in signals, resulting in high false-positive rates. Strong correlation of signals between CG sites also yields spurious results. In this article, we review applicability of high-dimensional mean vector tests for detection of differentially methylated regions (DMRs) and compare and contrast such tests with other methods for detecting DMRs. Comprehensive simulation studies are conducted to highlight the performance of these tests under different settings. Based on our observation, we make recommendations on the optimal test to use. We illustrate the superiority of mean vector tests in detecting cancer-related canonical gene pathways, which are significantly enriched for acute myeloid leukemia and ovarian cancer.

Abstract Motivation : DNA methylation is an epigenetic change occurring in genomic CpG sequences that contribute to the regulation of gene transcription both in normal and malignant cells. Next-generation sequencing has been used to characterize DNA methylation status at the genome scale, but suffers from high sequencing cost in the case of whole-genome bisulfite sequencing, or from reduced resolution (inability to precisely define which of the CpGs are methylated) with capture-based techniques. Results : Here we present a computational method that computes nucleotide-resolution methylation values from capture-based data by incorporating fragment length profiles into a model of methylation analysis. We demonstrate that it compares favorably with nucleotide-resolution bisulfite sequencing and has better predictive power with respect to a reference than window-based methods, often used for enrichment data. The described method was used to produce the methylation data used in tandem with gene expression to produce a novel and clinically significant gene signature in acute myeloid leukemia. In addition, we introduce a complementary statistical method that uses this nucleotide-resolution methylation data for detection of differentially methylated features. Availability : Software in the form of Python and R scripts is available at http://bioserv.mps.ohio-state.edu/ premer and is free for non-commercial use. Contact : [email protected] ; [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

RNA editing describes the process in which individual or short stretches of nucleotides in a messenger or structural RNA are inserted, deleted, or substituted. A high level of RNA editing has been observed in the mitochondrial genome of Physarum polycephalum. The most frequent editing type in Physarum is the insertion of individual Cs. RNA editing is extremely accurate in Physarum; however, little is known about its mechanism. Here, we demonstrate how analyzing two organisms from the Myxomycetes, namely Physarum polycephalum and Didymium iridis, allows us to test hypotheses about the editing mechanism that can not be tested from a single organism alone. First, we show that using the recently determined full transcriptome information of Physarum dramatically improves the accuracy of computational editing site prediction in Didymium. We use this approach to predict genes in the mitochondrial genome of Didymium and identify six new edited genes as well as one new gene that appears unedited. Next we investigate sequence conservation in the vicinity of editing sites between the two organisms in order to identify sites that harbor the information for the location of editing sites based on increased conservation. Our results imply that the information contained within only nine or ten nucleotides on either side of the editing site (a distance previously suggested through experiments) is not enough to locate the editing sites. Finally, we show that the codon position bias in C insertional RNA editing of these two organisms is correlated with the selection pressure on the respective genes thereby directly testing an evolutionary theory on the origin of this codon bias. Beyond revealing interesting properties of insertional RNA editing in Myxomycetes, our work suggests possible approaches to be used when finding sequence motifs for any biological process fails.

MOTIVATION: Sequence alignment is one of the most popular tools of modern biology. NCBI's PSI-BLAST utilizes iterative model building in order to better detect distant homologs with greater sensitivity than non-iterative BLAST. However, PSI-BLAST's performance is limited by the fact that it relies on deterministic alignments. Using a semi-probabilistic alignment scheme such as Hybrid alignment should allow for better informed model building and improved identification of homologous sequences, particularly remote homologs. RESULTS: We have built a new version of the tool in which the Smith-Waterman alignment algorithm core is replaced by the hybrid alignment algorithm. The favorable statistical properties of the hybrid algorithm allow the introduction of position-specific gap penalties in Hybrid PSI-BLAST. This improves the position-specific modeling of protein families and results in an overall improvement of performance. AVAILABILITY: Source code is freely available for download at http://bioserv.mps.ohio-state.edu/HybridPSI, implemented in C and supported on linux.

MOTIVATION: There are many important proteins which bind single-stranded nucleic acids, such as the nucleocapsid protein in HIV and the RecA DNA repair protein in bacteria. The presence of such proteins can strongly alter the secondary structure of the nucleic acid molecules. Therefore, accurate modeling of the interaction between single-stranded nucleic acids and such proteins is essential to fully understand many biological processes. RESULTS: We develop a model for predicting nucleic acid secondary structure in the presence of single-stranded binding proteins, and implement it as an extension of the Vienna RNA Package. All parameters needed to model nucleic acid secondary structures in the absence of proteins have been previously determined. This leaves the footprint and sequence-dependent binding affinity of the protein as adjustable parameters of our model. Using this model we are able to predict the probability of the protein binding at any position in the nucleic acid sequence, the impact of the protein on nucleic acid base pairing, the end-to-end distance distribution for the nucleic acid and FRET distributions for fluorophores attached to the nucleic acid. AVAILABILITY: Source code for our modified version of the Vienna RNA package is freely available at http://bioserv.mps.ohio-state.edu/Vienna+P, implemented in C and running on Linux.

MOTIVATION: Insertional RNA editing renders gene prediction very difficult compared to organisms without such RNA editing. A case in point is the mitochondrial genome of Physarum polycephalum in which only about one-third of the number of genes that are to be expected given its length are annotated. Thus, gene prediction methods that explicitly take into account insertional editing are needed for successful annotation of such genomes. RESULTS: We annotate the mitochondrial genome of P.polycephalum using several different approaches for gene prediction in organisms with insertional RNA editing. We computationally validate our annotations by comparing the results from different methods against each other and as proof of concept experimentally validate two of the newly predicted genes. We more than double the number of annotated putative genes in this organism and find several intriguing candidate genes that are not expected in a mitochondrial genome. AVAILABILITY: The C source code of the programs described here are available upon request from the corresponding author.

MOTIVATION: The deluge of biological information from different genomic initiatives and the rapid advancement in biotechnologies have made bioinformatics tools an integral part of modern biology. Among the widely used sequence alignment tools, BLAST and PSI-BLAST are arguably the most popular. PSI-BLAST, which uses an iterative profile position specific score matrix (PSSM)-based search strategy, is more sensitive than BLAST in detecting weak homologies, thus making it suitable for remote homolog detection. Many refinements have been made to improve PSI-BLAST, and its computational efficiency and high specificity have been much touted. Nevertheless, corruption of its profile via the incorporation of false positive sequences remains a major challenge. RESULTS: We have developed a simple and elegant approach to resolve the problem of model corruption in PSI-BLAST searches. We hypothesized that combining results from the first (least-corrupted) profile with results from later (most sensitive) iterations of PSI-BLAST provides a better discriminator for true and false hits. Accordingly, we have derived a formula that utilizes the E-values from these two PSI-BLAST iterations to obtain a figure of merit for rank-ordering the hits. Our verification results based on a 'gold-standard' test set indicate that this figure of merit does indeed delineate true positives from false positives better than PSI-BLAST E-values. Perhaps what is most notable about this strategy is that it is simple and straightforward to implement.

We provide two methods for identifying changes in genotype that are correlated with changes in a phenotype implied by phylogenetic trees. The first method, VENN, works when the number of branches over which the change occurred are modest. VENN looks for genetic changes that are completely penetrant with phenotype changes on a tree. The second method, CCTSWEEP, allows for a partial matching between changes in phenotypes and genotypes and provides a score for each change using Maddison's concentrated changes test. The mutations that are highly correlated with phenotypic change can be ranked by score. We use these methods to find SNPs correlated with resistance to Bacillus anthracis in inbred mouse strains. Our findings are consistent with the current biological literature, and also suggest potential novel candidate genes.

PSI-BLAST remains one of the popular tools for searching remote homologs in sequence databases. We recently demonstrated that hybrid alignment can function as the alignment core for PSI-BLAST without loss of sensitivity. Here, we start to exploit the benefits of hybrid alignment. We show that incorporating information about the suboptimal alignments, otherwise ignored in PSI-BLAST, already improves the sensitivity of our enhanced version of PSI-BLAST. More interestingly, we find a set of sequences on which our tool disagrees with the classification given by SCOP. Careful examination points to a possible misclassification in SCOP. Cross-referencing with two other methods of protein structure classification, CATH and DALI, supports this view, indicating that the enriched information from suboptimal alignments is valuable for detecting more weakly homologous sequences.

MOTIVATION: Some organisms edit their messenger RNA resulting in differences between the genomic sequence for a gene and the corresponding messenger RNA sequence. This difference complicates experimental and computational attempts to find and study genes in organisms with RNA editing even if the full genomic sequence is known. Nevertheless, knowledge of these editing sites is crucial for understanding the editing machinery of these organisms. RESULTS: We present a computational technique that predicts the position of editing sites in the genomic sequence. It uses a statistical approach drawing on the protein sequences of related genes and general features of editing sites of the organism. We apply the method to the mitochondrion of the slime mold Physarum polycephalum. It correctly predicts over 90% of the amino acids and over 70% of the editing sites.

Abstract Progressive sequence model refinement by means of iterative searches is an effective technique for high sensitivity database searches and is currently employed in popular tools such as PSI‐BLAST and SAM. Recently, a novel alignment algorithm has been proposed that offers features expected to improve the sensitivity of such iterative approaches, specifically a well‐characterized theory of its statistics even in the presence of position‐specific gap costs. Here, we demonstrate that the new hybrid alignment algorithm is ready to be used as the alignment core of PSI‐BLAST. In addition, we evaluate the accuracy of two proposed approaches to edge effect correction in short sequence alignment statistics that turns out to be one of the crucial issues in developing a hybrid‐alignment based version of PSI‐BLAST. Copyright © 2004 John Wiley & Sons, Ltd.

The score statistics of a recently introduced 'hybrid alignment' algorithm is studied in detail numerically. An extensive survey across the 2216 models of protein domains contained in the Pfam v5.4 database (Bateman et al., Nucleic Acids Res., 28, 263-266, 2000) verifies the theoretical predictions: For the position-specific scoring functions used in the Pfam models, the score statistics of hybrid alignment obey the Gumbel distribution, with the key Gumbel parameter lambda taking on the asymptotic value 1 universally for all models. Thus, the use of hybrid alignment eliminates the time-consuming computer simulations normally needed to assign p-values to alignment scores, freeing the users to experiment with different scoring parameters and functions. The performance of the hybrid algorithm in detecting sequence homology is also studied. For protein sequences from the SCOP database (Murzin et al., J. Mol. Biol., 247, 536-540, 1995) using uniform scoring functions, the performance is found to be comparable to the best of the existing methods. Preliminary results using the PfamA database suggest that the hybrid algorithm achieves similar performance as existing methods for position-specific scoring systems as well. Hybrid alignment is thereby established as a high performance alignment algorithm with well-characterized, universal statistics.

In order to assess the significance of sequence alignments it is crucial to know the distribution of alignment scores of pairs of random sequences. For gapped local alignment it is empirically known that the shape of this distribution is of the Gumbel form. However, the determination of the parameters of this distribution is a computationally very expensive task. We present a new algorithmic approach which allows to estimate the more important of the Gumbel parameters at least five times faster than the traditional methods. Actual runtimes of our algorithm between less than a second and a few minutes on a workstation bring significance estimation into the realm of interactive applications.

A detailed study of the Smith-Waterman alignment algorithm is performed in order to find an analytical approach to the problem of assessing the statistical significance of local alignments with gaps. The significance is shown to be given in terms of an eigenvalue equation which captures the dynamics of the much simpler global alignment algorithm. This eigenvalue equation is then explicitly solved for a simple scoring system and the resulting significance estimations are verified by a comparison to extensive numerical simulations