waashk/dblp huggingface dataset:
systematic and automated discovery of patterns in prosite families. prosite is a method for protein classification which relies on a database of biologically significant sites and patterns in protein sequences. most patterns in prosite have been gathered by a a labor intensive combination of experimental characterization of functional residues and sequence alignment. in this paper we present a new and efficient supervised learning procedure, based on the splash deterministic pattern discovery algorithm and on a framework to assess the statistical significance of patterns. we demonstrate its application to the fully automatic discovery of patterns in 974 prosite families. for these families, splash generates patterns with better specificity and/or sensitivity in 28%, identical statistics in 48%, and worse statistics in 15% of the cases; for the remaining families, patterns exhibited mixed behavior. second, we have characterized the amount of overlap, on the sequences, between newly discovered patterns and those in prosite. in about 75% of the cases, splash patterns identify sequence sites that overlap more than 50% with those reported in prosite. of the 272 patterns which perform strictly better than the corresponding prosite pattern, 178 show more than 70% overlap with the prosite pattern. third, our results suggest that the statistical significance of discovered patterns correlates well with their biological significance. finally, we use the trypsin subfamily of serine proteases to illustrate the use of this method to exhaustively discover all motifs in a family that are statistically and biologically significant. the complete analysis is sufficiently rapid, taking less than a day for all prosite families, to enable the use this methodology for routine curation of existing motif and profile databases.
haplotyping as perfect phylogeny: conceptual framework and efficient solutions. the next high-priority phase of human genomics will involve the development of a full haplotype map of the human genome [12]. it will be used in large-scale screens of populations to associate specific haplotypes with specific complex genetic-influenced diseases. a prototype haplotype mapping strategy is presently being finalized by an nih working-group. the biological key to that strategy is the surprising fact that genomic dna can be partitioned into long blocks where genetic recombination has been rare, leading to strikingly fewer distinct haplotypes in the population than previously expected [12, 6, 21, 7].in this paper we explore the algorithmic implications of the key (and now realistic) "no-recombination in long blocks" observation, for the problem of inferring haplotypes in populations. we observe that the no-recombination assumption is very powerful. this assumption, along with the standard population-genetic assumption of infinite sites [23, 14] imposes severe combinatorial constraints on the permitted solutions to the haplotype inference problem, leading to an efficient deterministic algorithm to deduce all features of the permitted haplotype solution(s) that can be known with certainty. the technical key is to view haplotype data as disguised information about paths in an unknown tree, and the haplotype deduction problem as a problem of reconstructing the tree from that path information. this formulation allows us to exploit deep theorems and algorithms from graph and matroid theory to efficiently find one permitted solution to the haplotype problem; it gives a simple test to determine if it is the unique solution; if not, we can implicitly represent the set of all permitted solutions so that each can be efficiently created.
stochastic models inspired by hybridization theory for short oligonucleotide arrays. high density oligonucleotide expression arrays are a widely used tool for the measurement of gene expression on a large scale. affymetrix genechip arrays appear to dominate this market. these arrays use short oligonucleotides to probe for genes in an rna sample. due to optical noise, non-specific hybridization, probe-specific effects, and measurement error, ad-hoc measures of expression, that summarize probe intensities, can lead to imprecise and inaccurate results. various researchers have demonstrated that expression measures based on simple statistical models can provide great improvements over the ad-hoc procedure offered by affymetrix. recently, physical models based on molecular hybridization theory, have been proposed as useful tools for prediction of, for example, non-specific hybridization. these physical models show great potential in terms of improving existing expression measures. in this paper we suggest that the system producing the measured intensities is too complex to be fully described with these relatively simple physical models and we propose empirically motivated stochastic models that compliment the above mentioned molecular hybridization theory to provide a comprehensive description of the data. we discuss how the proposed model can be used to obtain improved measures of expression useful for the data analysts.
computational analysis of the human and other mammalian genomes. working drafts are now available for the human, mouse and rat genomes, and other mammalian genome sequences are on the way. we discuss some of the key bioinformatic analysis problems presented by this data, including the problems of assembling the sequence, finding the genes and other functional elements, and reconstructing the evolutionary history of the genomes. recent comparisons between the human and mouse genomes have revealed that approximately 5% of the human genome appears to be more conserved with the orthologous regions in mouse than can be explained assuming neutral evolution. is this the portion of the genome under selection for specific functions? how can we use comparative genomics to further pinpoint functional elements? how accurately can we reconstruct the evolutionary history of key parts of the human genome? we briefly outline some recent work (described in more detail in adam siepel's talk) combining hidden markov models, used in bioinformatics to analyse dna from a single species, with continuous time markov models of molecular evolution, used to reconstruct evolutionary history of several species. while still a long way from answering these questions, these methods may contribute to such investigations.
an integrated probabilistic model for functional prediction of proteins. we develop an integrated probabilistic model to combine protein physical interactions, genetic interactions, highly correlated gene expression network, protein complex data, and domain structures of individual proteins to predict protein functions. the model is an extension of our previous model for protein function prediction based on markovian random field theory. the model is flexible in that other protein pairwise relationship information and features of individual proteins can be easily incorporated. two features distinguish the integrated approach from other available methods for protein function prediction. one is that the integrated approach uses all available sources of information with different weights for different sources of data. it is a global approach that takes the whole network into consideration. the second feature is that the posterior probability that a protein has the function of interest is assigned. the posterior probability indicates how confident we are about assigning the function to the protein. we apply our integrated approach to predict functions of yeast proteins based upon mips protein function classifications and upon the interaction networks based on mips physical and genetic interactions, gene expression profiles, tandem affinity purification (tap) protein complex data, and protein domain information. we study the sensitivity and specificity of the integrated approach using different sources of information by the leave-one-out approach. in contrast to using mips physical interactions only, the integrated approach combining all of the information increases the sensitivity from 57% to 87% when the specificity is set at 57%-an increase of 30%. it should also be noted that enlarging the interaction network greatly increases the number of proteins whose functions can be predicted.
inferring domain-domain interactions from protein-protein interactions. protein-protein interactions are important events in cellular and biochemical processes within a cell. several researchers have undertaken the task of analyzing protein-protein interactions covering all genes of an organism by using yeast two-hybrid assays. protein-protein interactions involve physical interactions between protein domains. therefore, understanding protein interactions at the domain level gives a global view of the protein interaction network, and possibly extends functions of proteins. in this study, we present a maximum likelihood approach to infer domain-domain interactions from the 5719 yeast protein-protein interactions obtained in the high throughput two-hybrid experiments by uetz et al., 2000 and ito et al., 2001. the accuracies of our predictions are measured at the protein level. our study includes the following three results: (1) using the inferred domain-domain interactions, we predict interactions between proteins and achieve 39.0% specificity and 79.7% sensitivity; (2) our predicted protein-protein interactions have a significant overlap with the mips(http://mips.gfs.de) protein-protein interactions obtained by methods other than the two-hybrid systems; and (3) the mean correlation coefficient of the gene expression profiles for our predicted interacting pairs is significantly higher than that for random pairs as well as that of interacting pairs in uetz's and ito's experimental data. our method has shown robustness in analyzing incomplete data sets and dealing with various experimental errors. we find several novel protein-protein interactions such as rps0a interacting with apg17 and taf40 interacting with spt3, which are consistent with the functions of the proteins.
tree fitting: an algebraic approach using profile distances. distance methods play a central role in the field of phylogeny reconstruction, providing fast, efficient algorithms which yield reliable trees. the taxonomy problem is; given a set of dna or amino acid sequences from several species, accurately reconstruct a phylogenetic tree representing their evolutionary history. distance methods approach this problem by inferring a distance matrix of species-to-species evolutionary distances, and finding a tree which approximates the distance matrix. our results consider the approach of using profile distances instead of leaf-to-leaf distances. we consider the vector space of tree metrics with regard to a basis generated by profile distances given a fixed tree topology, we show how to project edge weights onto a topology based upon its set of profile distances. the projected edge weights provide topological insight, as negative edge weights will point to false edges in the topology. although the presence of such negative edge weights is not guaranteed, we show that if the test tree is sufficiently close to the target tree in topology, negative edge weights will highlight the false edges. an algorithm is presented which uses this information to accurately reconstruct tree metrics.
sequencing by hybridization using direct and reverse cooperating spectra. dna sequencing by hybridization, proposed about a decade ago as an alternative to standard electrophoresis-based sequencing techniques, is relevant not only to sequencing per se but also to diagnostics and therapeutics. the inherent structural inadequacy of traditional probe patterns and well-known hybridization shortcomings had for some time deflated the interest in this approach. renewed interest for this topic has been generated by our recent discovery of a novel probing scheme whose performance for the first time asymptotically meets the information theory bound. after settling the question of asymptotic performance, due to the sizable volume of potential applications, the research focus has naturally shifted to issues of algorithmic fine tunings aimed at improving the performance "constants". in this paper, we introduce as a figure of merit the nucleotide-per-feature ratio (for a given confidence level), i.e., the length of a reliabily reconstructible (random) sequence divided by the number of probes placed on the sequencing array, regardless of the fabrication technology, and we explore the capabilities offered by the joint use of multiple different arrays in sequencing the same dna sequence. in particular we consider a probing scheme based on the use of the spectra pertaining to a given probing pattern and to its reversal (referred to here as tandem spectra), and we show analytically and experimentally a performance improvement per unit of microarray area of about 4/3 (in a representative instance) over the conventional single-spectrum approach. the proposed tandem-spectrum reconstruction, in conjunction with a "voting provision" discussed elsewhere (whereby one of two competing alternatives is chosen if the corresponding probes are less numerous in the current prefix of the reconstructive sequence), is the best known technique for sequencing by hybridization.
contig selection in physical mapping. in physical mapping one orders a set of genetic landmarks or a library of cloned fragments of dna according to their position in the genome. this is a preparatory step for efficient sequencing. our approach to physical mapping divides the problem into smaller and easier subproblems by partitioning the probe set into independent parts (contigs). the focus is on the selection of probe sets which can be grouped together into contigs. we introduce a new distance function between probes, the averaged rank distance (ard). the ard measures the reliability of certain probe configurations in physical maps which are generated by bootstrap resampling of the raw data. this mimics an independent experiment repetition in silico. the ard measures the distances of probes within a contig and smoothes the distances of probes in different contigs. it shows distinct jumps at contig borders. this makes it appropriate for contig selection by clustering. we designed a physical mapping algorithm that makes use of these observations and seems to be particularly well suited to the delineation of reliable contigs. we evaluated our method on data sets from two physical mapping projects. in comparison to a physical map of pasteurella haemolytica that was computed using simulated annealing, the newly computed map is considerably cleaner. on data from xylella fastidiosa the contigs produced by the new method could be compared to a map produced by a group of experts and the two maps largely agree in the definition of the contigs. the results of our method have already proven helpful for the design of experiments aiming at further improving the quality of a map.
analysis of gene expression profiles: class discovery and leaf ordering. we approach the class discovery and leaf ordering problems using spectral graph partitioning methodologies. for class discovery or clustering, we present a min-max cut hierarchical clustering method and show it produces subtypes quite close to human expert labeling on the lymphoma dataset with 6 classes. on optimal leaf ordering for displaying the gene expression data, we present a sequential ordering method that can be computed in o(n2) time which also preserves the cluster structure. we also show that the well known statistic methods such as f-statistic test and the principal component analysis are very useful in gene expression analysis.
accurate detection of very sparse sequence motifs. protein sequence alignments are more reliable the shorter the evolutionary distance. here, we align distantly related proteins using many closely spaced intermediate sequences as stepping stones. such transitive alignments can be generated between any two proteins in a connected set, whether they are direct or indirect sequence neighbours in the underlying library of pairwise alignments. we have implemented a greedy algorithm, maxflow, using a novel consistency score to estimate the relative likelihood of alternative paths of transitive alignment. in contrast to traditional profile models of amino acid preferences, maxflow models the probability that two positions are structurally equivalent and retains high information content across large distances in sequence space. thus, maxflow is able to identify sparse and narrow active-site sequence signatures which are embedded in high-entropy sequence segments in the structure-based multiple alignment of large diverse enzyme superfamilies. in a challenging benchmark, maxflow yields better reliability and double coverage compared to available sequence alignment software. this promises to increase information returns from functional and structural genomics, where reliable sequence alignment is a bottleneck to transferring the functional or structural characterization of model proteins to entire protein families and superfamilies.
a data-analysis pipeline for large-scale gene expression analysis. in this article we describe a method for characterization of large cdna clone libraries based on oligonucleotide fingerprints (ofps). the main advantage of this technique lies in that, without sequencing, each clone is tagged in an almost unique way, which has a couple of interesting applications, e.g. clustering of clones that belong to the same gene or gene family followed by sequencing of representative clones for each cluster. moreover, small clusters are likely to represent rarely expressed genes, which are difficult to find by common approaches. we will demonstrate that in the est projects carried out in our lab the global redundancy is very low compared to similar projects described in the literature, and simultaneously the number of unknown (novel) genes detected using this method is very high. in addition ofps can be used directly for data base mining, since the sequences of the oligos matching a specific clone is known recent results are presented, which underline the potential of our method in finding novel genes or genes homologous to known data. we will also address future applications in gene expression profiling, and give an outline of the various bioinformatics tools, which have been developed so far and which are used for automated data processing and analysis.
fifty years of sequence analysis: what have we learned? in 1955, not quite fifty years ago, sanger's group published the first amino acid sequence of a protein, bovine insulin. later that year, they reported sequences from sheep and pig, each of which showed a small number of differences from the bovine. even earlier, sequences of several polypeptide hormones had been worked out, and their similarities and differences had already caught the eye of evolutionists. from this tiny amount of data sprang the hope, considered unrealistic by many at the time, that the histories of all living organisms might be reconstructed. shortly thereafter, the notion that gene duplications were the source of most proteins was given a boost when the sequences of the alpha and beta chains of hemoglobin were reported to be more than 40 percent identical. by the 1960's, amino acid sequence analysis had taken hold as the major tool for determining the divergences of both creatures and their proteins. the obvious similarities of bacterial and eukaryotic enzyme sequences lent hope that the routes leading to all the major groups of organisms could be established, and the observation that proteins with different functions could have similar sequences showed that radical changes of function were possible. the paradigm that "all new proteins came from old proteins" became the dogma of the day. by the 1970's, the rna sequencing of certain rna moieties was almost routine, and the sequencing of numerous small subunit rrnas revealed unexpectedly that there were three domains of life, now referred to as archaea, bacteria and eukarya. the finding framed one of the major mysteries of all biology: which group came first and how are the others related to it? to this day the question has not been satisfactorily resolved. the advent of dna sequencing in the late 1970's ushered in a new era, the deluge of data making all previous work seem trivial, even if fundamental questions remained. the campaign in the 1980's to sequence the human genome changed the nature of biological inquiry in a major way. comparative genomics may indeed reveal the patterns of how the major life forms have evolved. among recent successes using the genomic approach has been the unraveling and intertwining of proteins involved in photosynthesis and nitrogen fixation and their spread through the prokaryotic world. on another front, the history of protein folds is being analyzed with surprising clarity. the technological advances that have made all this possible--computers, robotics, photochemistry, and much more--are as mind-numbing as the results. but where are we going? what do we want to know? although some of the evolutionary questions framed fifty years ago have been answered in part, many remain. what were the primordial proteins and how did they arise? what was the nature of the first cells? although sequence analysis alone may not tell all, it has given us a great beginning. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
computing life and global technologies (abstract only). the view &ldquo;biology is an informational science&rdquo; is now widely accepted&mdash;certainly catalyzed in part by the success of the human genome project. there are three levels of biological information: 1-dimensional information of dna, the 3-dimensional information of proteins, and the 4-dimensional (time variant) information of biological systems and networks. the key to deciphering biological information at each of these levels are the global technologies which analyze many genes, dnas or proteins at one time. i will discuss several new and pioneering global technologies for genomics and proteomics. information at each of these levels poses striking computational challenges, which will be discussed. the importance of the need for intimate interactions between biologists, computer scientists and mathematicians will also be discussed, as well as a new approach for teaching biology that may be effective for cross-disciplinary communication.
a bayesian approach to transcript estimation from gene array data: the beam technique. we present a new statistically optimal approach to estimate transcript levels and ratios from one or more gene array experiments. the bayesian estimation of array measurements (beam) technique uses a model of measurement noise and prior information to estimate biological expression levels. it provides a principled method to deal with negative expression level measurements, combine multiple measurements, and identify changes in expression level. beam is more flexible than existing techniques, because it does not assume a specific functional form for noise and prior models. rather, it uses a more accurate noise model developed from experimental data, a process we illustrate here using affymetrix yeast chips.