waashk/dblp huggingface dataset:
comprehensive statistical method for protein fold recognition. we present a protein fold recognition method that uses a comprehensive statistical interpretation of structural hidden markov models (hmms). the structure/fold recognition is done by summing the probabilities of all sequence-to-structure alignments conventionally, boltzmann statistics dictate that the optimal alignment can give an estimate of the lowest free energy of the sequence conformation imposed by the structural model. the alignment is optimized for a scoring function that is interpreted as a free energy of an amino acid in a structural environment. near-optimal alignments are ignored, regardless of how likely they might be compared to the optimal alignment. here we investigate an alternative view. a structure model can be seen as a statistical representation of an ensemble of similar structures. the optimal alignment is always the most probable, but sub-optimal alignments may have comparable probabilities. these sub-optimal alignments can be interpreted as optimal alignments to the &ldquo;other&rdquo; structures from the ensemble or optimal alignments under minor fluctuations in the scoring function. summing probabilities for all alignments gives an estimate of sequence-model compatibility. we have built a set of structural hmms for 188 protein structures, and have compared two methods for identifying the structure compatible with a sequence: by the optimal alignment probability and by the total probability. fold recognition by total probability was 40% more accurate than fold recognition by the optimal alignment probability.
haplotype phase inference. most of the information being collected on dna variation among people does not identify which of the two parents transmitted which of the two copies of each gene. even worse, the parent of origin is often scrambled for each single nucleotide polymorphism (snp) that is identified, so that each gene may be represented by hundreds of pairs of snp vectors or haplotypes. collection of a population sample of this kind of genotype data, however, does contain information about these haplotypes, and inference of the haplotype pairs from this kind of data is referred to has haplotype phase inference. the problem has a rich geometric representation, and has spawned a wealth of algorithms that span graph theoretic to bayesian approaches. good solutions to this problem are strongly motivated by the efforts seeking to identify genes that underlie complex genetic disorders. the latest efforts in this area will be described and reviewed.
on the predictive power of sequence similarity in yeast. perhaps the most direct way to infer functional linkage of proteins is through structural similarity. however, structure determination lags behind dna sequencing. here we show that sequence similarity based on nucleotide sequences alone between orfs in yeast is indicative of the corresponding genes being of the same functional group, having a similar gene expression pattern or of being involved in a protein-protein interaction. in particular, we compare the nucleotide sequences corresponding to the 6280 yeast orfs using blast, and then cluster them together using a simple neighbor-joining algorithm. this, in effect, gives us hierarchical clustering of 53 levels, where higher levels have bigger clusters. we compare the clustering to large databases that are not based a-priori on sequence information to get a notion of how well our clustering is correlated with this data. for functional annotation we use the sgd database that gives one of 540 annotations for about half the yeast genes. for all pairs that appear within a cluster, we test the hypothesis that almost all genes within the same cluster have the same function. we get very high percentage rates of correct annotation at the lower levels of the hierarchy, which decreases gradually at higher ones. from the results of the large scale gene expression experiments we generate a list of pairs of genes, whose expression is highly correlated (&nge;0.9). we then go over this list of pairs, and count how many of them are contained within a cluster as opposed to the expected number by a random model. we estimate the significance of our results using simulation, and get for all levels p-value&nle;&nle;0.001. the third type of data obtained from the protein-protein interaction database that is given as a list of airs of proteins involved in interaction. as before, we count how many pairs are contained within a cluster, and get much better results than expected by a random model, with p-values&nle;0.001 for almost all levels. in summary, we show that successful functional predictions and functional annotations can be applied at a genomic scale. this can be achieved by combining a naive hierarchical clustering method that creates sets of clusters at different levels of granularity with statistical validation tools.
computational structural proteomics and virtual ligand screening. large scale discovery of new human genes, gene families and isozymes creates an exciting biomedical opportunity. advanced modeling by homology techniques can be employed to generate 3d models for most of the interesting new gene family members. this opens many new opportunities for structural structure based functional annotation and molecular design. several key computational technologies enable structural protein modeling and rational drug design: sequence-structure relationships, multiple sequence alignments, threading molecular mechanics; global energy optimization; protein modeling by homology; structure based protein functional annotation (e.g. prediction of possible active sites, small molecule binding sites, protein-protein interaction sites, flexibility annotation); protein design and redesign using structure prediction algorithms; structural immunology, e.g. derivation and design of peptide sequence specific for a particular hla presenting molecule based on the hla structure; peptide-protein docking; protein-protein docking; small molecule docking and virtual ligand screening; cheminformatics algorithms and virtual chemistry.we have been developing the internal coordinate mechanics approach to structure prediction for the last 16 years. it is aimed at de novo prediction of large structural rearrangements. to achieve that goal an icm program has been developed and combined accurate energy functions with powerful global optimization algorithm in the internal coordinate space.the most recent developments include on-the-fly calculations of accurate poisson electrostatics using the efficient boundary element algorithm based on the analytical molecular surface. this allows to predict de novo a solution structure of a 23-residue peptide.new computational technology for virtual ligand screening allows to generate alternative receptor conformations and perform flexible docking of hundreds of thousands of virtual compounds to the binding site. the success of this technology is demonstrated on several benchmarks and in six experimental projects which tested the prediction results. for well defined binding pockets only about the initial compound set actually needs to be synthesized and tested. using icm docking and scoring technology we have identified new ligands in a number of cases, including cases in which a model was used instead of a crystallographic structure and a case in which protein-protein interaction has been targeted.the most interesting recent results tested experimentally include: the de novo design of novel antagonists of thyroid hormone receptor, for which no antagonists were known before and, consequently, no antagonist-bound structure was known; de novo design of ligands targeting ephrin-ephrin receptor interactions.
algorithms for phylogenetic footprinting. phylogenetic footprinting is a technique that identifies regulatory elements by finding unusually well conserved regions in a set of orthologous non-coding dna sequences from multiple species. in an earlier paper, we presented an exact algorithm that identifies the most conserved region of a set of sequences. here, we present a number of algorithmic improvements that produce a 1000 fold speedup over the original algorithm. we also show how prior knowledge can be used to identify weaker motifs, and how to handle data sets in which only an unknown subset of the sequences contain the regulatory element. each technique is implemented and successfully identifies a large number of known binding sites, as well as several highly conserved but uncharacterized regions.
a comparative analysis method for detecting binding sites in coding regions. while the problem of predicting transcription factor binding sites in a gene's promoter region has been extensively studied, binding sites located in coding regions are also crucial for regulating gene expression but are more difficult to detect. coding region binding sites are mostly involved in splicing regulation, but also in transcriptional and post-transcriptional regulation. we consider the problem of predicting such binding sites by comparative analysis. comparative analysis is based on the idea that functional sequences tend to evolve at slower rate than nonfunctional sequence, making unusually well conserved regions likely to be of interest. the difficulty in applying comparative analysis to the detection of binding sites located in coding sequence is that the whole sequence is under selective pressure, because it needs to code for a functional protein. we present a technique to distinguish between conservation due to constraints on the amino acid product and conservation due to constraints imposed by regulatory factors. more precisely, we show how to calculate the probability of observing a certain degree of conservation among the nucleotides of given set of orthologous codons, given a set of constraints on the amino acids they need to encode. the algorithms described are implemented in a program called cosmo, available at http://bio.cs.washington.edu. we ran cosmo on several genes known to contain exonic splicing enhancers and report the results.
the sequence of the human genome (abstract only). a consensus sequence of the euchromatic portion of human genome has been generated by the whole genome shot-gun sequencing method that was developed while sequencing the genomes of haemophilus influenzae and drosophila melanogaster. the 2.9 billion bp sequence, was generated over nine months from 27,271,853 high quality sequence reads (&nsim;5x coverage of the genome) from both ends of plasmid clones made from the dna of five individuals: three females and two males of african-american, asian-chinese, hispanic and caucasian ethnicity. the coverage of the genome in cloned dna represented by paired end-sequences exceeds 37x. two assembly methods, a whole genome assembly and a regional hybrid assembly were utilized, combining bac data from genbank with celera data. over 90 assemblies of 500,000 bp or greater and 2510 million bp or larger. analysis of the genome sequence reveals - 26,178 protein-encoding genes for which there is strong corroborating evidence and an additional 12,000 computationally derived genes with mouse homologues or other weak supporting evidence. comparative genomic analysis indicates vertebrate expansions of genes associated with neuronal function, tissue-specific developmental regulation, and in the hemostasis and immune systems. dna sequence comparisons among the five individuals provided locations of 2.6 million single nucleotide polymorphisms (snps). the haploid genomes of a randomly drawn pair of humans differ at a rate of one per 1,250 bp on average but there is marked heterogeneity in the level of polymorphism across the genome. only 0.75% of the snps led to possibly dysfunctional proteins.
tissue classification with gene expression profiles. constantly improving gene expression profiling technologies are expected to provide understanding and insight into cancer related cellular processes. gene expression data is also expected to significantly and in the development of efficient cancer diagnosis and classification platforms. in this work we examine two sets of gene expression data measured across sets of tumor and normal clinical samples one set consists of 2,000 genes, measured in 62 epithelial colon samples [1]. the second consists of &ap; 100,000 clones, measured in 32 ovarian samples (unpublished, extension of data set described in [26]). we examine the use of scoring methods, measuring separation of tumors from normals using individual gene expression levels. these are then coupled with high dimensional classification methods to assess the classification power of complete expression profiles. we present results of performing leave-one-out cross validation (loocv) experiments on the two data sets. employing svm [8], adaboost [13] and a novel clustering based classification technique. as tumor samples can differ from normal samples in their cell-type composition we also perform loocv experiments using appropriately modified sets of genes, attempting to eliminate the resulting bias. we demonstrate success rate of at least 90% in tumor vs normal classification, using sets of selected genes, with as well as without cellular contamination related members. these results are insensitive to the exact selection mechanism, over a certain range.
efficient extraction of mapping rules of atoms from enzymatic reaction data. extraction of mapping rules of atoms from enzymatic reaction data is useful for drug design, simulation of tracer experiments and consistency checking of pathway databases. most of previous methods for this problem are based on maximal common subgraph algorithms. in this paper, we propose a novel approach based on graph partition and graph isomorphism. we show that this problem is np-hard in general, but can be solved in polynomial time for wide classes of enzymatic reactions. we also present an o(n1.5) time algorithm for a special but fundamental class of reactions, where n is the maximum size of compounds appearing in a reaction. we develop practical polynomial time algorithms in which the morgan algorithm is used for computing the normal form of a graph, where it is known that the morgan algorithm works correctly for most chemical structures. computational experiments are performed for these practical algorithms using the chemical reaction data stored in the kegg/ligand database. the results of computational experiments suggest that practical algorithms are useful in many cases.
on approximation algorithms for local multiple alignment. this paper studies the local multiple alignment problem, which is also known as the general consensus patterns problem. local multiple alignment is, given protein or dna sequences, to locate a region (i.e., a substring) of fixed length from each sequence so that the score determined from the set of regions is optimized. we consider the following scoring schemes. the score indicating the average information content, the score defined by li et al, and the sum-of-pairs score we prove that multiple local alignment is np-hard under each of these scoring schemes. in addition, we prove that multiple local alignment is apx-hard under the average information content scoring. it implies that unless p = np there is no polynomial time algorithm whose worst case approximation error can be arbitrarily specified (precisely, a polynomial time approximation scheme). several related theoretical results are provided. we also made computational experiments on approximation algorithms for local multiple alignment under the average information content scoring. the results suggest that the gibbs sampling algorithm proposed by lawrence et al. is the best.
algorithms for identifying boolean networks and related biological networks based on matrix multiplication and fingerprint function. due to the recent progress of the dna microarray technology, a large number of gene expression profile data are being produced. how to analyze gene expression data is an important topic in computational molecular biology several studies have been done using the boolean network as a model of a genetic network this paper proposes efficient algorithms for identifying boolean networks of bounded indegree and related biological networks, where identification of a boolean network can be formalized as a problem of identifying many boolean functions simultaneously. for the identification of a boolean network, an o(mnd+1) time naive algorithm and a simple o(mnd) time algorithm are known, where n denotes the number of nodes, m denotes the number of examples, and d denotes the maximum indegree. this paper presents an improved o(mw-2nd + mnd+w-3) time monte-carlo type randomized algorithm, where w is the exponent of matrix multiplication (currently, w < 2376). the algorithm is obtained by combining fast matrix multiplication with the randomized fingerprint function for string matching. although the algorithm and its analysis are simple, the result is non-trivial and the technique can be applied to several related problems.
predicting the beta-helix fold from protein sequence data. a method is presented that uses &bgr;-strand interactions to predict the right-handed &bgr;-helix super-secondary structural motif in protein sequences. a program called betawrap implements this method, and is shown to score known &bgr;-helices above non-&bgr;-helices in the protein data bank in cross-validation. it is demonstrated that betawrap learns each of the seven known scop &bgr;-helix families, when trained on the the known &bgr;-helices from outside the family. betawrap also predicts many bacterial proteins of unknown structure that play a role in human infectious disease to &bgr;-helices; in particular, these proteins serve as virulence factors, adhesins and toxins in bacterial pathogenesis, and include cell surface proteins from chlamydia and the intestinal bacterium helicobacter pylori. the computational method used here may generalize to other &bgr; structures for which strand topology and profiles of residue accessibility are well conserved.
trilogy: discovery of sequence-structure patterns across diverse proteins. we describe a new computer program, trilogy, for the automated discovery of sequence-structure patterns in proteins. trilogy implements a pattern discovery algorithm that begins with an exhaustive analysis of flexible three-residue patterns; a subset of these patterns are selected as seeds for an extension process in which longer patterns are identified. a key feature of the method is explicit treatment of both the sequence and structure components of these motifs: each trilogy pattern is a pair consisting of a sequence pattern and a structure pattern. matches to both these component patterns are identified independently, allowing the program to assign a significance score to each sequence-structure pattern that assesses the degree of correlation between the corresponding sequence and structure motifs. trilogy identifies several thousand high-scoring patterns that occur across protein families. these include both previously identified and novel motifs. we expect that these sequence-structure patterns will be useful in predicting protein structure from sequence, annotating newly determined protein structures, and identifying novel motifs of potential functional or structural significance.
a combinatorial approach to protein docking with flexible side-chains. rigid body docking approaches are not sufficient to predict the structure of a protein complex from the unbound (native) structures of the two proteins. accounting for side&mdash;chain flexibility is an important step towards fully flexible protein docking. this work describes an approach that allows conformational flexibility for the side&mdash;chains while keeping the protein backbone rigid. starting from candidates created by a rigid docking algorithm, we demangle the side&mdash;chains of the docking site, thus creating reasonable approximations of the true complex structure. these structures are ranked with respect to the binding free energy. we present two new techniques for side&mdash;chain demangling. both approaches are based on a discrete representation of the side&mdash;chain conformational space by the use of a rotamer library. this leads to a combinatorial optimization problem. for the solution of this problem we propose a fast heuristic approach and an exact, albeit slower method using branch&mdash;&&mdash;cut techniques. as a test set we use the unbound structures of three proteases and the corresponding protein inhibitors. for each of the examples the highest&mdash;ranking conformation produced was a good approximation of the true complex structure.
information processing by cells and biologists (abstract only). the core agenda of post-wwii molecular biology has been defined as the molecular understanding of how genetic information was transmitted and read out (see for example stent 1968), and, by the 1950's, the analogy between the tape in a turing machine and the linear sequence of nucleotides in dna was apparent to both computer scientists and biologists. in the early 21st century, it may be that molecular biology can fruitfully return to these roots, by recasting part of its agenda in terms of the need to understand how biological information is processed. in a somewhat more modern formulation, cells can be though of as machines that process and make decisions on three kinds of information: 1) information stored in the genome 2) information about intracellular events (for example from heckpoint mechanisms) and 3) information external to the cell. in many cases the machinery that cells use to make decisions is reasonably well understood at a qualitative level. however, in no case do we possess a corresponding quantitative understanding, and, reflecting this, nor are we very capable of predicting the outcomes of perturbations to the genome, the internal workings of the cell, or its external environment. one path to understanding the behavior of these ensembles of components clearly lies in construction of mechanism-based quantitative models representing cellular processes. building such models requires solution of numerous computational and experimental biological challenges. i will detail some of these. another path may involve computation on the qualitative biological knowledge that now exists. expert biologists reason on this qualitative information to make statements about the consequences of perturbations, but expert systems that do the same in the main do not exist. here, although the need is clear, the relative opacity (to me) of much of the seemingly relevant computer science literature has made it more difficult to figure out first steps. finally, note that information theory (shannon 1948) has its roots in the 20th century need to understand transmission of electrical signals through channels. it is not immediately clear that the representations of biological processes used by biologists map well to concepts that come from this theory. to give only one example, one is hard pressed to define or find, inside a cell that is processing signals from the outside, either the signal or the &ldquo;bits&rdquo; (tukey, 1946) that might make it up. there may be thus be an opportunity here for new theory to guide thinking and further experiment.