waashk/dblp huggingface dataset:
using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures. we present a novel approach for studying the kinetics of protein folding. the framework has evolved from robotics motion planning techniques called probabilistic roadmap methods (prms) that have been applied in many diverse fields with great success. in our previous work, we used a prm-based technique to study protein folding pathways of several small proteins and obtained encouraging results. in this paper, we describe how our motion planning framework can be used to study protein folding kinetics. in particular, we present a refined version of our prm-based framework and describe how it can be used to produce potential energy landscapes, free energy landscapes, and many folding pathways all from a single roadmap which is computed in a few hours on a desktop pc. results are presented for 14 proteins. our ability to produce large sets of unrelated folding pathways may potentially provide crucial insight into some aspects of folding kinetics, such as proteins that exhibit both two-state and three-state kinetics, that are not captured by other theoretical techniques.
provably sensitive indexing strategies for biosequence similarity search. the field of algorithms for pairwise biosequence similarity search is dominated by heuristic methods of high efficiency but uncertain sensitivity. one reason that more formal string matching algorithms with sensitivity guarantees have not been applied to biosequences is that they cannot directly find similarities that score highly under substitution score functions such as the dnapam-tt [20], pam [9], or blosum [12] families of matrices. we describe a general technique, score simulation, to map ungapped similarity search problems using these score functions into the problem of finding pairs of strings that are close in hamming space. score simulation leads to indexing schemes for biosequences that permit efficient ungapped similarity searches with formal guarantees of sensitivity using arbitrary score functions. in particular, we introduce the lsh-all-pairs-sim algorithm for finding local similarities in large biosequence collections and show that it is both computationally feasible and sensitive in practice.
designing seeds for similarity search in genomic dna. large-scale comparison of genomic dna is of fundamental importance in annotating functional elements of genomes. to perform large comparisons efficiently, blast (methods: companion methods enzymol 266 (1996) 460, j. mol. biol. 215 (1990) 403, nucleic acids res. 25(17) (1997) 3389) and other widely used tools use seeded alignment, which compares only sequences that can be shown to share a common pattern or ''seed'' of matching bases. the literature suggests that the choice of seed substantially affects the sensitivity of seeded alignment, but designing and evaluating seeds is computationally challenging. this work addresses the problem of designing a seed to optimize performance of seeded alignment. we give a fast, simple algorithm based on finite automata for evaluating the sensitivity of a seed in a markov model of ungapped alignments, along with extensions to mixtures and inhomogeneous markov models. we give intuition and theoretical results on which seeds are good choices. finally, we describe mandala, a software tool for seed design, and show that it can be used to improve the sensitivity of alignment in practice.
finding motifs using random projections. pevzner and sze [23] considered a precise version of the motif discovery problem and simultaneously issued an algorithmic challenge: find a motif m of length 15, where each planted instance differs from m in 4 positions. whereas previous algorithms all failed to solve this (15,4)-motif problem. pevzner and sze introduced algorithms that succeeded. however, their algorithms failed to solve the considerably more difficult (14,4)-, (16,5)-, and (18,6)-motif problems. we introduce a novel motif discovery algorithm based on the use of random projections of the input's substrings. experiments on simulated data demonstrate that this algorithm performs better than existing algorithms and, in particular, typically solves the difficult (14,4)-, (16,5)-, and (18,6)-motif problems quite efficiently. a probabilistic estimate shows that the small values of d for which the algorithm fails to recover the planted (l, d)-motif are in all likelihood inherently impossible to solve. we also present experimental results on realistic biological data by identifying ribosome binding sites in prokaryotes as well as a number of known transcriptional regulatory motifs in eukaryotes.
an analytic approach to significance assessment in local sequence alignment with gaps. a detailed study of the smith-waterman alignment algorithm is performed in order to find an analytical approach to the problem of assessing the statistical significance of local alignments with gaps. the significance is shown to be given in terms of an eigenvalue equation which captures the dynamics of the much simpler global alignment algorithm. this eigenvalue equation is then explicitly solved for a simple scoring system and the resulting significance estimations are verified by a comparison to extensive numerical simulations
rapid significance estimation in local sequence alignment with gaps. in order to assess the significance of sequence alignments it is crucial to know the distribution of alignment scores of pairs of random sequences. for gapped local alignment it is empirically known that the shape of this distribution is of the gumbel form. however, the determination of the parameters of this distribution is a computationally very expensive task. we present a new algorithmic approach which allows to estimate the more important of the gumbel parameters at least five times faster than the traditional methods. actual runtimes of our algorithm between less than a second and a few minutes on a workstation bring significance estimation into the realm of interactive applications.
stochastic roadmap simulation: an efficient representation and algorithm for analyzing molecular motion. classic techniques for simulating molecular motion, such as the monte carlo and molecular dynamics methods, generate individual motion pathways one at a time and spend most of their time trying to escape from the local minima of the energy landscape of a molecule. their high computational cost prevents them from being used to analyze many pathways. we introduce stochustic roadmap sirrrcllation (srs), a new approach for exploring the kinetics of molecular motion by simultaneously examining multiple pathways encoded compactly in a graph, called a roadmap. a roadmap is computed by sampling a molecule's conformation space at random. the computation does not suffer from the localminima problem encountered with existing methods. each path in the roadmap represents a potential motion pathway and is associated with a probability indicating the likelihood that the molecule follows this pathway. by viewing the roadmap as a markov chain, we can efficiently compute kinetic properties of molecular motion over the entire molecular energy landscape. we also prove that, in the limit, srs converges to the same distribution as monte carlo simulation. to test the effectiveness of our approach, we apply it to the computation of the transmission coefficients for protein folding, an important order parameter that measures the "kinetic distance" of a protein's conformation to its native state our computational studies show that srs obtains more accurate results and achieves several orders- of- magnitude reduction in computation time, compared with monte carlo simulatio.
optimal amnesic probabilistic automata or how to learn and classify proteins in linear time and space. statistical modeling of sequences is a central paradigm of machine learning that finds multiple uses in computational molecular biology and many other domains. the probabilistic automata typically built in these contexts are subtended by uniform, fixed-memory markov models. in practice, such automata tend to be unnecessarily bulky and computationally imposing both during their synthesis and use. in [8], much more compact, tree-shaped variants of probabilistic automata are built which assume an underlying markov process of variable memory length. in [3, 4], these variants, called probabilistic suffix trees (psts) were successfully applied to learning and prediction of protein families. the process of learning the automaton from a given training set s of sequences requires &thgr; (ln2) worst-case time, where n is the total length of the sequences in s and l is the length of a longest substring of s to be considered for a candidate state in the automaton. once the automaton is built, predicting the likelihood of a query sequence of m characters may cost time &thgr; (m2) in the worst case. the main contribution of this paper is to introduce automata equivalent to psts but having the following properties: learning the automaton takes o (n) time. prediction of a string of m symbols by the automaton takes o (m) time. along the way, the paper presents an evolving learning sheme, and addresses notions of empirical probability and related efficient computation,possibly a by-product of more general interest.
monotony of surprise and large-scale quest for unusual words. the problem of characterizing and detecting recurrent sequence patterns such as substrings or motifs and related associations or rules is variously pursued in order to compress data, unveil structure, infer succinct descriptions, extract and classify features, etc. in molecular biology, exceptionally frequent or rare words in bio-sequences have been implicated in various facets of biological function and structure. the discovery, particularly on a massive scale, of such patterns poses interesting methodological and algorithmic problems, and often exposes scenarios in which tables and synopses grow faster and bigger than the raw sequences they are meant to encapsulate. in previous study, the ability to succinctly compute, store, and display unusual substrings has been linked to a subtle interplay between the combinatorics of the subwords of a word and local monotonicities of some scores used to measure the departure from expectation. in this paper, we carry out an extensive analysis of such monotonicities for a broader variety of scores. this supports the construction of data structures and algorithms capable of performing global detection of unusual substrings in time and space linear in the subject sequences, under various probabilistic models.
dna sequence evolution with neighbor-dependent mutation. we introduce a model of dna sequence evolution which can account for biases in mutation rates that depend on the identity of the neighboring bases. an analytic solution for this class of models is developed by adopting well-known methods of nonlinear dynamics. results are presented for the cpg-methylation-deamination process which dominates point substitutions in vertebrates. the dinucleotide frequencies generated by the model (using empirically obtained mutation rates) match the overall pattern observed in non-coding dna. a web-based tool has been constructed to compute single- and dinucleotide frequencies for arbitrary neighbor-dependent mutation rates. also provided is the backward procedure to infer the mutation rates using maximum likelihood analysis given the observed single- and dinucleotide frequencies. reasonable estimates of the mutation rates can be obtained very efficiently, using generic non-coding dna sequences as input, after masking out long homonucleotide subsequences. our method is much more convenient and versatile to use than the traditional method of deducing mutation rates by counting mutation events in carefully chosen sequences. more generally, our approach provides a more realistic but still tractable description of non-coding genomic dna, and may be used as a null model for various sequence analysis applications.
regulatory element detection using correlation with expression (abstract only). we present a new computational method for discovering cis- regulatory elements which circumvents the need to cluster genes based on their expression profiles. based on a model in which upstream motifs contribute additively to the expression level of a gene, it requires a single genome-wide set of expression ratios and the upstream sequence for each gene, and outputs statistically significant motifs. analysis of publicly available expression data for sac charomyes cerevisiae reveals several new putative regulatory elements, some of which plausibly control the early, transient induction of genes during sporulation. known motifs generally have high statistical significance.
a new approach to sequence comparison: normalized sequence alignment. the smith-waterman algorithm for local sequence alignment is one of the most important techniques in computational molecular biology. this ingenious dynamic programming approach was designed to reveal the highly conserved fragments by discarding poorly conserved initial and terminal segments. however, the existing notion of local similarity has a serious flaw: it does not discard poorly conserved intermediate segments. the smith-waterman algorithm finds the local alignment with maximal score but it is unable to find local alignment with maximum degree of similarity (e.g., maximal percent of matches). moreover, there is still no efficient algorithm that answers the following natural question: do two sequences share a (sufficiently long) fragment with more than 70% of similarity? as a result, the local alignment sometimes produces a mosaic of well-conserved fragments artificially connected by poorly-conserved or even unrelated fragments. this may lead to problems in comparison of long genomic sequences and comparative gene prediction as recently pointed out by zhang et al., 1999 [33]. in this paper we propose a new sequence comparison algorithm (normalized local alignment) that reports the regions with maximum degree of similarity. the algorithm is based on fractional programming and its running time is &ogr;(n2 log n). in practice, normalized local alignment is only 3-5 times slower than the standard smith-waterman algorithm.
recent advances on the manipulation of single biomolecules. over the last ten years, a number of new approaches have emerged that have made it possible for scientists to mechanically manipulate individual molecules. these methods are proving themselves quite powerful to investigate the molecular mechanisms underlying many dynamic biochemical processes. because molecules are studied one at a time, single molecule manipulation techniques avoid the ensemble average characteristic of bulk studies. this feature is particularly useful to follow complex dynamic processes in time where the presence of multiple species in solution blurs the dynamical description of the system. moreover, many processes in the cell are known to be mechanical in nature and mechanical force is one of the "products" of the reaction. it follows that forces applied to the molecules undergoing these processes can be used to alter the extent and in some cases even the fate of the reactions, thus helping to reveal the molecular mechanisms by which force is generated in them. in this presentation, i will illustrate the use of optical tweezers with three different examples taken from my own research.
gene tree reconstruction and orthology analysis based on an integrated model for duplications and sequence evolution. gene tree and species tree reconstruction, orthology analysis and reconciliation, are problems important in multigenome-based comparative genomics and biology in general. in the present paper, we advance the frontier of these areas in several respects and provide important computational tools. first, exact algorithms are given for several probabilistic reconciliation problems with respect to the probabilistic gene evolution model, previously developed by the authors. until now, those problems were solved by mcmc estimation algorithms. second, we extend the gene evolution model to the gene sequence evolution model, by including sequence evolution. third, we develop mcmc algorithms for the gene sequence evolution model that, given gene sequence data allows: (1) orthology analysis, reconciliation analysis, and gene tree reconstruction, w.r.t. a species tree, that balances a likely/unlikely reconciliation and a likely/unlikely gene tree and (2) species tree reconstruction that balance a likely/unlikely reconciliation and a likely/unlikely gene trees. these mcmc algorithms take advantage of the exact algorithms for the gene evolution model. we have successfully tested our dynamical programming algorithms on real data for a biogeography problem. the mcmc algorithms perform very well both on synthetic and biological data.
identifying conserved gene clusters in the presence of orthologous groups. current biological evidence suggests a correlation between the function and the position of genes in chromosomes. examples include operon structure in prokaryotic genomes and similar expression patterns of neighboring genes in some eukaryotic genomes. in this paper, we present a new model and algorithm for identifying conserved gene clusters from pairwise genome comparison. this generalizes a recent model called "gene teams." a gene team is a set of orthologous genes that appear in two or more species, possibly in a different order yet with the distance of adjacent genes in the team for each chromosome always no more than a certain threshold. we remove the constraint in the original model that each gene must have a unique copy in the chromosomes, and thus allow the analysis on complex prokaryotic or eukaryotic genomes with extensive paralogs. our algorithm runs in o(mn) time and uses o(m+n) space, where m and n are the number of common genes in each chromosomes. we used this approach to study two bacterial genomes, e. coli and b. subtilis and successfully identified 85 conserved clusters, including clusters containing uncharacterized genes and a large cluster consisting of 21 ribosomal proteins. our implementation is publicly available at http://euler.slu.edu/~goldwasser/cogteams/.
on de novo interpretation of tandem mass spectra for peptide identification. the correct interpretation of tandem mass spectra is a difficult problem, even when it is limited to scoring peptides against a database. de novo sequencing is considerably harder, but critical when sequence databases are incomplete or not available. in this paper we build upon earlier work due to dancik et al., and chen et al. to provide a dynamic programming algorithm for interpreting de novo spectra. our method can handle most of the commonly occurring ions, including a; b; y, and their neutral losses. additionally, we shift the emphasis away from sequencing to assigning ion types to peaks. in particular, we introduce the notion of core interpretations, which allow us to give confidence values to individual peak assignments, even in the absence of a strong interpretation. finally, we introduce a systematic approach to evaluating de novo algorithms as a function of spectral quality. we show that our algorithm, in particular the core-interpretation, is robust in the presence of measurement error, and low fragmentation probability.
haplotypes and informative snp selection algorithms: don't block out information. it is widely hoped that variation in the human genome will provide a means of predicting risk of a variety of complex, chronic diseases. a major stumbling block to the successful identification of association between human dna polymorphisms (snps) and variability in risk of complex diseases is the enormous number of snps in the human genome (4,9). the large number of snps results in unacceptably high costs for exhaustive genotyping, and so there is a broad effort to determine ways to select snps so as to maximize the informativeness of a subset.in this paper we contrast two methods for reducing the complexity of snp variation: haplotype tagging, i.e. typing a subset of snps to identify segments of the genome that appear to be nearly unrecombined (haplotype blocks), and a new block-free model that we develop in this report. we present a statistic for comparing haplotype blocks and show that while the concept of haplotype blocks is reasonably robust there is substantial variability among block partitions. we develop a measure for selecting an informative subset of snps in a block free model. we show that the general version of this problem is np-hard and give efficient algorithms for two important special cases of this problem.
discovering local structure in gene expression data: the order-preserving submatrix problem. this paper concerns the discovery of patterns in gene expression matrices, in which each element gives the expression level of a given gene in a given experiment. most existing methods for pattern discovery in such matrices are based on clustering genes by comparing their expression levels in all experiments, or clustering experiments by comparing their expression levels for all genes. our work goes beyond such global approaches by looking for local patterns that manifest themselves when we focus simultaneously on a subset g of the genes and a subset t of the experiments. specifically, we look for order-preserving submatrices (opsms), in which the expression levels of all genes induce the same linear ordering of the experiments (we show that the opsm search problem is np-hard in the worst case). such a pattern might arise, for example, if the experiments in t represent distinct stages in the progress of a disease or in a cellular process, and the expression levels of all genes in g vary across the stages in the same way.we define a probabilistic model in which an opsm is hidden within an otherwise random matrix. guided by this model we develop an efficient algorithm for finding the hidden opsm in the random matrix. in data generated according to the model the algorithm recovers the hidden opsm with very high success rate. application of the methods to breast cancer data seems to reveal significant local patterns.our algorithm can be used to discover more than one opsm within the same data set, even when these opsms overlap. it can also be adapted to handle relaxations and extensions of the opsm condition. for example, we may allow the different rows of g x t to induce similar but not identical orderings of the columns, or we may allow the set t to include more than one representative of each stage of a biological process.
lymphocyte turnover in hiv-1 infection and the role of the thymus in siv infection. we investigated the dynamics of lymphocyte turnover in normal subjects as well as in hiv-1-infected patients using a novel labeling technique based on the administration of deuterium-containing glucose. a new mathematical model was also used to interpret the results. this approach provided direct determination of lymphocyte proliferation and death rates. we believe our findings convincingly demonstrate the increased turnover (3-6 fold) of both cd4 and cd8 lymphocytes in hiv-1 infection. furthermore, we also noted that the heightened t-cell turnover reverted toward normal upon effective combination antiretroviral therapy. collectively, these data show that the lymphocyte depletion seen in aids is not a consequence of a t-cell regenerative failure.we have also assessed the role of thymus in contributing to t lymphocyte homeostasis with and without siv infection. upon thymectomy in rhesus macaques, we noted a very gradual decline in the number of recent thymic emigrants as measured by the number of t-cell receptor excision circles. these results suggest that the normal thymic output in monkeys is small, and that recent thymic emigrants typically have a prolonged lifespan. we have also found relatively little impact of thymectomy on the outcome of siv infection. again, these findings indicate that thymus does not play a major role in the lymphocyte depletion observed in siv or hiv infection.