waashk/dblp huggingface dataset:
disruption of a transcriptional regulatory pathway contributes to phenotypes in carriers of ataxia telangiectasia. ataxia telangiectasia, at, is a recessive disorder caused by mutations in the atm gene. although it is a recessive disorder, population-based studies have shown that carriers of at have increased risks of breast cancer and other diseases compared to non-carriers. the goal of this study is to characterize phenotypes in at carriers. since expression level of genes is a major determinant of cellular phenotypes, we studied gene expression in at carriers and identified regulatory mechanisms that influence these expression phenotypes. we found gene expression phenotypes that showed a recessive pattern, where at carriers are similar to non-carriers but differ from at patients. however, there are also expression phenotypes that showed a dominant pattern where at carriers are similar to at patients but differ from non-carriers. one of the dominant gene expression phenotypes is that of tnfsf4. we showed that atm regulates tnfsf4 expression through a transcriptional regulatory pathway that includes transcription factors and mirnas. in at carriers and at patients, this pathway is disrupted, resulting in higher expression of tnfsf4. in this presentation, i will describe this atm-mediated pathway, and show that the disruption of this pathway leads to increased risk of breast cancer and cardiac death in at carriers. the integration of molecular and computational analyses of gene and microrna expression revealed the complex consequences of a human gene mutation.
a combined expression-interaction model for inferring the temporal activity of transcription factors. methods suggested for reconstructing regulatory networks can be divided into two sets based on how the activity level of transcription factors (tfs) is inferred. the first group of methods relies on the expression levels of tfs assuming that the activity of a tf is highly correlated with its mrna abundance. the second treats the activity level as unobserved and infers it from the expression of the genes the tf regulates. while both types of methods were successfully applied, each suffers from drawbacks that limit their accuracy. for the first set, the assumption that mrna levels are correlated with activity is violated for many tfs due to post-transcriptional modifications. for the second, the expression level of a tf which might be informative is completely ignored. here we present the post-transcriptional modification model (ptmm) that unlike previous methods utilizes both sources of data concurrently. our method uses a switching model to determine whether a tf is transcriptionally or post-transcriptionally regulated. this model is combined with a factorial hmm to fully reconstruct the interactions in a dynamic regulatory network. using simulated and real data we show that ptmm outperforms the other two approaches discussed above. using real data we also show that ptmm can recover meaningful tf activity levels and identify post-transcriptionally modified tfs, many of which are supported by other sources.
at the origin of life: how did folded proteins evolve? proteins are essential building blocks of living cells; indeed, life can be viewed as resulting substantially from the chemical activity of proteins. because of their importance, it is hardly surprising that ancestors for most proteins observed today were already present at the time of the 'last common ancestor', a primordial organism from which all life on earth is descended. yet folded proteins are too complex to have arisen de novo. how then did they evolve? we are pursuing the hypothesis that folded proteins evolved by fusion and recombination from an ancestral set of peptides, which emerged in the context of rna-dependent replication and catalysis (the "rna world"). systematic studies should allow a description of this ancient peptide set in the same way in which ancient vocabularies have been reconstructed from the comparative study of modern languages.
automatic parameter learning for multiple network alignment. we developed græmlin 2.0, a new multiple network aligner with (1) a novel scoring function that can use arbitrary features of a multiple network alignment, such as protein deletions, protein duplications, protein mutations, and interaction losses; (2) a parameter learning algorithm that uses a training set of known network alignments to learn parameters for our scoring function and thereby adapt it to any set of networks; and (3) an algorithm that uses our scoring function to find approximate multiple network alignments in linear time. we tested græmlin 2.0's accuracy on protein interaction networks from intact, dip, and the stanford network database.we show that, on each of these datasets, græmlin 2.0 has higher sensitivity and specificity than existing network aligners. græmlin 2.0 is available under the gnu public license at http://graemlin.stanford.edu.
automatic recognition of cells (arc) for 3d images of c. elegans. the development of high-resolution microscopy makes possible the high-throughput screening of cellular information, such as gene expression at single cell resolution. one of the critical enabling techniques yet to be developed is the automatic recognition or annotation of specific cells in a 3d image stack. in this paper, we present a novel graph-based algorithm, arc, that determines cell identities in a 3d confocal image of c. elegans based on their highly stereotyped arrangement. this is an essential step in our work on gene expression analysis of c. elegans at the resolution of single cells. our arc method integrates both the absolute and relative spatial locations of cells in a c. elegans body. it uses a marker-guided, spatially-constrained, two-stage bipartite matching to find the optimal match between cells in a subject image and cells in 15 template images that have been manually annotated and vetted. we applied arc to the recognition of cells in 3d confocal images of the first larval stage (l1) of c. elegans hermaphrodites, and achieved an average accuracy of 94.91%.
learning models for aligning protein sequences with predicted secondary structure. accurately aligning distant protein sequences is notoriously difficult. a recent approach to improving alignment accuracy is to use additional information such as predicted secondary structure. we introduce several new models for scoring alignments of protein sequences with predicted secondary structure, which use the predictions and their confidences to modify both the substitution and gap cost functions. we present efficient algorithms for computing optimal pairwise alignments under these models, all of which run in near-quadratic time. we also review an approach to learning the values of the parameters in these models called inverse alignment. we then evaluate the accuracy of these models by studying how well an optimal alignment under the model recovers known benchmark reference alignments. our experiments show that using parameters learned by inverse alignment, these new secondary-structure-based models provide a significant improvement in alignment accuracy for distant sequences. the best model improves upon the accuracy of the standard sequence alignment model for pairwise alignment by as much as 15% for sequences with less than 25% identity, and improves the accuracy of multiple alignment by 20% for difficult benchmarks whose average accuracy under standard tools is less than 40%.
shared peptides in mass spectrometry based protein quantification. in analyzing the proteome using mass spectrometry, the mass values help identify the molecules, and the intensities help quantify them, relative to their abundance in other samples. peptides that are shared across different protein sequences are typically discarded as being uninformative w.r.t each of the parent proteins.in this paper, we investigate the use of shared peptides which are ubiquitous (~50% of peptides) in mass spectrometric data-sets. in many cases, shared peptides can help compute the relative amounts of different proteins that share the same peptide. also, proteins with no unique peptide in the sample can still be analyzed for relative abundance. our paper is the first attempt to use shared peptides in protein quantification, and makes use of combinatorial optimization to reduce the error in relative abundance measurements. we describe the topological and numerical properties required for robust estimates, and use them to improve our estimates for ill-conditioned systems. extensive simulations validate our approach even in the presence of experimental error. we apply our method to a model of arabidopsis root knot nematode infection, and elucidate the differential role of many protein family members in mediating host response to the pathogen.
a robust bayesian two-sample test for detecting intervals of differential gene expression in microarray time series. understanding the regulatory mechanisms that are responsible for an organism's response to environmental changes is an important question in molecular biology. a first and important step towards this goal is to detect genes whose expression levels are affected by altered external conditions. a range of methods to test for differential gene expression, both in static as well as in time-course experiments, have been proposed. while these tests answer the question whether a gene is differentially expressed, they do not explicitly address the question when a gene is differentially expressed, although this information may provide insights into the course and causal structure of regulatory programs. in this article, we propose a two-sample test for identifying intervals of differential gene expression in microarray time series. our approach is based on gaussian process regression, can deal with arbitrary numbers of replicates and is robust with respect to outliers. we apply our algorithm to study the response of arabidopsis thaliana genes to an infection by a fungal pathogen using a microarray time series dataset covering 30,336 gene probes at 24 time points. in classification experiments our test compares favorably with existing methods and provides additional insights into time-dependent differential expression.
simultaneous alignment and folding of protein sequences. accurate comparative analysis tools for low-homology proteins remains a difficult challenge in computational biology, especially sequence alignment and consensus folding problems. we presentpartifold-align, the first algorithm for simultaneous alignment and consensus folding of unaligned protein sequences; the algorithm's complexity is polynomial in time and space. algorithmically,partifold-align exploits sparsity in the set of super-secondary structure pairings and alignment candidates to achieve an effectively cubic running time for simultaneous pairwise alignment and folding. we demonstrate the efficacy of these techniques on transmembrane β-barrel proteins, an important yet difficult class of proteins with few known three-dimensional structures. testing against structurally derived sequence alignments,partifold-align significantly outperforms state-of-the-art pairwise sequence alignment tools in the most difficult low sequence homology case and improves secondary structure prediction where current approaches fail. importantly, partifold-align requires no prior training. these general techniques are widely applicable to many more protein families. partifold-align is available at http://partifold.csail.mit.edu.
phylogenies without branch bounds: contracting the short, pruning the deep. we introduce a new phylogenetic reconstruction algorithm which, unlike most previous rigorous inference techniques, does not rely on assumptions regarding the branch lengths or the depth of the tree. the algorithm returns a forest which is guaranteed to contain all edges that are: 1) sufficiently long and 2) sufficiently close to the leaves. how much of the true tree is recovered depends on the sequence length provided. the algorithm is distance-based and runs in polynomial time.
combinatorial algorithms for structural variation detection in high throughput sequenced genomes. recent studies show that, along with single nucleotide polymorphisms and small indels, larger structural variants among human individuals are common. these studies have typically been based high-cost library generation and sanger sequencing; however, recent introduction of next-generation sequencing (ngs) technologies is changing how research in this area is conducted in a significant way. highthroughput sequencing technologies such as 454, illumina, helicos, and ab solid produce shorter reads than the traditional capillary sequencing, yet they reduce the cost (and/or the redundancy) by a factor of 10 - 100 and perhaps even more. those ngs technologies with the capability of sequencing paired-ends (or matepairs) of a clone insert (which follows a tight length distribution) have made it feasible to perform detailed and comprehensive genome variation and rearrangement studies. unfortunately, the few existing algorithms for identifying structural variation among individuals using paired-end reads have not been designed to handle the short read lengths and the errors implied by these platforms. here, we describe, for the first time, algorithms for identifying various forms of structural variation between a paired-end ngs sequenced genome and a reference genome.
detecting the presence and absence of causal relationships between expression of yeast genes with very few samples. inference of biological networks from high-throughput data is a central problem in bioinformatics. particularly powerful for network reconstruction is data collected by recent studies that contain both genetic variation information and gene expression profiles from genetically distinct strains of an organism. various statistical approaches have been applied to these data to tease out the underlying biological networks that govern how individual genetic variation mediates gene expression and how genes regulate and interact with each other. extracting meaningful causal relationships from these networks remains a challenging but important problem. in this paper we use causal inference techniques to infer the presence or absence of causal relationships between yeast gene expressions in the framework of graphical causal models. we evaluate our method using a well studied dataset consisting of both genetic variation information and gene expressions collected over yeast strains. our predictions of causal regulators are consistent with previously known experimental evidence. in addition, our method can distinguish between direct and indirect effects of variation on a gene expression level.
haplotype inference in complex pedigrees. despite the desirable information contained in complex pedigree datasets, analysis methods struggle to efficiently process these datasets. the attractiveness of pedigree data sets is their power for detecting rare variants, particularly in comparison with studies of unrelated individuals. in addition, rather than assuming individuals in a study are unrelated, knowledge of their relationships can avoid spurious results due to confounding population structure effects. however, a major challenge for the applicability of pedigree methods is the ability handle complex pedigrees, having multiple founding lineages, inbreeding, and half-sibling relationships.a key ingredient in association studies is imputation and inference of haplotypes from genotype data. existing haplotype inference methods either do not efficiently scales to complex pedigrees or their accuracy is limited. in this paper, we present algorithms for efficient haplotype inference and imputation in complex pedigrees. our method, phyloped, leverages the perfect phylogeny model, resulting in an efficient method with high accuracy. in addition, phyloped effectively combines the founder haplotype information from different lineages and is immune to inaccuracies in prior information about the founders.
lifting prediction to alignment of rna pseudoknots. prediction and alignment of rna pseudoknot structures are np-hard. nevertheless, several efficient prediction algorithms by dynamic programming have been proposed for restricted classes of pseudoknots. we present a general scheme that yields an efficient alignment algorithm for arbitrary such classes. moreover, we show that such an alignment algorithm benefits from the class restriction in the same way as the corresponding structure prediction algorithm does. we look at five of these classes in greater detail. the time and space complexity of the alignment algorithm is increased by only a linear factor over the respective prediction algorithm. for four of the classes, no efficient alignment algorithms were known. for the fifth, most general class, we improve the previously best complexity of o(n 5 m 5) time to o(nm 6), where n and m denote sequence lengths. finally, we apply our fastest algorithm with o(nm 4) time and o(nm 2) space to comparative de-novo pseudoknot prediction.
optimizing pcr assays for dna based cancer diagnostics. somatically acquired dna rearrangements are characteristic of many cancers. the use of these mutations as diagnostic markers is challenging, because tumor cells are frequently admixed with normal cells, particularly in early stage tumor samples, and thus the samples contain a high background of normal dna. detection is further confounded by the fact that the rearrangement boundaries are not conserved across individuals, and might vary over hundreds of kilobases. here, we present an algorithm for designing pcr primers and oligonucleotide probes to assay for these variant rearrangements. specifically, the primers and probes tile the entire genomic region surrounding a rearrangement, so as to amplify the mutant dna over a wide range of possible breakpoints and robustly assay for the amplified signal on an array. our solution involves the design of a complex combinatorial optimization problem, and also includes a novel alternating multiplexing strategy that makes efficient detection possible. simulations show that we can achieve near-optimal detection in many different cases, even when the regions are highly non-symmetric. additionally, we prove that the suggested multiplexing strategy is optimal in breakpoint detection.we applied our technique to create a custom design to assay for genomic lesions in several cancer cell-lines associated with a disruption in the cdkn2a locus. the cdkn2a deletion has highly variable boundaries across many cancers. we successfully detect the breakpoint in all cell-lines, even when the region has undergone multiple rearrangements. these results point to the development of a successful protocol for early diagnosis and monitoring of cancer.
an online approach for mining collective behaviors from molecular dynamics simulations. collective behavior involving distally separate regions in a protein is known to widely affect its function. in this paper, we present an online approach to study and characterize collective behavior in proteins as molecular dynamics simulations progress. our representation of md simulations as a stream of continuously evolving data allows us to succinctly capture spatial and temporal dependencies that may exist and analyze them efficiently using data mining techniques. by using multi-way analysis we identify (a) parts of the protein that are dynamically coupled, (b) constrained residues/ hinge sites that may potentially affect protein function and (c) time-points during the simulation where significant deviation in collective behavior occurred. we demonstrate the applicability of this method on two different protein simulations for barnase and cyclophilin a. for both these proteins we were able to identify constrained/ flexible regions, showing good agreement with experimental results and prior computational work. similarly, for the two simulations, we were able to identify time windows where there were significant structural deviations. of these time-windows, for both proteins, over 70% show collective displacements in two or more functionally relevant regions. taken together, our results indicate that multi-way analysis techniques can be used to analyze protein dynamics and may be an attractive means to automatically track and monitor molecular dynamics simulations.
sorting signed permutations by inversions in o(nlogn) time. the study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. after the initial breakthrough of hannenhalli and pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inversions, improved algorithms have been designed, culminating with an optimal linear-time algorithm for computing the inversion distance and a subquadratic algorithm for providing a shortest sequence of inversions--also known as sorting by inversions. remaining open was the question of whether sorting by inversions could be done in o(nlogn) time.in this paper, we present a qualified answer to this question, by providing two new sorting algorithms, a simple and fast randomized algorithm and a deterministic refinement. the deterministic algorithm runs in time o(nlogn + kn), where k is a data-dependent parameter. we provide the results of extensive experiments showing that both the average and the standard deviation for k are small constants, independent of the size of the permutation. we conclude (but do not prove) that almost all signed permutations can be sorted by inversions in o(nlogn) time.
spatial clustering of multivariate genomic and epigenomic information. the combination of fully sequence genomes and new technologies for high density arrays and ultra-rapid sequencing enables the mapping of gene-regulatory and epigenetics marks on a global scale. this new experimental methodology was recently applied to map multiple histone marks and genomic factors, characterizing patterns of genome organization and discovering interactions among processes of epigenetic reprogramming during cellular differentiation. the new data poses a significant computational challenge in both size and statistical heterogeneity. understanding it collectively and without bias remains an open problem. here we introduce spatial clustering - a new unsupervised clustering methodology for dissection of large, multi-track genomic and epigenomic data sets into a spatially organized set of distinct combinatorial behaviors. we develop a probabilistic algorithm that finds spatial clustering solutions by learning an hmm model and inferring the most likely genomic layout of clusters. application of our methods to meta-analysis of combined chip-seq and chip-chip epigenomic datasets in mouse and human reveals known and novel patterns of local co-occurrence among histone modification and related factors. moreover, the model weaves together these local patterns into a coherent global model that reflects the higher level organization of the epigenome. spatial clustering constitutes a powerful and scalable analysis methodology for dissecting even larger scale genomic dataset that will soon become available.