waashk/dblp huggingface dataset:
a nmr-spectra-based scoring function for protein docking. a well studied problem in the area of computational molecular biology is the so-called protein-protein docking problem (ppd) that can be formulated as follows: given two proteins a and b that form a protein complex, compute the 3d-structure of the protein complex ab. protein docking algorithms can be used to study the driving forces and reaction mechanisms of docking processes. they are also able to speed up the lenghty process of experimental structure elucidation of protein complexes by proposing potential structures. in this paper, we are discussing a variant of the ppd-problem where the input consists of the tertiary structures of a and b plus an unassigned 1h-nmr spectrum of the complex ab. we present a new scoring function for evaluating and ranking potential complex structures produced by a docking algorithm. the scoring function computes a &ldquo;theoretical&rdquo; 1h-nmr spectrum for each tentative complex structure and subtracts the calculated spectrum from the experimental spectrum. the absolute areas of the difference spectra are then used to rank the potential complex structures. in contrast to formerly published approaches (e.g. morelli et. al. [38]) we do not use distance constraints (intermolecular noe constraints). we have tested the approach with the bound conformations of four protein complexes whose three-dimensional structures are stored in the pdb data bank [5] and whose 1h-nmr shift assignments are available from the bmrb database (biomagresbank [47]). in all examples, the new scoring function produced very good rankings of the structures. the best result was obtained for an example, where all standard scoring functions failed completely. here, our new scoring function achieved an almost perfect separation between good approximations of the true complex structure and false positives. unfortunately, the number of complexes with known structure and available spectra is very small. nevertheless, these experiments indicate that scoring functions based on comparisons of one- or multi-dimensional nmr spectra might be a good instrument to improve the reliability and accuracy of docking predictions and perhaps also of protein structure predictions (threading).
model-based inference of haplotype block variation. the uneven recombination structure of human dna has been highlighted by several recent studies. knowledge of the haplotype blocks generated by this phenomenon can be applied to dramatically increase the statistical power of genetic mapping. several criteria have already been proposed for identifying these blocks, all of which require haplotypes as input. we propose a comprehensive statistical model of haplotype block variation and show how the parameters of this model can be learned from haplotypes and/or unphased genotype data. using real-world snp data, we demonstrate that our approach can be used to resolve genotypes into their constituent haplotypes with greater accuracy than previously known methods.
simultaneous identification of duplications and lateral transfers. this paper introduces a combinatorial model that incorporates duplication events as well as lateral gene transfer events (a.k.a. horizontal gene transfer events). to the best of our knowledge, this is the first such model containing both of these events. a so-called dt-scenario is used to explain differences between a gene tree t and species trees s. the model is biologically as well as mathematically sound. among other biological considerations, the model respects the partial order of evolution implied by s by demanding that the dt-scenarios are "acyclic". we present fixed parameter tractable algorithms that count the minimum number of duplications and lateral transfers, and more generally can compute the set of pairs (t,d) where d is the minimum number of duplications required by any explanation that requires t lateral transfers. this allows us to also compute a weighted parsimony score. we also show how gene loss events can be incorporated into our model. we also give an $np$-completeness proof which suggests that the intractability is due to the demand that the dt-scenarios be acyclic. when this condition is removed, we can show that the problem is computable in polynomial time via dynamic programming. by generating "synthetic" gene and species trees via a birth-death process, we explored the capacity of our algorithms to faithfully reconstruct the actual number of events taken place. the results are positive.
reconstructing distances in physical maps of chromosomes with nonoverlapping probes. we present a new method for reconstructing the distances between probes in physical maps of chromosomes constructed by hybridizing pairs of clones under the so-called sampling-without-replacement protocol. in this protocol, which is simple, inexpensive, and has been used to successfully map several organisms, equal-length clones are hybridized against a clone-subset called the probes. the probes are chosen by a sequential process that is designed to generate a pairwise-nonoverlapping subset of the clones. we derive a likelihood function on probe spacings and orders for this protocol under a natural model of hybridization error, and describe how to reconstruct the most likely spacing for a given order under this objective using continuous optimization. the approach is tested on simulated data and real data from chromosome vi of aspergillus nidulans. on simulated data we recover the true order and close to the true spacing; on the real data, for which the true order and spacing is unknown, we recover a probe order differing significantly from the published one. to our knowledge this is the first practical approach for computing a globally-optimal maximum-likelihood reconstruction of interprobe distances from clone-probe hybridization data.
joint classifier and feature optimization for cancer diagnosis using gene expression data. recent research has demonstrated quite convincingly that accurate cancer diagnosis can be achieved by constructing classifiers that are designed to compare the gene expression profile of a tissue of unknown cancer status to a database of stored expression profiles from tissues of known cancer status. this paper introduces the jcfo, a novel algorithm that uses a sparse bayesian approach to jointly identify both the optimal nonlinear classifier for diagnosis and the optimal set of genes on which to base that diagnosis. we show that the diagnostic classification accuracy of the proposed algorithm is superior to a number of current state-of-the-art methods in a full leave-one-out cross-validation study of two widely used benchmark datasets. in addition to its superior classification accuracy, the algorithm is designed to automatically identify a small subset of genes (typically around twenty in our experiments) that are capable of providing complete discriminatory information for diagnosis. focusing attention on a small subset of genes is not only useful because it produces a classifier with good generalization capacity, but also because this set of genes may provide insights into the mechanisms responsible for the disease itself. a number of the genes identified by the jcfo in our experiments are already in use as clinical markers for cancer diagnosis; some of the remaining genes may be excellent candidates for further clinical investigation. if it is possible to identify a small set of genes that is indeed capable of providing complete discrimination, inexpensive diagnostic assays might be widely deployable in clinical settings.
101 optimal pdb structure alignments: a branch-and-cut algorithm for the maximum contact map overlap problem. structure comparison is a fundamental problem for structural genomics. a variety of structure comparison methods were proposed and several protein structure classification servers e.g., scop, dali, cath, were designed based on them, and are extensively used in practice. this area of research continues to be very active, being energized bi-annually by the casp folding competitions, but despite the extraordinary international research effort devoted to it, progress is slow. a fundamental dimension of this bottleneck is the absence of rigorous algorithmic methods. a recent excellent survey on structure comparison by taylor et.al. [23] records the state of the art of the area: in structure comparison, we do not even have an algorithm that guarantees an optimal answer for pairs of structures &hellip; in this paper we provide the first rigorous algorithm for structure comparison. our method is based on developing an effective integer linear programming (ip) formulation of protein structure contact maps overlap (cmo), and a branch-and-cut strategy that employs lower-bounding heuristics at the branch nodes. our algorithms identified a gallery of optimal and near-optimal structure alignments for pairs of proteins from the protein data bank with up to 80 amino acids and about 150 contacts each &mdash; problems of instance size of about 300. although these sizes also reflect our current limitations, these are the first provable optimal and near-optimal algorithms in the literature for a measure of structure similarity which sees extensive practical use. at the heart of our success in finding optimal alignments is a reduction of the cmo optimization to the maximum independent set (mis) problem on special graphs. for cmo instances of size 300, the corresponding mis graph instance contains about 10,000 nodes. while our algorithms are able to solve to optimality mis problem of these sizes, the known optimal algorithms for the mis on general graphs can at present only solve instances with up to a few hundred nodes. this is the first effective use of ip methods in protein structure comparison; the biomolecular structure literature contains only one other effective ip method devoted to rna comparison, due to lenhof et.al. [18]. the hybrid heuristic approach that worked well for providing lower bounds in the branch and cut algorithm was tried on large proteins in a test set suggested by jeffrey skolnick. it involved 33 proteins classified into four families: flavodoxin-like fold chey-related, plastocyanin, tim barrel, and ferratin. out of the set of all 528 pairwise structure alignments, we have validated the clustering with a 98.7% accuracy (1.3% false negatives and 0% false positives).
extracting structural information using time-frequency analysis of protein nmr data. high-throughput, data-directed computational protocols for structural genomics (or proteomics) are required in order to evaluate the protein products of genes for structure and function at rates comparable to current gene-sequencing technology. to develop such methods, new algorithms are required that can quickly extract significantly more structural information from sparse experimental data. this paper presents a new class of signal processing algorithms for nuclear magnetic resonance (nmr) structural biology, based on time-frequency analysis of chemical shift dynamics. a novel approach to multidimensional nmr analysis is proposed in which the data are interpreted in the time-frequency domain, as opposed to the traditional frequency domain. time-frequency analysis (tfa) exposes behavior orthogonal to the magnetic coherence transfer pathways, thus affording new avenues of nmr discovery. an implementation yielding new biophysical results is discussed. in particular, we demonstrate the heretofore unknown presence of through-space inter-atomic distance information within 15n-edited heteronuclear single-quantum coherence(15n hsqc) data. a biophysical model explains these results, and is supported by further experiments on simulated spectra.
large a polynomial-time nuclear vector replacement algorithm for automated nmr resonance assignments. high-throughput nmr structural biology can play an important role in structural genomics. we report an automated procedure for high-throughput nmr resonance assignment for a protein of known structure, or of an homologous structure. these assignments are a prerequisite for probing protein-protein interactions, protein-ligand binding, and dynamics by nmr. assignments are also the starting point for structure determination and refinement. a new algorithm, called nuclear vector replacement (nvr) is introduced to compute assignments that optimally correlate experimentally-measured nh residual dipolar couplings (rdcs) to a given a priori whole-protein 3d structural model. the algorithm requires only uniform 15n-labelling of the protein, and processes unassigned hn-15n hsqc spectra, hn-15n rdcs, and sparse hn-hn noe's dnns), all of which can be acquired in a fraction of the time needed to record the traditional suite of experiments used to perform resonance assignments. nvr runs in minutes and efficiently assigns the (hn,15n) backbone resonances as well as the dnns of the 3d \nfif-noesy spectrum, in o(n3) time. the algorithm is demonstrated on nmr data from a 76-residue protein, human ubiquitin, matched to four structures, including one mutant (homolog), determined either by x-ray crystallography or by different nmr experiments (without rdcs). nvr achieves an average assignment accuracy of over 90%. we further demonstrate the feasibility of our algorithm for different and larger proteins, using nmr data for hen lysozyme (129 residues, 98% accuracy) and streptococcal protein g (56 residues, 95% accuracy), matched to a variety of 3d structural models. finally, we extend nvr to a second application, 3d structural homology detection, and demonstrate that nvr is able to identify structural homologies between proteins with remote amino acid sequences using a database of structural models.
phase-independent rhythmic analysis of genome-wide expression patterns. we introduce a model-based analysis technique for extracting and characterizing rhythmic expression profiles from genome-wide dna microarray hybridization data. these patterns are clues to discovering rhythmic genes implicated in cell-cycle, circadian, and other biological processes. the algorithm, implemented in a program called rage (rhythmic analysis of gene expression), decouples the problems of estimating a pattern's periodicity and phase. our algorithm is linear-time in frequency and phase resolution, an improvement over previous quadratic-time approaches. unlike previous approaches, rage uses a true distance metric for measuring expression profile similarity, based on the hausdorff distance. this results in better clustering of expression profiles for rhythmic analysis. the confidence of each frequency estimate is computed using z-scores. we demonstrate that rage is superior to other techniques on synthetic and actual dna microarray hybridization data. we also show how to replace the discretized phase search in our method with an exact (combinatorially precise) phase search, resulting in a faster algorithm with no complexity dependence on phase resolution.
checking homogeneity of motifs' distribution in heterogenous sequences. studying the distribution of a motif along sequences may help to understand its biological function, or to detect regions of interest. a statistical model is needed to assess the significancy of the observed distribution. we propose an heterogenous compound poisson process to model the possibility of overlap between occurrences and some heterogeneity of the sequence a priori known. the parameters estimation procedure is described and tests of homogenous sub-models are proposed. we also consider the detection of rich regions using either cumulated distances or moving intervals, via an homogenization technique. illustrations of the method are given with applications to bacterial genomes.
a complete and effective move set for simplified protein folding. we present new lowest energy configurations for several large benchmark problems for the two-dimensional hydrophobic-hydrophilic model. we found these solutions with a generic implementation of tabu search using an apparently novel set of transformations that we call pull moves. our experiments show that our algorithm can find these best solutions in 3 to 14 hours, on average. pull moves appear quite effective and may also be useful for other local search algorithms for the problem. additionally, we prove that pull moves are complete; that is, any pair of valid configurations are mutually reachable through a sequence of pull moves. our implementation was developed with the human-guided search (hugs) middleware, which allows rapid development of interactive optimization systems.
invited: prediction of protein function. a genome sequence embodies the potential life of an organism, but implementation of genetic information depends on the functions of the proteins that it encodes. many proteins of known sequence and even of known structure present challenges to understanding their function. in some cases genes responsible for diseases have been identified but their specific functions are unknown. annotation of a genome involves assignment of functions to gene products, in most cases on the basis of amino acid sequence alone, in the absence of experimental information. protein structures from structural genomics projects are invaluable for function assignment. nevertheless, prediction of protein function remains a difficult problem. some methods provide reasonable guesses, but no method is foolproof. moreover, even when it is possible to ascribe a particular function to a gene product, the protein may have multiple functions. an underlying problem has been that function is in many cases an ill-defined concept.
a class of edit kernels for svms to predict translation initiation sites in eukaryotic mrnas. the prediction of translation initiation sites (tiss) in eukaryotic mrnas has been a challenging problem in computational molecular biology. in this paper, we present a new algorithm to recognize tiss with a very high accuracy. our algorithm includes two novel ideas. first, we introduce a class of new sequence-similarity kernels based on string edit, called the edit kernels, for use with support vector machines (svms) in a discriminative approach to predict tiss. the edit kernels are simple and have significant biological and probabilistic interpretations. second, we convert the region of an input mrna sequence downstream to a putative tis into an amino acid sequence before applying svms to avoid the high redundancy in the genetic code. the algorithm has been implemented and tested on previously published data. our experimental results on real mrna data show that both ideas improve the prediction accuracy greatly and our method performs significantly better than those based on neural networks and svms with polynomial kernels or salzberg kernel.
haplotype reconstruction from snp alignment. in this paper we describe a method for statistical reconstruction of haplotypes from a set of aligned snp fragments. we consider the case of a pair of homologous human chromosomes, one from the mother and the other from the father. after fragment assembly and snp detection, we wish to reconstruct the two haplotypes of the parents. given a set of snp sites inferred from the assembly alignment, we wish to divide the fragment set into two subsets, each of which represents one chromosome. our method is based on a statistical model of sequencing errors, compositional information and haplotype memberships.we calculate probabilities of different haplotypes conditional on the alignment. due to computational complexity, we first determine phases for neighboring snps. then we connect them and construct haplotype segments. also we compute the accuracy or confidence of the reconstructed haplotypes. we discuss other issues such as alternative methods, parameter estimation, computational efficiency, and relaxation of assumptions.
combining pairwise sequence similarity and support vector machines for remote protein homology detection. one key element in understanding the molecular machinery of the cell is to understand the meaning, or function, of each protein encoded in the genome. a very successful means of inferring the function of a previously unannotated protein is via sequence similarity with one or more proteins whose functions are already known. currently, one of the most powerful such homology detection methods is the svm-fisher method of jaakkola, diekhans and haussler (ismb 2000). this method combines a generative, profile hidden markov model (hmm) with a discriminative classification algorithm known as a support vector machine (svm). the current work presents an alternative method for svm-based protein classification. the method, svm-pairwise, uses a pairwise sequence similarity algorithm such as smith-waterman in place of the hmm in the svm-fisher method. the resulting algorithm, when tested on its ability to recognize previously unseen families from the scop database, yields significantly better remote protein homology detection than svm-fisher, profile hmms and psi-blast.
a novel ensemble-based scoring and search algorithm for protein redesign, and its application to modify the substrate specificity of the gramicidin synthetase a phenylalanine adenylation enzyme. realization of novel molecular function requires the ability to alter molecular complex formation. enzymatic function can be altered by changing enzyme-substrate interactions via modification of an enzyme's active site. a redesigned enzyme may either perform a novel reaction on its native substrates or its native reaction on novel substrates. a number of computational approaches have been developed to address the combinatorial nature of the protein redesign problem. these approaches typically search for the global minimum energy conformation among an exponential number of protein conformations. we present a novel algorithm for protein redesign, which combines a statistical mechanics-derived ensemble-based approach to computing the binding constant with the speed and completeness of a branch-and-bound pruning algorithm. in addition, we developed an efficient deterministic approximation algorithm, capable of approximating our scoring function to arbitrary precision. in practice, the approximation algorithm decreases the execution time of the mutation search by a factor of ten. to test our method, we examined the phe-specific adenylation domain of the non-ribosomal peptide synthetase gramicidin synthetase a (grsa-phea). ensemble scoring, using a rotameric approximation to the partition functions of the bound and unbound states for grsa-phea, is first used to predict binding of the wildtype protein and a previously described mutant (selective for leucine), and second, to switch the enzyme specificity toward leucine, using two novel active site sequences computationally predicted by searching through the space of possible active site mutations. the top scoring in silico mutants were created in the wetlab and dissociation / binding constants were determined by fluorescence quenching. these tested mutations exhibit the desired change in specificity from phe to leu. our ensemble-based algorithm which flexibly models both protein and ligand using rotamer-based partition functions, has application in enzyme redesign, the prediction of protein-ligand binding, and computer-aided drug design.