waashk/dblp huggingface dataset:
bubbles: alternative splicing events of arbitrary dimension in splicing graphs. eukaryotic splicing structures are known to involve a high degree of alternative forms derived from a premature transcript by alternative splicing (as). with the advent of new sequencing technologies, evidence for new splice forms becomes more and more easily available-- bit by bit revealing that the true splicing diversity of "as events" often comprises more than two alternatives and therefore cannot be sufficiently described by pairwise comparisons as conducted in analyzes hitherto. further challenges emerge from the richness of data (millions of transcripts) and artifacts introduced during the technical process of obtaining transcript sequences (noise)--especially when dealing with singleread sequences known as expressed sequence tags (ests). we describe a novel method to efficiently predict as events in different resolutions (i.e., dimensions) from transcript annotations that allows for combination of fragmented est data with full-length cdnas and can cope with large datasets containing noise. applying this method to estimate the real complexity of alternative splicing, we found in human thousands of novel as events that either have been disregarded or mischaracterized in earlier works. in fact, the majority of exons that are observed as "mutually exclusive" in pairwise comparisons truly involve at least one other alternative splice form that disagrees with their mutual exclusion. we identified four major classes that contain such "optional" neighboring exons and show that they clearly differ from each other in characteristics, especially in the length distribution of the middle intron.
detecting disease-specific dysregulated pathways via analysis of clinical expression profiles. we present a method for identifying connected gene subnetworks significantly enriched for genes that are dysregulated in specimens of a disease. these subnetworks provide a signature of the disease potentially useful for diagnosis, pinpoint possible pathways affected by the disease, and suggest targets for drug intervention. our method uses microarray gene expression profiles derived in clinical case-control studies to identify genes significantly dysregulated in disease specimens, combined with protein interaction data to identify connected sets of genes. our core algorithm searches for minimal connected subnetworks in which the number of dysregulated genes in each diseased sample exceeds a given threshold. we have applied the method in a study of huntington's disease caudate nucleus expression profiles and in a meta-analysis of breast cancer studies. in both cases the results were statistically significant and appeared to home in on compact pathways enriched with hallmarks of the diseases.
the statistical power of phylogenetic motif models. one component of the genomic program controlling the transcriptional regulation of genes are the locations and arrangement of transcription factors bound to the promoter and enhancer regions of a gene. because the genomic locations of the functional binding sites of most transcription factors is not yet known, predicting them is of great importance. unfortunately, it is well known that the low specificity of the binding of transcription factors to dna makes such prediction, using position-specific probability matrices (motifs) alone, subject to huge numbers of false positives. one approach to alleviating this problem has been to use phylogenetic "shadowing" or "footprinting" to remove unconserved regions of the genome from consideration. another approach has been to combine a phylogenetic model and the site-specificity model into a single, predictive model of conserved binding sites. both of these approaches are based on alignments of orthologous genomic regions from two or more species. in this work, we use a simplified, theoretical model to study the statistical power of the later approach to the prediction of features such as transcription factor binding sites. we investigate the question of the number of genomes required at varying evolutionary distances to achieve specified levels of accuracy (false positive and false negative prediction rates). we show that this depends strongly on the information content of the position-specific probability matrix and on the evolutionary model. we explore the effects of modifying the structure of the phylogenetic model, and conclude that placing the target genome at the root of the tree has a negligible effect on the power predicted by the model. hence, as it is much easier to calculate, we can use this as an approximation to phylogenetic motif scanning using real trees. finally we perform an empirical study and demonstrate that the performance of current phylogenetic motif scanning programs is far from the theoretical limit of their power, leaving ample room for improvement.
framework for identifying common aberrations in dna copy number data. high-resolution array comparative genomic hybridization (acgh) provides exon-level mapping of dna aberrations in cells or tissues. such aberrations are central to carcinogenesis and, in many cases, central to targeted therapy of the cancers. some of the aberrations are sporadic, one-of-a-kind changes in particular tumor samples; others occur frequently and reflect common themes in cancer biology that have interpretable, causal ramifications. hence, the difficult task of identifying and mapping common, overlapping genomic aberrations (including amplifications and deletions) across a sample set is an important one; it can provide insight for the discovery of oncogenes, tumor suppressors, and the mechanisms by which they drive cancer development. in this paper we present an efficient computational framework for identification and statistical characterization of genomic aberrations that are common to multiple cancer samples in a cgh data set. we present and compare three different algorithmic approaches within the context of that framework. finally, we apply our methods to two datasets - a collection of 20 breast cancer samples and a panel of 60 diverse human tumor cell lines (the nci-60). those analyses identified both known and novel common aberrations containing cancer-related genes. the potential impact of the analytical methods is well demonstrated by new insights into the patterns of deletion of cdkn2a (p16), a tumor suppressor gene crucial for the genesis of many types of cancer.
reconstructing the topology of protein complexes. recent advances in high-throughput experimental techniques have enabled the production of a wealth of protein interaction data, rich in both quantity and variety. while the sheer quantity and variety of data present special difficulties for modeling, they also present unique opportunities for gaining insight into protein behavior by leveraging multiple perspectives. recent work on the modularity of protein interactions has revealed that reasoning about protein interactions at the level of domain interactions can be quite useful. we present proctor, a learning algorithm for reconstructing the internal topology of protein complexes by reasoning at the domain level about both direct protein interaction data (y2h) and protein co-complex data (ap-ms). while other methods have attempted to use data from both these kinds of assays, they usually require that cocomplex data be transformed into pairwise interaction data under a spoke or clique model, a transformation we do not require. we apply proctor to data from eight highthroughput datasets, encompassing 5,925 proteins, essentially all of the yeast proteome. first we show that proctor outperforms other algorithms for predicting domain-domain and protein-protein interactions from y2h and ap-ms data. then we show that our algorithm can reconstruct the internal topology of ap-ms purifications, revealing known complexes like arp2/3 and rna polymerase ii, as well as suggesting new complexes along with their corresponding topologies.
computation of median gene clusters. whole genome comparison based on gene order has become a popular approach in comparative genomics. an important task in this field is the detection of gene clusters, i.e. sets of genes that occur colocalized in several genomes. for most applications it is preferable to extend this definition to allow for small deviations in the gene content of the cluster occurrences. however, relaxing the equality constraint increases the computational complexity of gene cluster detection drastically. existing approaches deal with this problem by using simplifying constraints on the cluster definition and/or allowing only pairwise genome comparison. in this paper we introduce a cluster concept named median gene clusters that improves over existing models and present efficient algorithms for their computation that allow for the detection of approximate gene clusters in multiple genomes.
an efficient method for dynamic analysis of gene regulatory networks and gene perturbation experiments. with the increasing availability of experimental data on gene-gene and protein-protein interactions, modeling of gene regulatory networks has gained a special attention lately. to have a better understanding of these networks it is necessary to capture their dynamical properties, by computing its steady states. various methods have been proposed to compute steady states but almost all of them suffer from the state space explosion problem with the increasing size of the networks. hence it becomes difficult to model even moderate sized networks using these techniques. in this paper, we present a new representation of gene regulatory networks, which facilitates the steady state computation of networks as large as 1200 nodes and 5000 edges. we benchmarked and validated our algorithm on the t helper model from [8] and performed in silico knock out experiments: showing both a reduction in computation time and correct steady state identification.
network motif discovery using subgraph enumeration and symmetry-breaking. the study of biological networks and network motifs can yield significant new insights into systems biology. previous methods of discovering network motifs - network-centric subgraph enumeration and sampling - have been limited to motifs of 6 to 8 nodes, revealing only the smallest network components. new methods are necessary to identify larger network sub-structures and functional motifs. here we present a novel algorithm for discovering large network motifs that achieves these goals, based on a novel symmetry-breaking technique, which eliminates repeated isomorphism testing, leading to an exponential speed-up over previous methods. this technique is made possible by reversing the traditional network-based search at the heart of the algorithm to a motif-based search, which also eliminates the need to store all motifs of a given size and enables parallelization and scaling. additionally, our method enables us to study the clustering properties of discovered motifs, revealing even larger network elements. we apply this algorithm to the protein-protein interaction network and transcription regulatory network of s. cerevisiae, and discover several large network motifs, which were previously inaccessible to existing methods, including a 29-node cluster of 15-node motifs corresponding to the key transcription machinery of s. cerevisiae.
comparative analysis of spatial patterns of gene expression in imaginal discs. determining the precise spatial extent of expression of genes across different tissues, along with knowledge of the biochemical function of the genes is critical for understanding the roles of various genes in the development of metazoan organisms. to address this problem, we have developed high-throughput methods for generating images of gene expression in drosophila melanogaster imaginal discs and for the automated analysis of these images. our method automatically learns tissue shapes from a small number of manually segmented training examples and automatically aligns, extracts and scores new images, which are analyzed to generate gene expression maps for each gene. we have developed a reverse lookup procedure that enables us to identify genes that have spatial expression patterns most similar to a given gene of interest. our methods enable us to cluster both the genes and the pixels that of the maps, thereby identifying sets of genes that have similar patterns, and regions of the tissues of interest that have similar gene expression profiles across a large number of genes.
beyond galled trees - decomposition and computation of galled networks. reticulate networks are a type of phylogenetic network that are used to represent reticulate evolution involving hybridization, horizontal gene transfer or recombination. the simplest form of these networks are galled trees, in which all reticulations are independent of each other. this paper introduces a more general class of reticulate networks, that we call galled networks, in which reticulations are not necessarily independent, but may overlap in a tree-like manner. we prove a decomposition theorem for these networks that has important consequences for their computation, and present a fixed-parameter-tractable algorithm for computing such networks from trees or binary sequences. we provide a robust implementation of the algorithm and illustrate its use on two biological datasets, one based on a set of three gene-trees and the other based on a set of binary characters obtained from a restriction site map.
deterministic pharmacophore detection via multiple flexible alignment of drug-like molecules. we present a novel highly efficient method for the detection of a pharmacophore from a set of ligands/drugs that interact with a target receptor. a pharmacophore is a spatial arrangement of physicochemical features in a ligand that is responsible for the interaction with a specific receptor. in the absence of a known 3d receptor structure, a pharmacophore can be identified from a multiple structural alignment of the ligand molecules. the key advantages of the presented algorithm are: (a) its ability to multiply align flexible ligands in a deterministic manner, (b) its ability to focus on subsets of the input ligands, which may share a large common substructure, resulting in the detection of both outlier molecules and alternative binding modes, and (c) its computational efficiency, which allows to detect pharmacophores shared by a large number of molecules on a standard pc. the algorithm was extensively tested on a dataset of almost 80 ligands acting on 12 different receptors. the results, which were achieved using a standard default parameter set, were consistent with reference pharmacophores that were derived from the bound ligand-receptor complexes. the pharmacophores detected by the algorithm are expected to be a key component in the discovery of new leads by screening large drug-like molecule databases.
free energy estimates of all-atom protein structures using generalized belief propagation. we present a technique for approximating the free energy of protein structures using generalized belief propagation (gbp). the accuracy and utility of these estimates are then demonstrated in two different application domains. first, we show that the entropy component of our free energy estimates can be useful in distinguishing native protein structures from decoys -- structures with similar internal energy to that of the native structure, but otherwise incorrect. our method is able to correctly identify the native fold from among a set of decoys with 87.5% accuracy over a total of 48 different immunoglobin folds. the remaining 12.5% of native structures are ranked among the top 4 of all structures. second, we show that our estimates of δδg upon mutation upon mutation for three different data sets have linear correlations between 0.63-0.70 with experimental values and statistically significant p-values. together, these results suggests that gbp is an effective means for computing free energy in all-atom models of protein structures. gbp is also efficient, taking a few minutes to run on a typical sized protein, further suggesting that gbp may be an attractive alternative to more costly molecular dynamic simulations for some tasks.
a bayesian model that links microarray mrna measurements to mass spectrometry protein measurements. an important problem in biology is to understand correspondences between mrna microarray levels and mass spectrometry peptide counts. recently, a compendium of mrna expression levels and protein abundances were released for the entire genome of the laboratory mouse, mus musculus. the availability of these two data sets facilitate using machine learning methods to automatically infer plausible correspondences between the gene products. knowing these correspondences can be helpful either for predicting protein abundances from microarray data or as an independent source of information that can be used for learning richer models such as regulatory networks. we propose a probabilistic model that relates protein abundances to mrna expression levels. using cross-mapped data from the above-mentioned studies, we learn the model and then score the genes for their strength of relationship by performing probabilistic inference in the learned model. while we gave a simplified outline of our technique in a publication aimed at biologists (cell 2006), in this paper, we give a complete description of the bayesian model and the computational technique used to perform inference. in addition, we demonstrate that the bayesian technique achieves mappings with higher statistical significance, compared to standard linear regression and a maximum likelihood version of the proposed model.
peptide retention time prediction yields improved tandem mass spectrum identification for diverse chromatography conditions. most tandem mass spectrum identification algorithms use information only from the final spectrum, ignoring precursor information such as peptide retention time (rt). efforts to exploit peptide rt for peptide identification can be frustrated by its variability across liquid chromatography analyses. we show that peptide rt can be reliably predicted by training a support vector regressor on a single chromatography run. this dynamically trained model outperforms a published statically trained model of peptide rt across diverse chromatography conditions. in addition, the model can be used to filter peptide identifications that produce large discrepancies between observed and predicted rt. after filtering, estimated true positive peptide identifications increase by as much as 50% at a false discovery rate of 3%, with the largest increase for non-specific cleavage with elastase.
rb-finder: an improved distance-based sliding window method to detect recombination breakpoints. recombination detection is important before inferring phylogenetic relationships. this will eventually lead to a better understanding of pathogen evolution, more accurate genotyping and advancements in vaccine development. in this paper, we introduce rb-finder, a fast and accurate distance-based window method to detect recombination in a multiple sequence alignment. our method introduces a more informative distance measure and a novel weighting strategy to reduce the window size sensitivity problem and hence improve the accuracy of breakpoint detection. furthermore, our method is faster than existing phylogenybased methods since we do not need to construct and compare complex phylogenetic trees. when compared with the current best method pruned-pdm, we are about a few hundred times more efficient. experimental evaluation of rb-finder using synthetic and biological datasets showed that our method is more accurate than existing phylogeny-based methods. we also show how our method has potential use in other related applications such as genotyping.
network legos: building blocks of cellular wiring diagrams. publicly-available data sets provide detailed and large-scale information on multiple types of molecular interaction networks in a number of model organisms. these multi-modal universal networks capture a static view of cellular state. an important challenge in systems biology is obtaining a dynamic perspective on these networks by integrating them with gene expression measurements taken under multiple conditions. we present a top-down computational approach to identify building blocks of molecular interaction networks by (i) integrating gene expression measurements for a particular disease state (e.g., leukaemia) or experimental condition (e.g., treatment with growth serum) with molecular interactions to reveal an active network, which is the network of interactions active in the cell in that disease state or condition and (ii) systematically combining active networks computed for different experimental conditions using set-theoretic formulae to reveal network legos, which are modules of coherently interacting genes and gene products in the wiring diagram. we propose efficient methods to compute active networks, systematically mine candidate legos, assess the statistical significance of these candidates, arrange them in a directed acyclic graph (dag), and exploit the structure of the dag to identify true network legos. we describe methods to assess the stability of our computations to changes in the input and to recover active networks by composing network legos. we analyse two human datasets using our method. a comparison of three leukaemias demonstrates how a biologist can use our system to identify specific differences between these diseases. a larger-scale analysis of 13 distinct stresses illustrates our ability to compute the building blocks of the interaction networks activated in response to these stresses.
nucleosome occupancy information improves motif discovery. a complete understanding of transcriptional regulatory processes in the cell requires identification of transcription factor binding sites on a genomewide scale. unfortunately, these binding sites are typically short and degenerate, posing a significant statistical challenge: many more matches to known transcription factor binding sites occur in the genome than are actually functional. chromatin structure is known to play an important role in guiding transcription factors to those sites that are functional. in particular, it has been shown that active regulatory regions are usually depleted of nucleosomes, thereby enabling transcription factors to bind dna in those regions [1]. in this paper, we describe a novel algorithm which employs an informative prior over dna sequence positions based on a discriminative view of nucleosome occupancy; the nucleosome occupancy information comes from a recently published computational model [2]. when a gibbs sampling algorithm with our informative prior is applied to yeast sequencesets identified by chip-chip [3], the correct motif is found in 50% more cases than with an uninformative uniform prior. moreover, if nucleosome occupancy information is not available, our informative prior reduces to a new kind of prior that can exploit discriminative information in a purely generative setting.
protein conformational flexibility analysis with noisy data. protein conformational changes play a critical role in biological functions such as ligand-protein and protein-protein interactions. due to the noise in structural data, determining salient conformational changes reliably and efficiently is a challenging problem. this paper presents an efficient algorithm for analyzing protein conformational changes, using noisy data. it applies a statistical flexibility test to all contiguous fragments of a protein and combines the information from these tests to compute a consensus flexibility measure for each residue of the protein. we tested the algorithm, using data from the protein data bank and the macromolecular movements database. the results show that our algorithm can reliably detect different types of salient conformational changes, including well-known examples such as hinge and shear, as well as the flap motion of hiv-1 protease. the software implementing our algorithm is available at http://motion.comp.nus.edu.sg/projects/ proflexana/proflexana.html.