waashk/dblp huggingface dataset:
algorithms for identifying protein cross-links via tandem mass spectrometry. cross-linking technology combined with tandem mass spectrometry (ms-ms) is a powerful method that provides a rapid solution to the discovery of protein-protein interactions and protein structures. we studied the problem of detecting cross-linked peptides and cross-linked amino acids from tandem mass spectral data. our method consists of two steps: the first step finds two protein subsequences whose mass sum equals a given mass measured from the mass spectrometry; and the second step finds the best cross-linked amino acids in these two peptide sequences that are optimally correlated to a given tandem mass spectrum. we designed fast and space-efficient algorithms for these two steps, and implemented and tested them on experimental data of cross-linked hemoglobin proteins.
a compression algorithm for dna sequences and its applications in genome comparison. we present a lossless compression algorithm, gen-compress, for dna sequences, based on searching for approximate repeats. our algorithm achieves the best compression ratios for benchmark dna sequences, comparing to other dna compression programs [3, 7]. significantly better compression results show that the approximate repeats are one of the main hidden regularities in dna sequences. we then describe a theory of measuring the relatedness between two dna sequences. we propose to use d(x, y) = 1 &mdash; k(x) - k(x|y)/k(xy to measure the distance of any two sequences, where k stands for kolmogorov complexity [5]. here, k(x) - k(x|y) is the mutual information shared by x and y. but mutual information is not a distance, there is no triangle inequality. the distance d(x, y) is symmetric. it also satisfies the triangle inequality, and furthermore, it is universal [4]. it has not escaped our notice that the distance measure we have postulated can be immediately used to construct evolutionary trees from dna sequences, especially those that cannot be aligned, such as complete genomes. with more and more genomes sequenced, constructing trees from genomes becomes possible [1, 2, 6, 8]. kolmogorov complexity is not computable. we use gencompress to approximate it. we present strong experimental support for this theory, and demonstrate its applicability by correctly constructing a 16s (18s) rrna tree, and a whole genome tree for several species of bacteria. larger scale experiments are underway at the university of waterloo, with very promising results.
universal dna tag systems: a combinatorial design scheme. custom-designed dna arrays offer the possibility of simultaneously monitoring thousands of hybridization reactions these arrays show great potential for many medical and scientific applications such as polymorphism analysis and genotyping. relatively high costs are associated with the need to specifically design and synthesize problem specific arrays. recently, an alternative approach was suggested that utilizes fixed, universal arrays. this approach presents an interesting design problem&mdash;the arrays should contain as many probes as possible, while minimizing experimental errors caused by cross-hybridization. we use a simple thermodynamic model to cast this design problem in a formal mathematical framework. employing new combinatorial ideas, we derive an efficient construction for the design problem, and prove that our construction is near-optimal.
significance of inter-species matches when evolutionary rate varies. we develop techniques to estimate the statistical significance of gap-free alignments between two genomic dna sequences, using human-mouse alignments as an example. the sequences are assumed to be sufficiently similar that some but not all of the neutrally evolving regions (i.e., those under no evolutionary constraint) can be reliably aligned. our goal is to model the situation in which the neutral rate of evolution, and hence the extent of the aligning intervals, varies across the genome. in some cases, this permits the weaker of two matches to be judged as less likely to have arisen by chance, provided it lies in a genomic interval with a high level of background divergence. we employ a hidden markov model to capture variations in divergence rates, and assign probability values to gap-free alignments using techniques related to those used for the same purpose by blast. our methods are illustrated in detail using a 1.49 mb genomic region. preliminary results using all of human chromosome 22 indicate that these techniques will work for the entire human genome.
learning multiple evolutionary pathways from cross-sectional data. we introduce a mixture model of trees to describe evolutionary processes that are characterized by the accumulation of permanent genetic changes. the basic building block of the model is a directed weighted tree that generates a probability distribution on the set of all patterns of genetic events. we present an em-like algorithm for learning a mixture model of k trees and show how to determine k with a maximum likelihood approach. as a case study we consider the accumulation of mutations in the hiv-1 reverse transcriptase that are associated with drug resistance. the fitted model is statistically validated as a density estimator and the stability of the model topology is analyzed. we obtain a generative probabilistic model for the development of drug resistance in hiv that agrees with biological knowledge. further applications and extensions of the model are discussed.
an optimal procedure for gap closing in whole genome shotgun sequencing. tettelin et. al. proposed a new method for closing the gaps in whole genome shotgun sequencing projects. the method uses a multiplex pcr strategy in order to minimize the time and effort required to sequence the dna in the missing gaps. this procedure has been used in a number of microbial sequencing projects including streptococcus pneumoniae and other bacteria. in this paper we describe a theoretical framework for this problem and propose an improved method that guarantees to minimize the number of steps involved in the gap closure procedures. in given particular collection of n/2 dna fragments we describe a strategy that requires. 0.75 log n work in eight parallel rounds of experiment closely matching a corresponding lower bound 0.5 log of n
efficient exact value computation and applications to biosequence analysis. like other fields of life sciences, bioinformatics has turned to capture biological phenomena through probabilistic models, and to analyse these models using statistical methodology. a central computational problem in applying useful statistical procedures such as various hypothesis testing procedures is the computation of p-values. in this paper, we devise a branch and bound approach to efficient exact p-value computation, and apply it to a likelihood ratio test in a frequency table setting. by recursively partitioning the sample domain and bounding the statistic we avoid the explicit exhaustive enumeration of all possible outcomes which is currently carried by the standard statistical packages. the convexity of the test statistic is further utilized to confer additional speed-up.empirical evaluation demonstrates a reduction in the computational complexity of the algorithm, even in worst case scenarios, significantly extending the practical range for performing the exact test. we also show that speed-up greatly improves the sparser the underlying null hypothesis is; that computation precision actually increases with speed-up; and that computation time is very moderately affected by the magnitude of the computed p-value. these qualities make our algorithm an appealing alternative to the exhaustive test, the χ2 asymptotic approximation and monte carlo samplers in the respective regimes.the proposed method is readily extendible to other tests and test statistics of interest. we survey several examples of established biosequence analysis methods, where small sample size and sparseness do occur, and to which our computational framework could be applied to improve performance. we briefly demonstrate this with two applications, measuring binding site positional correlations in dna, and detecting compensatory mutation events in functional rna.
phylogenetically and spatially conserved word pairs associated with gene expression changes in yeasts. background. transcriptional regulation in eukaryotes is often multifactorial, involving multiple transcription factors binding to the same transcription control region (e.g., upstream activating sequences and enhancers), and to understand the regulatory content of eukaryotic genomes it is necessary to consider the co-occurrence and spatial relationships of individual binding sites. the identification of sequences conserved among related species (often known as phylogenetic footprinting) has been successfully used to identify individual transcription factor binding sites. here, we extend this concept of functional conservation to higher-order features of transcription control regions involved in the multifactorial control of gene expression.results. we used the genome sequences of four yeast species of the genus saccharomyces to identify sequences potentially involved in multifactorial control of gene expression. we found 1,117 potential regulatory "templates": pairs of hexameric sequences that are jointly conserved in transcription regulatory regions and also exhibit non-random relative spacing. many of the individual sequences in these templates correspond to known transcription factor binding sites, and the sets of genes containing a particular template in their transcription control regions tend to be differentially expressed in conditions where the corresponding transcription factors are known to be active.conclusions. the incorporation of both joint conservation and spacing constraints of sequence pairs predicts groups of target genes that were specific for common patterns of gene expression. our work suggests that positional information, especially the relative spacing between transcription factor binding sites, may represent a common organizing principle of transcription control regions.
finding motifs for insufficient number of sequences with strong binding to transcription facto. finding motifs is an important problem in computational biology. our paper makes two major contributions to this problem. firstly, we better characterize the types of problem instances that cannot be solved by most existing methods of finding motifs. secondly, we introduce a different method, which is shown to succeed for various problem instances for which popular existing methods fail.most existing computational methods to finding motifs are based on the strong-signal model wherein only strong-signal sequences (i.e. those that are known to contain binding sites very similar to the motif) are considered as input and weak-signal sequences (i.e. those do not contain any sub-string similar to the motif) are disregarded.buhler and tompa have studied the limitations of methods based on the strong-signal model. they characterized the problem instances for which the motif is unlikely to be found in terms of the number of input (strong-signal) sequences needed under the assumption that each input sequence contains exactly one binding site. they further gave a method to calculate the minimum number of input sequences required.we re-characterize the limitations of the strong-signal model in terms of the minimum total number of binding sites, rather than the minimum number of strong-signal sequences, required to be in the input data set. we use a probability matrix to represent a motif instead of a string pattern to calculate the minimum total number of binding sites required. this new characterization is shown to be more general and realistic.next, we introduce a more general and realistic energy-based model, which considers all available sequences (including weak-signal sequences) with varying degrees of binding strength to the transcription factors (as measured experimentally by observed color intensity). given varying degrees of binding strength, our model can consider sequences ranging from those that contain more than one binding site to those that are weak sequences. by treating sequences with different degrees of binding strength differently, we develop a heuristic algorithm called ebmf (energy-based motif finding algorithm) using an em-like approach to find motifs under our model. this ebmf algorithm can find motifs for data sets that do not even have the required minimum number of binding sites as previously derived for the strong-signal model. our algorithm compares favorably with common motif-finding programs alignace and meme, which are based on the strong-signal model. in particular, for some simulated and real data sets, our algorithm finds the motif when both alignace and meme fail to do so.
multiple maxima of likelihood in phylogenetic trees: an analytic approach. maximum likelihood (ml) is a widely used criterion for selecting optimal evolutionary trees. however, little is known on the nature of the likelihood surface for trees, especially as to the frequency of multiple optima. we initiate an analytic study for identifying sequences that generate multiple optima. we report a new approach to calculating ml directly, which we have used to find large families of sequences that have multiple optima, including sequences with a continuum of optimal points. such datasets are best supported by different (two or more) phylogenies that vary significantly in their timings of evolutionary events some standard biological processes can lead to data with multiple optima and consequently the field needs further investigation. our results imply that hill climbing techniques, as currently implemented in various software packages, cannot guarantee to find the global ml point, even if it is unique.
maximum likelihood on four taxa phylogenetic trees: analytic solutions. maximum likelihood (ml) is increasingly used as an optimality criterion for selecting evolutionary trees (felsenstein, 1981), but finding the global optimum is a hard computational task. because no general analytic solution is known, numeric techniques such as hill climbing or expectation maximization (em), are used in order to find optimal parameters for a given tree. so far, analytic solutions were derived only for the simplest model - three taxa, two state characters, under a molecular clock (mc). quoting ziheng yang (2000), who initiated the analytic approach, "this seems to be the simplest case, but has many of the conceptual and statistical complexities involved in phylogenetic estimation".in this work, we give analytic solutions for four taxa, two state characters under a molecular clock. the change from three to four taxa incurs a major increase in the complexity of the underlying algebraic system, and requires novel techniques and approaches. we start by presenting the general maximum likelihood problem on phylogenetic trees as a constrained optimization problem, and the resulting system of polynomial equations. in full generality, it is infeasible to solve this system, therefore specialized tools for the mc case are developed.four taxa rooted trees have two topologies -- the fork (two subtrees with two leaves each) and the comb (one subtree with three leaves, the other with a single leaf). we combine the ultrametric properties of mc trees with the hadamard conjugation (hendy and penny, 1993) to derive a number of topology dependent identities. employing these identities, we substantially simplify the system of polynomial equations. we finally use tools from algebraic geometry (e.g. grobner bases, ideal saturation, resultants) and employ symbolic algebra software to obtain closed form analytic solutions (expressed parametrically in the input data) for the fork topology, and analytic solutions for the comb. we show that in contrast to the fork, the comb has no closed form solutions (expressed by radicals in the input data). in general, four taxa trees can have multiple ml points (steel, 1994, chor et. al., 2001). in contrast, we can now prove that under the mc assumption, both the fork and the comb topologies have a unique (local and global) ml point.
designing rna structures: natural and artificial selection. messenger rna (mrna) sequences serve as templates for proteins according to the triplet code, in which each of the 43 = 64 different codons (sequences of three consecutive nucleotide bases) in rna either terminate transcription or map to one of the 20 different amino acids (or residues) which build up proteins. because there are more codons than residues, there is inherent redundancy in the coding. certain residues (e.g. tryptophan) have only a single corresponding codon, while other residues (e.g. arginine) have as many as six corresponding codons. this freedom implies that the number of possible rna sequences coding for a given protein grows exponentially in the length of the protein.thus nature has wide latitude to select among mrna sequences which are informationally equivalent, but structurally and energetically divergent. in this paper, we explore how nature takes advantage of this freedom, and how to algorithmically design structures more energetically favorable than have been built through natural selection. in particular:natural selection, -- we perform the first large-scale computational experiment comparing the stability of mrna sequences from a variety of organisms to random synonymous sequences which respect the codon preferences of the organism. this experiment was conducted on over 27,000 sequences from 34 microbial species with 36 genomic structures. we provide evidence that in all genomic structures highly stable sequences are disproportionately abundant, and in 19 of 36 cases highly unstable sequences are disproportionately abundant. this suggests that the stability of mrna sequences is subject to natural selection.artificial selection -- motivated by these biological results, we examine the algorithmic problem of designing the most stable and unstable mrna sequences which code for a target protein. we give a polynomial-time dynamic programming solution to the most stable sequence problem (mssp), which is asymptotically no more complex than secondary structure prediction. we show that the corresponding least stable sequence problem (lssp) is np-complete, and develop two heuristics for the construction of such sequences.we have implemented these algorithms, and present experimental results placing the high/low stability sequences in context with both wildtype and random encodings. our implementation has already been applied to the design of rna "code-words" creating little or no secondary structure in rna computing [1, 12], and we anticipate a variety of other applications of this work to sequence design problems [16].
fast recovery of evolutionary trees with thousands of nodes. we present a novel distance-based algorithm for evolutionary tree reconstruction. our algorithm reconstructs the topology of a tree with n leaves in o(n2) time using o(n) working space. in the general markov model of evolution the algorithm recovers the topology successfully with (1 &mdash; &ogr;(1)) probability from sequences with polynomial length in n. moreover, for almost all trees, our algorithm achieves the same success probability on polylogarithmic sample sizes. the theoretical results are supported by simulation experiments involving trees with 500, 1895, and 3135 leaves. the topologies of the trees are recovered with high success from 2000 bp dna sequences.
handling long targets and errors in sequencing by hybridization. sequencing by hybridization (sbh) is a dna sequencing technique, in which the sequence is reconstructed using its k-mer content. this content, which is called the spectrum of the sequence, is obtained by hybridization to a universal dna array. standard universal arrays contain all k-mers for some fixed k, typically 8 to 10. currently, in spite of its promise and elegance, sbh is not competitive with standard gel-based sequencing methods. this is due to two main reasons: lack of tools to handle realistic levels of hybridization errors, and an inherent limitation on the length of uniquely reconstructible sequence by standard universal arrays.in this paper we deal with both problems. we introduce a simple polynomial reconstruction algorithm which can be applied to spectra from standard arrays and has provable performance in the presence of both false negative and false positive errors. we also propose a novel design of chips containing universal bases, that differs from the one proposed by preparata et al. we give a simple algorithm that uses spectra from such chips to reconstruct with high probability random sequences of length lower only by a squared log factor compared to the information theoretic bound. our algorithm is very robust to errors, and has a provable performance even if there are both false negative and false positive errors. simulations indicate that its sensitivity to errors is also very small in practice.
perfect phylogeny and haplotype assignment. this paper is concerned with the reconstruction of perfect phylogenies from binary character data with missing values, and related problems of inferring complete haplotypes from haplotypes or genotypes with missing data. in cases where the problems considered are np-hard we assume a rich data hypothesis under which they become tractable. natural probabilistic models are introduced for the generation of character vectors, haplotypes or genotypes with missing data, and it is shown that these models support the rich data hypothesis. the principal results include: a near-linear time algorithm for inferring a perfect phylogeny from binary character data (or haplotype data) with missing values, under the rich data hypothesis; a quadratic-time algorithm for inferring a perfect phylogeny from genotype data with missing values with high probability, under certain distributional assumptions; demonstration that the problems of maximum-likelihood inference of complete haplotypes from partial haplotypes or partial genotypes can be cast as minimum-entropy disjoint set cover problems; in the case where the haplotypes come from a perfect phylogeny, a representation of the set cover problem as minimum-entropy covering of subtrees of a tree by nodes; an exact algorithm for minimum-entropy subtree covering, and demonstration that it runs in polynomial time when the subtrees have small diameter; demonstration that a simple greedy approximation algorithm solves the minimum-entropy subtree covering problem with relative error tending to zero when the number of partial haplotypes per complete haplotype is large; an asymptotically consistent method of estimating the frequencies of the complete haplotypes in a perfect phylogeny, under an iid model for the distribution of missing data; computational results on real data demonstrating the effectiveness of a the greedy algorithm for inferring haplotypes from genotypes with missing data, even in the absence of a perfect phylogeny..