waashk/dblp huggingface dataset:
faster genome annotation of non-coding rna families without loss of accuracy. non-coding rnas (ncrnas) are functional rna molecules that do not code for proteins. covariance models (cms) are a useful statistical tool to find new members of an ncrna gene family in a large genome database, using both sequence and, importantly, rna secondary structure information. unfortunately, cm searches are slow. this paper shows how to make cms faster while provably sacrificing none of their accuracy. specifically, based on the cm, our software builds a profile hidden markov model (hmm), which filters the genome database. this hmm is a gorous filter i.e., its filtering eliminates only sequences that provably could not be annotated as homologs. the cm is run only on what remains. optimizing the hmm for filtering involves minimizing an exponential objective function with linear inequality constraints. for most known ncrna families, this allows an 8-gigabase database to be scanned in 2-20 days instead of years, and yields new family members missed by other techniques to improve cm speed.
finding approximate tandem repeats in genomic sequences. an efficient algorithm is presented for detecting approximate tandem repeats in genomic sequences. the algorithm is based on a flexible statistical model which allows a wide range of definitions of approximate tandem repeats. the ideas and methods underlying the algorithm are described and examined and its effectiveness on genomic data is demonstrated.
systems biology and malaria. malaria is the cause of significant global morbidity and mortality with 300-500 million cases annually. despite its disease burden relatively little is known about the molecular biology of the pathogen that causes malaria. for example, the completion of the genome sequence of plasmodium falciparum, the species responsible for the most severe form of human malaria revealed that only 35% of the genes code for proteins with an identifiable function. in addition, little is known about how transcription and translation are regulated. the absence of routine genetic tools for studying plasmodium parasites suggests that these numbers are unlikely to change quickly if conventional, serial, biological methods are used to study the parasite. we are using high-density oligonucleotide arrays and informatic methods to study the genome of the malaria parasite with the goals of understanding how expression is regulated, functionally cataloging the genome, discovering allelic variation and identifying new therapeutic targets. we have shown that genes with highly correlated levels and temporal patterns of expression are often involved in similar functions or cellular processes suggesting that expression profiling can be used to rapidly predict function. in addition we find that there is good correlation between protein levels and transcript levels, suggesting that regulation of expression occurs transcriptionally. analysis of whole-genome transcription patterns reveals that the chromosome is organized into regions that are transcriptionally active and transcriptionally silent in the intraerythrocytic stage of the parasite's lifecycle. thus, both the timing and the relative level of transcription in the parasite is organized into position-dependent domains suggesting that transcription may be regulated at least partially at the level of chromatin structure.
protein structure determination using protein threading and sparse nmr data (extended abstract). it is well known that the nmr method for protein structure determination applies to small proteins and that its effectiveness decreases very rapidly as the molecular weight increases beyond about 30 kd. we have recently developed a method for protein structure determination that can fully utilize partial nmr data as calculation constraints. the core of the method is a threading algorithm that guarantees to find a globally optimal alignment between a query sequence and a template structure, under distance constraints specified by nmr/noe data. our preliminary tests have demonstrated that a small number of nmr/noe distance restraints can significantly improve threading performance in both fold recognition and threading-alignment accuracy, and can possibly extend threading's scope of applicability from structural homologs to structural analogs. an accurate backbone structure generated by nmr-constrained threading can then provide a significant amount of structural information, equivalent to that provided by the nmr method with many nmr/noe restraints; and hence can greatly reduce the amount of nmr data typically required for accurate structure determination. our prelimenary study suggest that a small number of noe restraints may suffice to determine adequately the all-atom structure when those restraints are incorporated in a procedure combining threading, modeling of loops and sidechains, and molecular dynamics simulation. potentially, this new technique can expand nmr's capability to larger proteins.
physical network models and multi-source data integration. we develop a new framework for inferring models of transcriptional regulation. the models in this approach, which we call physical models, are constructed on the basis of verifiable molecular attributes of the underlying biological system. the attributes include, for example, the existence of protein-protein and protein-dna interactions in gene regulatory processes, the directionality of signal transduction in protein-protein interactions, as well as the signs of the immediate effects of these interactions (e.g., whether an upstream gen activates or represses the downstream genes). each attribute is included as a variable in the model, and the variables define a collection of annotated random graphs. possible configurations of these variables (realizations of the underlying biological system) are constrained by the available data sources. some of the data sources such as factor-binding data (location data) involve measurements that are directly tied to the variables in the model. other sources such as gene knock-outs are functional in nature and provide only indirect evidence about the (physical) variables. we associate each knock-out effect in the deletion mutant data with a set of causal paths (molecular cascades) that could in principle explain the effect, resulting in aggregate constraints about the physical variables in the model. the most likely setting of all the variables is found by the max-product algorithm. by testing our approach on datasets related to the pheromone response pathway in s. cerevisiae, we demonstrate that the resulting transcriptional models are consistent with previous studies about the pathway. moreover, we show that the approach is capable of predicting gene knock-out effects with high degree of accuracy in a cross-validation setting. the method also implicates likely molecular cascades responsible for each observed knock-out effect. the inference results are robust against variations in the model parameters. we can extend the approach to include other data sources such as time course expression profiles. we also discuss coordinated regulation and the use of automated experiment design
maximum entropy modeling of short sequence motifs with applications to rna splicing signals. we propose a framework for modeling sequence motifs based on the maximum entropy principle (mep).we recommend approximating short sequence motif distributions with the maximum entropy distribution (med) consistent with low-order marginal constraints estimated from available data, which may include dependencies between non-adjacent as well as adjacent positions.finally, we suggest mechanistically-motivated ways of comparing models.
a unified sequence-structure classification of protein sequences: combining sequence and structure in a map of the protein space. we analyze all known protein sequences in search for a global map of protein space that is consistent in terms of both sequence and structure. our goal is to define clusters of homologous protein domains, beyond those detected by sequence-based methods alone, and then to build a three-dimensional (3d) model for each of the sequences that are homologous to sequences of known 3d structure. this analysis uses both sequence and structure based metrics in the analysis of all protein sequences in a non-redundant (nr) database, comprising all major sequence databases. the analysis starts from the sequences of the scop database domains, which have known three-dimensional structures these sequences are clustered first into families based on sequence similarity alone, without incorporating any information from the scop classification. each sequence-based family is represented by a profile, and this profile is used to search the nr database, using psi-blast. since psi-blast can lead to false similarities, several different indices of validity are used to control the procedure each of the detected sequences is marked and a profile is built for the whole cluster of similar sequences. a 3d model is then built for each sequence in the cluster using an alignment made using the profile as well as the known structures of the scop representatives in the cluster clusters based on scop domains are called type-i clusters in all we find 1421 type-i clusters with total of 168,431 sequences (44.5% of our nr database) after all members of type-i clusters have been marked, we analyze the remaining sequences. the psi-blast procedure is applied repeatedly, each time with a different query, to search what is left over from the previous run. this give type-ii clusters, which may overlap. type-i and type-ii clusters are then grouped using higher level measures of similarity. those pairs of clusters that contain the same common protein (significant overlap in membership), are marked first. the pairs of clusters are then compared using either a structure metric (when 3d structures are known) or a novel sequence profile metric, and clustered into superfamilies and &ldquo;fold&rdquo; families. this analysis avoids the limitation of classifications that are based just on sequence comparison, and allows us to construct a 3d model for a substantial portion of the sequences in the nr database.
a simple iterative approach to parameter optimization. various bioinformatics problems require optimizing several different properties simultaneously. for example, in the protein threading problem, a linear scoring function combines the values for different properties of possible sequence-to-structure alignments into a single score to allow for unambigous optimization. in this context, an essential question is how each property should be weighted. as the native structures are known for some sequences, the implied partial ordering on optimal alignments may be used to adjust the weights. to resolve the arising interdependence of weights and computed solutions, we propose a novel approach: iterating the computation of solutions (here: threading alignments) given the weights and the estimation of optimal weights of the scoring function given these solutions via a systematic calibration method. we show that this procedure converges to structurally meaningful weights, that also lead to significantly improved performance on comprehensive test data sets as measured in different ways. the latter indicates that the performance of threading can be improved in general.
dynamic programming algorithms for haplotype block partitioning: applications to human chromosome 21 haplotype data. recent studies have shown that the human genome has a haplotype block structure such that it can be divided into discrete blocks of limited haplotype diversity. patil et al. [6] and zhang et al. [12] developed algorithms to partition haplotypes into blocks with minimum number of tag snps for the entire chromosome. however, it is not clear how to partition haplotypes into blocks with restricted number of snps when only limited resources are available. in this paper, we first formulated this problem as finding a block partition with a fixed number of tag snps that can cover the maximal percentage of a genome. then we solved it by two dynamic programming algorithms, which are fairly flexible to take into account the knowledge of functional polymorphism. we applied our algorithms to the published snp data of human chromosome 21 combining with the functional information of these snps and demonstrated the effectiveness of them. statistical investigation of the relationship between the starting points of a block partition and the coding and non-coding regions illuminated that the snps at these starting points are not significantly enriched in coding regions. we also developed an efficient algorithm to find all possible long local maximal haplotypes across a subset of samples. after applying this algorithm to the human chromosome 21 haplotype data, we found that samples with long local haplotypes are not necessarily globally similar.
finding short dna motifs using permuted markov models. many short dna motifs such as transcription factor binding sites (tfbs) and splice sites exhibit strong local as well as non-local dependence. we introduce permuted variable length markov models (pvlmm) which could capture the potentially important dependencies among positions, and apply them to the problem of detecting splice and tfb sites. they have been satisfactory from the viewpoint of prediction performance, and also give ready biological interpretations of the sequence dependence observed. the issue of model selection is also studied.
microarrays: how many do you need? we estimate the number of microarrays that is required in order to gain reliable results from a common type of study: the pairwise comparison of different classes of samples. current knowlegde seems to suffice for the construction of models that are realistic with respect to searches for individual differentially expressed genes. such models allow to investigate the dependence of the required number of samples on the relevant parameters: the biological variability of the samples within each class; the fold changes in expression; the detection sensitivity of the microarrays; and the acceptable error rates of the results. we supply experimentalists with general conclusions as well as a freely accessible java applet at http://cartan.gmd.de/~zien/classsize/ for fine tuning simulations to their particular actualities. since the situation can be assumed to be very similar for large scale proteomics and metabolomics studies, our methods and results might also apply there.
support vector training of protein alignment models. sequence to structure alignment is an important step in homology modeling of protein structures. incorporation of features like secondary structure, solvent accessibility, or evolutionary information improve sequence to structure alignment accuracy, but conventional generative estimation techniques for alignment models impose independence assumptions that make these features difficult to include in a principled way. in this paper, we overcome this problem using a support vector machine (svm) method that provides a well-founded way of estimating complex alignment models with hundred-thousands of parameters. furthermore, we show that the method can be trained using a variety of loss functions. in a rigorous empirical evaluation, the svm algorithm outperforms the generative alignment method ssaln, a highly accurate generative alignment model that incorporates structural information. the alignment model learned by the svm aligns 47% of the residues correctly and aligns over 70% of the residues within a shift of 4 positions.
shift-invariant adaptive double threading: learning mhc ii - peptide binding. specificity of mhc binding to short peptide fragments from cellular as well as pathogens' proteins has been found to correlate with disease outcome and pathogen or cancer evolution. the large variation in mhc class ii epitope length has complicated training of predictors for binding affinities compared to mhc class i. in this paper, we treat the relative position of the peptide inside the mhc protein as a hidden variable, and model the ensemble of different binding configurations. the training procedure iterates the predictions with re estimation of the parameters of a binding groove model. we show that the model generalizes to new mhc class ii alleles, which were not a part of the training set. to the best of our knowledge, our technique outperforms all previous approaches to mhc ii epitope prediction. we demonstrate how our model can be used to explain previously documented associations between mhc ii alleles and disease.
improved ranking functions for protein and modification-site identifications. there are a number of computational tools for assigning identifications to peptide tandem mass spectra, but many fewer tools for the crucial next step of integrating spectral identifications into higher-level identifications, such as proteins or modification sites. here we describe a new program called combyne for scoring and ranking higher-level identifications. we compare combyne to existing algorithms on several complex biological samples, including a sample of mouse blood plasma spiked with known concentrations of human proteins. a web interface to our software is at http://bio.parc.xerox.com.
qnet: a tool for querying protein interaction networks. molecular interaction databases can be used to study the evolution of molecular pathways across species. querying such pathways is a challenging computational problem, and recent efforts have been limited to simple queries (paths), or simple networks (forests). in this paper, we significantly extend the class of pathways that can be efficiently queried to the case of trees, and graphs of bounded treewidth. our algorithm allows the identification of non-exact (homeomorphic) matches, exploiting the color coding technique of alon et al. we implement a tool for tree queries, called qnet, and test its retrieval properties in simulations and on real network data. we show that qnet searches queries with up to 9 proteins in seconds on current networks, and outperforms sequence-based searches.we also use qnet to perform the first large scale cross-species comparison of protein complexes, by querying known yeast complexes against a fly protein interaction network. this comparison points to strong conservation between the two species, and underscores the importance of our tool in mining protein interaction networks.
tools for simulating and analyzing rna folding kinetics. it has recently been found that some rna functions are determined by the actual folding kinetics and not just the rna's nucleotide sequence or its native structure. we present new computational tools for simulating and analyzing rna folding kinetic metrics such as population kinetics, folding rates, and the folding of particular subsequences. our method first builds an approximate representation (called a map) of the rna's folding energy landscape, and then uses specialized analysis techniques to extract folding kinetics from the map. we provide a new sampling strategy called probabilistic boltzmann sampling (pbs) that enables us to approximate the folding landscape with much smaller maps, typically by several orders of magnitude. we also describe a new analysis technique, map-based monte carlo (mmc) simulation, to stochastically extract folding pathways from the map. we demonstrate that our technique can be applied to large rna (e.g., 200+ nucleotides), where representing the full landscape is infeasible, and that our tools provide results comparable to other simulation methods that work on complete energy landscapes. we present results showing that our approach computes the same relative functional rates as seen in experiments for the relative plasmid replication rates of cole1 rnaii and its mutants, and for the relative gene expression rates of ms2 phage rna and its mutants.
production-passage-time approximation: a new approximation method to accelerate the simulation process of enzymatic reactions. given the substantial computational requirements of stochastic simulation, approximation is essential for efficient analysis of any realistic biochemical system. this paper introduces a new approximation method to reduce the computational cost of stochastic simulations of an enzymatic reaction scheme which in biochemical systems often includes rapidly changing fast reactions with enzyme and enzyme-substrate complex molecules present in very small counts. our new method removes the substrate dissociation reaction by approximating the passage time of the formation of each enzyme-substrate complex molecule which is destined to a production reaction. this approach skips the firings of unimportant yet expensive reaction events, resulting in a substantial acceleration in the stochastic simulations of enzymatic reactions. additionally, since all the parameters used in our new approach can be derived by the michaelis-menten parameters which can actually be measured from experimental data, applications of this approximation can be practical even without having full knowledge of the underlying enzymatic reaction. furthermore, since our approach does not require a customized simulation procedure for enzymatic reactions, it allows biochemical systems that include such reactions to still take advantage of standard stochastic simulation tools. here, we apply this new method to various enzymatic reaction systems, resulting in a speedup of orders of magnitude in temporal behavior analysis without any significant loss in accuracy.
accounting for non-genetic factors improves the power of eqtl studies. the recent availability of large scale data sets profiling single nucleotide polymorphisms (snps) and gene expression across different human populations, has directed much attention towards discovering patterns of genetic variation and their association with gene regulation. the influence of environmental, developmental and other factors on gene expression can obscure such associations. we present a model that explicitly accounts for non-genetic factors so as to improve significantly the power of an expression quantitative trait loci (eqtl) study. our method also exploits the inherent block structure of haplotype data to further enhance its sensitivity. on data from the hapmap project, we find more than three times as many significant associations than a standard eqtl method.
baycis: a bayesian hierarchical hmm for cis-regulatory module decoding in metazoan genomes. the transcriptional regulatory sequences in metazoan genomes often consist of multiple cis-regulatory modules (crms). each crm contains locally enriched occurrences of binding sites (motifs) for a certain array of regulatory proteins, capable of integrating, amplifying or attenuating multiple regulatory signals via combinatorial interaction with these proteins. the architecture of crm organizations is reminiscent of the grammatical rules underlying a natural language, and presents a particular challenge to computational motif and crm identification in metazoan genomes. in this paper, we present baycis, a bayesian hierarchical hmm that attempts to capture the stochastic syntactic rules of crm organization. under the baycis model, all candidate sites are evaluated based on a posterior probability measure that takes into consideration their similarity to known bss, their contrasts against local genomic context, their first-order dependencies on upstream sequence elements, as well as priors reflecting general knowledge of crm structure. we compare our approach to five existing methods for the discovery of crms, and demonstrate competitive or superior prediction results evaluated against experimentally based annotations on a comprehensive selection of drosophila regulatory regions. the software, database and supplementary materials will be available at http://www.sailing.cs. cmu.edu/baycis.