waashk/dblp huggingface dataset:
panel construction for mapping in admixed populations via expected mutual information. mapping by admixture linkage disequilibrium (mald) is an economical and powerful approach for the identification of genomic regions harboring disease susceptibility genes in recently admixed populations. we develop an information-theory based measure, called emi (expected mutual information), that computes the impact of a set of markers on the ability to infer ancestry at each chromosomal location. we then present a simple and effective algorithm for the selection of panels that strives to maximize the emi score. finally, we demonstrate via well established simulation tools that our panels provide considerably more power and accuracy for inferring disease gene loci via the mald method in comparison to previous methods.
a fast, alignment-free, conservation-based method for transcription factor binding site discovery. as an increasing number of eukaryotic genomes are being sequenced, comparative studies aimed at detecting regulatory elements in intergenic sequences are becoming more prevalent. most comparative methods for transcription factor (tf) binding site discovery make use of global or local alignments of orthologous regulatory regions to assess whether a particular dna site is conserved across related organisms, and thus more likely to be functional. since binding sites are usually short, sometimes degenerate, and often independent of orientation, alignment algorithms may not align them correctly. here, we present a novel, alignment-free approach for incorporating conservation information into tf motif discovery. we relax the definition of conserved sites: we consider a dna site within a regulatory region to be conserved in an orthologous sequence if it occurs anywhere in that sequence, irrespective of orientation. we use this definition to derive informative priors over dna sequence positions, and incorporate these priors into a gibbs sampling algorithm for motif discovery. our approach is simple and fast. it does not require sequence alignments, nor the phylogenetic relationships between the orthologous sequences, and yet it is more effective on real biological data than methods that do.
constructing treatment portfolios using affinity propagation. a key problem of interest to biologists and medical researchers is the selection of a subset of queries or treatments that provide maximum utility for a population of targets. for example, when studying how gene deletion mutants respond to each of thousands of drugs, it is desirable to identify a small subset of genes that nearly uniquely define a drug 'footprint' that provides maximum predictability about the organism's response to the drugs. as another example, when designing a cocktail of hiv genome sequences to be used as a vaccine, it is desirable to identify a small number of sequences that provide maximum immunological protection to a specified population of recipients. we refer to this task as 'treatment portfolio design' and formalize it as a facility location problem. finding a treatment portfolio is np-hard in the size of portfolio and number of targets, but a variety of greedy algorithms can be applied. we introduce a new algorithm for treatment portfolio design based on similar insights that made the recently-published affinity propagation algorithm work quite well for clustering tasks. we demonstrate this method using the two problems described above: selecting a subset of yeast genes that act as a drug-response footprint, and selecting a subset of vaccine sequences that provide maximum epitope coverage for an hiv genome population.
compostbin: a dna composition-based algorithm for binning environmental shotgun reads. a major hindrance to studies of microbial diversity has been that the vast majority of microbes cannot be cultured in the laboratory and thus are not amenable to traditional methods of characterization. environmental shotgun sequencing (ess) overcomes this hurdle by sequencing the dna from the organisms present in a microbial community. the interpretation of this metagenomic data can be greatly facilitated by associating every sequence read with its source organism. we report the development of compostbin, a dna composition-based algorithm for analyzing metagenomic sequence reads and distributing them into taxon-specific bins. unlike previous methods that seek to bin assembled contigs and often require training on known reference genomes, compostbin has the ability to accurately bin raw sequence reads without need for assembly or training. compostbin uses a novel weighted pca algorithm to project the high dimensional dna composition data into an informative lower-dimensional space, and then uses the normalized cut clustering algorithm on this filtered data set to classify sequences into taxon-specific bins. we demonstrate the algorithm's accuracy on a variety of low to medium complexity data sets.
on the inference of ancestries in admixed populations. inference of ancestral information in recently admixed populations, in which every individual is composed of a mixed ancestry (e.g., african americans in the us), is a challenging problem. several previous model-based approaches have used hidden markov models (hmm) to model the problem, however, the markov chain monte carlo (mcmc) algorithms underlying these models converge slowly on realistic datasets. while retaining the hmm as a model, we show that a combination of an accurate fast initialization and a local hill-climb in likelihood results in significantly improved estimates of ancestry.we studied this approach in two scenarios--the inference of locus-specific ancestries in a population that is assumed to originate from two unknown ancestral populations, and the inference of allele frequencies in one ancestral population given those in another.
systems metabolic engineering. metabolic engineering allows purposeful modification of metabolic and cellular network towards achieving several goals including enhanced production of various bioproducts, production of novel products, and broadening the substrate utilization range. traditional metabolic engineering has been performed by manipulating a handful of genes and pathways based on known literature information and our rational thinking. advances in omics technology, computational bioscience, and systems biology are now providing us with new information and knowledge that had not been possible to obtain using traditional approaches. systems biology is allowing us to elucidate the metabolism and physiology of cells and organisms at the global levels. metabolic engineering based on the systems-level analysis of cells and organisms, termed systems metabolic engineering, is now offering a new powerful way of designing and developing strains having improved performance. in this lecture, i will present the general strategies of systems metabolic engineering. also, several examples of applying systems metabolic engineering for the production of amino acids, primary metabolite (succinic acid) and secondary metabolite (lycopene) will be presented. 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
rapid and accurate protein side chain prediction with local backbone information. high-accuracy protein structure modeling demands accurate and very fast side chain prediction since such a procedure must be repeatedly called at each step of structure refinement. many known side chain prediction programs, such as scwrl and treepack, depend on the philosophy that global information and pairwise energy function must be used to achieve high accuracy. these programs are too slow to be used in the case when side chain packing has to be used thousands of times, such as protein structure refinement and protein design. we present an unexpected study that local backbone information can determine side chain conformations accurately. localpack, our side chain packing program which is based on only local information, achieves equal accuracy as scwrl and treepack, yet runs 4-14 times faster, hence providing a key missing piece in our efforts to high-accuracy protein structure modeling.
high-resolution modeling of cellular signaling networks. a central challenge in systems biology is the reconstruction of biological networks from high-throughput data sets. a particularly difficult case of this is the inference of dynamic cellular signaling networks. within signaling networks, a common motif is that of many activators and inhibitors acting upon a small set of substrates. here we present a novel technique for high-resolution inference of signaling networks from perturbation data based on parameterized modeling of biochemical rates. we also introduce a powerful new signal-processing method for reduction of batch effects in microarray data. we demonstrate the efficacy of these techniques on data from experiments we performed on the drosophila rho-signaling network, correctly identifying many known features of the network. in comparison to existing techniques, we are able to provide significantly improved prediction of signaling networks on simulated data, and higher robustness to the noise inherent in all high-throughput experiments. while previous methods have been effective at inferring biological networks in broad statistical strokes, this work takes the further step of modeling both specific interactions and correlations in the background to increase the resolution. the generality of our techniques should allow them to be applied to a wide variety of networks.
protein function prediction based on patterns in biological networks. in this paper, we propose a pattern-based protein function annotation framework, employing protein interaction networks, to predict annotation functions of proteins. more specifically, we first detect patterns that appear in the neighborhood of proteins with a particular functionality, and then transfer annotations between two proteins only if they have similar annotation patterns. we show that, in comparison with other techniques, our approach predicts protein annotations more effectively. our technique (a) produces the highest prediction accuracy of 70-80% precision and recall for different organism specific datasets, and (b) is robust to false positives in protein interaction networks.
algorithms for joint optimization of stability and diversity in planning combinatorial libraries of chimeric proteins. in engineering protein variants by constructing and screening combinatorial libraries of chimeric proteins, two complementary and competing goals are desired: the new proteins must be similar enough to the evolutionarily-selected wild-type proteins to be stably folded, and they must be different enough to display functional variation. we present here the first method, staversity, to simultaneously optimize stability and diversity in selecting sets of breakpoint locations for site-directed recombination. our goal is to uncover all "undominated" breakpoint sets, for which no other breakpoint set is better in both factors. our first algorithm finds the undominated sets serving as the vertices of the lower envelope of the two-dimensional (stability and diversity) convex hull containing all possible breakpoint sets. our second algorithm identifies additional breakpoint sets in the concavities that are either undominated or dominated only by undiscovered breakpoint sets within a distance bound computed by the algorithm. both algorithms are efficient, requiring only time polynomial in the numbers of residues and breakpoints, while characterizing a space defined by an exponential number of possible breakpoint sets. we applied staversity to identify 2-10 breakpoint sets for three different sets of parent proteins from the pure family of biosynthetic enzymes. the average normalized distance between our plans and the lower bound for optimal plans is around 1 percent. our plans dominate most (60-90% on average for each parent set) of the plans found by other possible approaches, random sampling or explicit optimization for stability with implicit optimization for diversity. the identified breakpoint sets provide a compact representation of good plans, enabling a protein engineer to understand and account for the trade-offs between two key considerations in combinatorial chimeragenesis.
an integrative network approach to map the transcriptome to the phenome. although many studies have been successful in the discovery of cooperating groups of genes, mapping these groups to phenotypes has proved a much more challenging task. in this paper, we present the first genome-wide mapping of gene coexpression modules onto the phenome. we annotated coexpression networks from 136 microarray datasets with phenotypes from the unified medical language system (umls). we then designed an efficient graph-based simulated annealing approach to identify coexpression modules frequently and specifically occurring in datasets related to individual phenotypes. by requiring phenotypespecific recurrence, we ensure the robustness of our findings. we discovered 9,183 modules specific to 47 phenotypes, and developed validation tests combining gene ontology, generif and umls. our method is generally applicable to any kind of abundant network data with defined phenotype association, and thus paves the way for genome-wide, gene network-phenotype maps.
more efficient algorithms for closest string and substring problems. the closest string and substring problems find applications in pcr primer design, genetic probe design, motif finding, and antisense drug design. for their importance, the two problems have been extensively studied recently in computational biology. unfortunately both problems are np-complete. researchers have developed both fixed-parameter algorithms and approximation algorithms for the two problems. in terms of fixed-parameter, when the radius d is the parameter, the best-known fixed-parameter algorithm for closest string has time complexity o(ndd+1), which is still superpolynomial even if d = o(log n). in this paper we provide an o(n|σ|o(d)) algorithm where σ is the alphabet. this gives a polynomial time algorithm when d = o(log n) and σ has constant size. using the same technique, we additionally provide a more efficient subexponential time algorithm for the closest substring problem. in terms of approximation, both closest string and closest substring problems admit polynomial time approximation schemes (ptas). the best known time complexity of the ptas is o(no(ɛ-2 log 1/ɛ)). in this paper we present a ptas with time complexity o(no(ɛ-2)). at last, we prove that a restricted version of the closest substring has the same parameterized complexity as closest substring, answering an open question in the literature.
bcl-2: from translocation to therapy. impaired apoptosis is a critical step in the development of cancer and a major impediment to effective therapy. bcl-2, the oncoprotein activated by chromosome translocation in human follicular lymphoma, inhibits cells from undergoing apoptosis in response to many cytotoxic agents. exciting recent developments suggest that small molecules which neutralise bcl-2 and its anti-apoptotic homologues will be effective cancer therapeutics. 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
fast and accurate alignment of multiple protein networks. comparative analysis of protein networks has proven to be a powerful approach for elucidating network structure and predicting protein function and interaction. a fundamental challenge for the successful application of this approach is to devise an efficient multiple network alignment algorithm. here we present a novel framework for the problem. at the heart of the framework is a novel representation of multiple networks that is only linear in their size as opposed to current exponential representations. our alignment algorithm is very efficient, being capable of aligning 10 networks with tens of thousands of proteins each in minutes. we show that our algorithm outperforms a previous strategy for the problem that is based on progressive alignment, and produces results that are more in line with current biological knowledge.
bootstrapping the interactome: unsupervised identification of protein complexes in yeast. protein interactions and complexes are major components of biological systems. recent genome-wide applications of tandem affinity purification (tap) in yeast have increased significantly the available information on such interactions. from these experiments, protein complexes were predicted with different approaches first from the individual experiments only and later from their combination. the resulting predictions showed surprisingly little agreement and all of the corresponding methods rely on additional training data. in this article, we present an unsupervised algorithm for the identification of protein complexes which is independent of the availability of additional complex information. based on a bootstrap approach, we calculated intuitive confidence scores for interactions which are more accurate than previous scoring metrics. the complexes determined from this confidence network are of similar quality as the complexes identified by the best supervised approaches. despite the similar quality of the latest predictions and our predictions, considerable differences are still observed between all of them. nevertheless, the set of consistently identified complexes is more than four times as large as for the first two studies. our results illustrate that meaningful and reliable complexes can be determined from the purification experiments alone. as a consequence, the approach presented in this article is easily applicable to large-scale tap experiments for any organism.
computational biology: its challenges past, present, and future. the recognition of the role of mathematics and computer science in modern biology has led to new terminology, as did chemistry with biochemistry, and physics with biophysics. we need to think only of bioinformatics, computational biology, and even system biology and genomics for example. these terms seem to strongly suggest that this is all rather new. yet a short review of the work of those such as j.b.s. haldane, sewell wright, darcy thompson and r.a. fisher, to say nothing of scientists like luria and delbrueck or hodgkin and huxley or thomas hunt morgan, is useful. their work and foresight set the stage for modern applications of mathematical modeling and statistics in the biological sciences. it has often been said that the only difference between now and then is the increase in data-a lot more data. this is clearly not the full story. in addition, we have computational power unimaginable to these earlier researchers, as well as to anyone only forty years ago. so what are our challenges? some are clear, including the modeling and analysis of biologys complex systems such as a cells signaling, metabolic and differentiation. also needed are analysis and models of complex neural systems and ecological structures. the latter, for example, will require a nearly full revamping of the early field of population genetics and evolution in order to exploit both modern genomics and new field studies of multiple species and environmental interactions. and there will be more, much of which will only become apparent as new data and questions arise. one example would be rnai and micro-arrays inducing the development of new analysis tools.
a bayesian approach to protein inference problem in shotgun proteomics. the protein inference problem represents a major challenge in shotgun proteomics. here we describe a novel bayesian approach to address this challenge that incorporates the predicted peptide detectabilities as the prior probabilities of peptide identification. our model removes some unrealistic assumptions used in previous approaches and provides a rigorious probabilistic solution to this problem. we used a complex synthetic protein mixture to test our method, and obtained promising results.
spectrum fusion: using multiple mass spectra for de novo peptide sequencing. we report on a new algorithm for combining the information from several mass spectra of the same peptide. the algorithm automatically learns peptide fragmentation patterns, so that it can handle spectra from any instrument and fragmentation technique. we demonstrate the utility of the algorithm, and the power of multiple spectra, by showing that combining pairs of spectra (one cid and one etd) greatly improves de novo sequencing success rates.
de novo sequencing of nonribosomal peptides. while nonribosomal peptides (nrps) are of tremendous pharmacological importance, there is currently no technology capable of high-throughput sequencing of nrps. difficulties in sequencing nrps slow down the progress in elucidating the non-ribosomal genetic code and negatively affect various screening programs aimed at the discovery of natural compounds of medical importance. we propose to employ multi-stage mass-spectrometry (msn) for the data acquisition, followed by alignment-based heuristic algorithms for data analysis. since mass spectrometry based analysis of nrps is fast and inexpensive, this approach opens the possibility of high-throughput sequencing of many unknown nrps accumulated in large screening programs.
accurate computation of likelihoods in the coalescent with recombination via parsimony. understanding the variation of recombination rates across a given genome is crucial for disease gene mapping and for detecting signatures of selection, to name just a couple of applications. a widely-used method of estimating recombination rates is the maximum likelihood approach, and the problem of accurately computing likelihoods in the coalescent with recombination has received much attention in the past. a variety of sampling and approximation methods have been proposed, but no single method seems to perform consistently better than the rest, and there still is great value in developing better statistical methods for accurately computing likelihoods. so far, with the exception of some twolocus models, it has remained unknown how the true likelihood exactly behaves as a function of model parameters, or how close estimated likelihoods are to the true likelihood. in this paper, we develop a deterministic, parsimony-based method of accurately computing the likelihood for multi-locus input data of moderate size. we first find the set of all ancestral configurations (acs) that occur in evolutionary histories with at most k crossover recombinations. then, we compute the likelihood by summing over all evolutionary histories that can be constructed only using the acs in that set. we allow for an arbitrary number of crossing over, coalescent and mutation events in a history, as long as the transitions stay within that restricted set of acs. for given parameter values, by gradually increasing the bound k until the likelihood stabilizes, we can obtain an accurate estimate of the likelihood. at least for moderate crossover rates, the algorithm-based method described here opens up a new window of opportunities for testing and fine-tuning statistical methods for computing likelihoods.
dlight - lateral gene transfer detection using pairwise evolutionary distances in a statistical framework. this paper presents an algorithm to detect lateral gene transfer (lgt) on the basis of pairwise evolutionary distances. the prediction is made from a likelihood ratio derived from hypotheses of lgt versus no lgt, using multivariate normal theory. in contrast to approaches based on explicit phylogenetic lgt detection, it avoids the high computational cost and pitfalls associated with gene tree inference, while maintaining the high level of characterization obtainable from such methods (species involved in lgt, direction, distance to the lgt event in the past). we validate the algorithm empirically using both simulation and real data, and compare its predictions with standard methods and other studies.