waashk/dblp huggingface dataset:
edit distance between two rna structures. arc-annotated sequences are useful in representiug the structural information of rna sequences. typically, rna secondary and tertiary structures could be represented by a set of nested arcs and a set of crossing arcs, respectively. as the specified rna functions are determined by the specified molecular confirmation and therefore the specified secondary and tertiary structures, the comparison between rna secondary and tertiary structures have received much attention recently. in this paper, we propose the notion of edit distance to measure the similarity between two rna secondary and tertiary structures, by incorporating the various edit operations performing on both bases and arcs (base-pairs). several algorithms are presented to compute the edit distance two rna sequences with various arc structures and under various score schemes, either exactly or approximately. preliminary experimental tests confirm that our definition of edit distance and the computation model are among the most reasonable ones ever studied in the literature.
finding anchors for genomic sequence comparison. recent sequencing of the human and other mammalian genomes has brought about the necessity to align them, to identify and characterize their commonalities and differences. programs that align whole genomes generally use a seed-and-extend technique, starting from exact or near-exact matches and selecting a reliable subset of these, called anchors, and then filling in the remaining portions between the anchors using a combination of local and global alignment algorithms, but their choices for the parameters so far have been primarily heuristic. we present a statistical framework and practical methods for selecting a set of matches that is both sensitive and specific and can constitute a reliable set of anchors for a one-to-one mapping of two genomes from which a whole-genome alignment can be built. starting from exact matches, we introduce a novel per-base repeat annotation, the $z$-score, from which noise and repeat filtering conditions are explored. dynamic programming-based chaining algorithms are also evaluated as context-based filters. we apply the methods described here to the comparison of two progressive assemblies of the human genome, ncbi build 28 and build 34 http://genome.ucsc.edu), and show that a significant portion of the two genomes can be found in selected exact matches, with very limited amount of sequence duplication.
pseudoknots in rna secondary structures. rna molecules are sequences of nucleotides that serve as more than mere intermediaries between dna and proteins, e.g. as catalytic molecules. computational prediction of rna secondary structure is among the few structure prediction problems that can be solved satisfactory in polynomial time. most work has been done to predict structures that do not contain pseudoknots. allowing pseudoknots introduce modelling and computational problems. in this paper we consider the problem of predicting rna secondary structure when certain types of pseudoknots are allowed. we first present an algorithm that in time &ogr;(n5) and space &ogr;(n3) predicts the secondary structure of an rna sequence of length n in a model that allows certain kinds of pseudoknots. we then prove that the general problem of predicting rna secondary structure containing pseudoknots is np-complete for a large class of reasonable models of pseudoknots.
the role of computational chemistry in translating genomic information into bioactive small molecules (abstract only). although genomic information provides many potential targets for drug discovery, the challenge is to convert this information into drugs that cure human disease. workers in computer assisted molecular design and chemometrics have developed a number of techniques to aid this process. examples include selecting diverse compounds for high throughput screening, designing universal or targeted combinatorial libraries, and using a variety of computational techniques to forecast binding affinitiy and bioavailability of compounds. this lecture will summarize recent advances in these areas.
evolutionary change in developmental genetic networks. the different combinations of genes that are active in different cells control the development and diversity of multicellular organisms. the codes that control this process, written in both cis-regulatory and protein-coding dna sequence, are poorly understood. decoding those sequences will require many experimental and bioinformatic approaches. one approach that will be useful is discovering the nodal control points that change when genetic networks evolve to change form and function. recent discoveries will be described on the molecular changes in a network that modifies limb number during arthropod evolution. another important experimental approach useful to decoding is the determination of precise gene expression patterns during model organism development, including which expression patterns are conserved and which are variable. a new approach has been developed that involves assigning spectral barcodes to many different nascent transcripts in developing animal nuclei. this will allow the rapid determination of precise spatial domains of transcriptional activation, and the construction of virtual embryos with complete maps of combinatorial gene expression. 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
wrap-and-pack: a new paradigm for beta structural motif recognition with application to recognizing beta trefoils. a method is presented that uses β-strand interactions at both the sequence and the atomic level, to predict the beta-structural motifs in protein sequences. a program called wrap-and-pack implements this method, and is shown to recognize β-trefoils, an important class of globular β-structures, in the protein data bank with 92% specificity and 92.3% sensitivity in cross-validation. it is demonstrated that wrap-and-pack learns each of the ten known scop β-trefoil families, when trained primarily on β-structures that are not β-trefoils, together with 3d structures of known β-trefoils from outside the family. wrap-and-pack also predicts many proteins of unknown structure to be β-trefoils. the computational method used here may generalize to other β-structures for which strand topology and profiles of residue accessibility are well conserved.
the evolutionary capacity of protein structures. in nature, one finds large collections of different protein sequences exhibiting roughly the same three-dimensional structure, and this observation underpins the study of structural protein families. in studying such families at a global level, a natural question to ask is how close to "optimal" the native sequences are in terms of their energy. we therefore define and compute the evolutionary capacity of a protein structure as the total number of sequences whose energy in the structure is below that of the native sequence. an important aspect of our definition is that we consider the space of all possible protein sequences, i.e. the exponentially large set of all strings over the 20-letter amino acid alphabet, rather than just the set of sequences found in nature.in order to make our approach computationally feasible, we develop randomized algorithms that perform approximate enumeration in sequence space with provable performance guarantees. we draw on the area of rapidly mixing markov chains, by exhibiting a connection between the evolutionary capacity of proteins and the number of feasible solutions to the knapsack problem. this connection allows us to design an algorithm for approximating the evolutionary capacity, extending a recent result of morris and sinclair on the knapsack problem. we present computational experiments that show the method to be effective in practice on large collections of protein structures. in addition, we show how to use approximations to the evolutionary capacity to compute a statistical mechanics notion of "evolutionary temperature" on sequence space.
revealing protein structures: a new method for mapping antibody epitopes. a recent idea for determining the three-dimensional structure of a protein uses antibody recognition of surface structure and random peptide libraries to map antibody epitope combining sites. antibodies that bind to the surface of the protein of interest can be used as "witnesses" to report the structure of the protein as follows: proteins are composed of linear polypeptide chains that come together in complex spatial folding patterns to create the native protein structures and these folded structures form the binding sites for the antibodies. short amino acid probe sequences, which bind to the active region of each antibody, can be selected from random sequence peptide libraries. these probe sequences can often be aligned to discontinuous regions of the one-dimensional target sequence of a protein. such alignments indicate how pieces of the protein sequence must be folded together in space and thus provide valuable long-range constraints for solving the overall 3-d structure. this new approach is applicable to the very large number of proteins that are refractory to current approaches to structure determination and has the advantage of requiring very small amounts of the target protein. the binding site of an antibody is a surface, not just a linear sequence, so the epitope mapping alignment problem is outside the scope of classical string alignment algorithms, such as smith-waterman. we formalize the alignment problem that is at the heart of this new approach, prove that the epitope mapping alignment problem is np-complete, and give some initial results using a branch-and-bound algorithm to map two real-life cases.
comparing sequence scaffolds. the dna sequence assembler we built for the whole genome shotgun assembly of the human genome, utilizes end-reads of inserts to order and orient assembled contigs into scaffolds for which the distances between consecutive contigs are statistically characterized. we consider the problem of comparing two such scaffolds. applications include comparison of two distinct assemblies for mutual confirmation, and comparison of scaffold assemblies of bacs to determine a whole genome tiling of the bacs. we formalize the problem and develop efficient algorithms for a number of variations of the problem, the essential result being a sparse algorithm that refines gap estimates based on the overlap evidence.
a multi-expert system for the automatic detection of protein domains from sequence information. we describe a novel method for detecting the domain structure of a protein from sequence information alone. the method is based on analyzing multiple sequence alignments that are derived from a database search. multiple measures are defined to quantify the domain information content of each position along the sequence, and are combined into a single predictor using a neural network. the output is further smoothed and post-processed using a probabilistic model to predict the most likely transition or boundary positions between domains. the method was assessed using the domain definitions in scop for proteins of known structures and was compared to several other existing methods. our method improves significantly over the best method available, the semi-manual pfam domain database, while being fully automatic. our method can also be used to verify domain partitions based on structural data. few examples of predicted domain definitions and alternative partitions, as suggested by our method, are also discussed.
reconstructing reticulate evolution in species: theory and practice. we present new methods for reconstructing reticulate evolution of species due to events such as horizontal transfer or hybrid speciation; both methods are based upon extensions of wayne maddison's approach in his seminal 1997 paper. our first method is a polynomial time algorithm for constructing phylogenetic networks from two gene trees contained inside the network. we allow the network to have an arbitrary number of reticulations, but we limit the reticulation in the network so that the cycles in network are node-disjoint ("galled"); we prove accuracy guarantees for our first method by presenting a formal characterization of the set of gene trees defined by a species network. our second method is a polynomial time algorithm for constructing networks with one reticulation, where we allow for errors in the estimated gene trees. using simulations, we demonstrate improved performance of this method over both neighbornet and maddison's method.
fast and simple character classes and bounded gaps pattern matching, with application to protein searching. the problem of fast searching of a pattern that contains classes of characters and bounded size gaps (cbg) in a text has a wide range of applications, among which a very important one is protein pattern matching (for instance, one prosite protein site is associated with the cbg [rk] &mdash; x(2, 3) &mdash; [de] &mdash; x(2, 3) &mdash; y, where the brackets match any of the letters inside, and x(2, 3) a gap of length between 2 and 3). currently, the only way to search a cbg in a text is to convert it into a full regular expression (re). however, a re is more sophisticated than a cbg, and searching it with a re pattern matching algorithm complicates the search and makes it slow. this is the reason why we design in this article two new practical cbg matching algorithms that are much simpler and faster than all the re search techniques. the first one looks exactly once at each text character. the second one does not need to consider all the text characters and hence it is usually faster than the first one, but in bad cases may have to read the same text character more than once. we then propose a criterion based on the form of the cbg to choose a-priori the fastest between both. we performed many practical experiments using the prosite database, and all them show that our algorithms are the fastest in virtually all cases.
simulating boolean circuits on a dna computer. we demonstrate that dna computers can simulate boolean circuits with a small overhead. boolean circuits embody the notion of massively parallel signal processing and are frequently encountered in many parallel algorithms. many important problems such as sorting, integer arithmetic, and matrix multiplication are known to be computable by small size boolean circuits much faster than by ordinary sequential digital computers. this paper shows that dna chemistry allows one to simulate large semi-unbounded fan-in boolean circuits with a logarithmic slowdown in computation time. also, for the class nc$^1$, the slowdown can be reduced to a constant. in this algorithm we have encoded the inputs, the boolean and gates, and the or gates to dna oligonucleotide sequences. we operate on the gates and the inputs by standard molecular techniques of sequence-specific annealing, ligation, separation by size, limited amplification, sequence-specific cleavage, and detection by size. preliminary biochemical experiments on a small test circuit have produced encouraging results. further confirmatory experiments are in progress.
determining contact energy function for continuous state models of globular protein conformations. one of the approaches to protein structure prediction is to obtain energy functions which can recognize the native conformation of a given sequence among a zoo of conformations. the discriminations can be done by assigning the lowest energy to the native conformation, with the guarantee that the native is in the zoo. well-adjusted functions, then, can be used in the search for other (near-) natives. here the aim is the discrimination at relatively high resolution (rmsd difference between the native and the closest nonnative is around 1 &aring;) by pairwise energy potentials. the results show that the potential can be trained to discriminate between the native conformation of one protein as the (near-) global minimum, and other nonnatives, including energy-minimized ones (or local minima). this potential function is able to identify the native conformation of another protein, too.
set association analysis of snp case-control and microarray data. common heritable diseases ("complex traits") are assumed to be due to multiple underlying susceptibility genes. while genetic mapping methods for mendelian disorders have been very successful, the search for genes underlying complex traits has been difficult and often disappointing. one of the reasons may be that most current gene mapping approaches are still based on conventional methodology of testing one or a few snps at a time. here we demonstrate a simple strategy that allows for the joint analysis of multiple disease-associated snps in different genomic regions. our set-association method combines information over snps by forming sums of relevant single-marker statistics. this approach successfully addresses the "curse of dimensionality" problem - too many variables should be estimated with a comparatively small number of observations. we also extend our method to microarray expression data, where expression levels for large numbers of genes should be compared between two tissue types. in applications to experimental expression data our approach turned out to be highly efficient.
applications of generalized pair hidden markov models to alignment and gene finding problems. hidden markov models (hmms) have been successfully applied to a variety of problems in molecular biology, ranging from alignment problems to gene finding and annotation. alignment problems can be solved with pair hmms, while gene finding programs rely on generalized hmms in order to model exon lengths. in this paper we introduce the generalized pair hmm (gphmm), which is an extension of both pair and generalized hmms. we show how gphmms, in conjunction with approximate alignments, can be used for cross-species gene finding, and describe applications to dna-cdna and dna-protein alignment. gphmms provide a unifying and probabilistically sound theory for modeling these problems.
picking alignments from (steiner) trees. the application of needleman-wunsch alignment techniques to biological sequences is complicated by two serious problems when the sequences are long: the running time, which scales as the product of the lengths of sequences, and the difficulty in obtaining suitable parameters that produce meaningful alignments. the running time problem is often corrected by reducing the search space, using techniques such as banding, or chaining of high scoring pairs. the parameter problem is more difficult to fix, partly because the probabilistic model, which needleman-wunsch is equivalent to, does not capture a key feature of biological sequence alignments, namely the alternation of conserved blocks and seemingly unrelated non-conserved segments. we present a solution to the problem of designing efficient search spaces for pair hidden markov models that align biological sequences by taking advantage of their associated features. our approach leads to an optimization problem, for which we obtain a 2-approximation algorithm, and that is based on the construction of manhattan networks, which are close relatives of steiner trees. we describe the underlying theory and show how our methods can be applied to alignment of dna sequences in practice, succesfully reducing the viterbi algorithm search space of alignment phmms by three orders of magnitude.
gene functional classification from heterogeneous data. in our attempts to understand cellular function at the molecular level, we must be able to synthesize information from disparate types of genomic data. we consider the problem of inferring gene functional classifications from a heterogeneous data set consisting of dna microarray expression measurements and phylogenetic profiles from whole-genome sequence comparisons. we demonstrate the application of the support vector machine (svm) learning algorithm to this functional inference task. our results suggest the importance of exploiting prior information about the heterogeneity of the data. in particular, we propose an svm kernel function that is explicitly heterogeneous. we also show how to use knowledge about heterogeneity to aid in feature selection.
resolution of haplotypes and haplotype frequencies from snp genotypes of pooled samples. recent efforts to characterize genetic variation indicate that humans share large chromosomal blocks, along which little to no recombination is observable. thus, on a segment-by-segment basis, only a handful of haplotypes account for most human genotypes. currently, the challenge of registering haplotypes and their frequencies is met by genotyping individuals one by one, a process which is overall resource intensive. instead, we propose utilizing the ability of current genotyping technologies to pool dna samples and output allele frequencies of snp markers. we enable inference of haplotypes and haplotype frequencies from such pooled data, by novel computational methods. this strategy harnesses the economics of pooling for the task of haplotyping, potentially offering a 10-20-fold saving in genotyping reactions performed.we show that a small number of pools can be used to accurately and cost-effectively reconstruct a haplotype block and determine haplotype frequencies.
comparing rna expression patterns of embryos. in situ staining of a target mrna at several time points during the development of a d. melanogaster embryo gives one a detailed spatio-temporal view of the expression pattern of a given gene. we have developed algorithms and software for analyzing a database of such images with the goal of being able to identify coordinately expressed genes and further our understanding of cis-regulatory control during embryogenesis. our approach combines measures of similarity at both the global and local levels, based on gaussian mixture model (gmm) decompositions. at the global level, the observed distribution of pixel values is quantized using an adaptive gmm decomposition and then quantized images are compared using mutual information. at the local level, we decompose quantized images into 2-dimensional gaussian kernels or "blobs" and then develop a blob-set matching method to search for the best matching traits in different pattern-images. a hybrid scoring method is proposed to combine both global and local matching results. we further develop a voting scheme to search for genes with similar spatial staining patterns over the time course of embryo development. to evaluate the effectiveness of our approach, we compare it with several global image matching schemes and a controlled vocabulary method. we then apply our method to 4400 images of 136 genes to detect potentially co-regulated genes that have similar spatio-temporal patterns, using expert-annotation to evaluate our results.
mutation-tolerant protein identification by mass-spectrometry. database search in tandem mass spectrometry is a powerful tool for protein identification. high-throughput spectral acquisition raises the problem of dealing with genetic variation and peptide modifications within a population of related proteins. a method that cross-correlates and clusters related spectra in large collections of uncharacterized spectra (i.e from normal and diseased individuals) would be extremely valuable in functional proteomics. this problem is far from being simple since very similar peptides may have very different spectra. we introduce a new notion of spectral similarity that allows one to identify related spectra even if the corresponding peptides have multiple modifications/mutations. based on this notion we developed a new algorithm for mutation-tolerant database search as well as a method for cross-correlating related uncharacterized spectra. the paper describes this new approach and its applications in functional proteomics.