waashk/dblp huggingface dataset:
large scale sequencing by hybridization. sequencing by hybridization is a method for reconstructing a dna sequence based on its k-mer content. this content, called the spectrum of the sequence, can be obtained from hybridization with a universal dna chip. however, even with a sequencing chip containing all 49 9-mers and assuming no hybridization errors, only about 400 bases-long sequences can be reconstructed unambiguously. drmanac et al. suggested sequencing long dna targets by obtaining spectra of many short overlapping fragments of the target, inferring their relative positions along the target and computing spectra of subfragments that are short enough to be uniquely recoverable. drmanac et al. do not treat the realistic case of errors in the hybridization process. in this paper we study the effect of such errors. we show that the probability of ambiguous reconstruction in the presence of (false negative) errors is close to the probability in the errorless case. more precisely, the ratio between these probabilities is 1 + &ogr;(p/(1 - p)4 &middot; 1/d) where d is the average distance between neighboring subfragments, and p is the probability of a false negative. we also obtain lower and upper bounds for the probability of unambiguous reconstruction based on errorless spectrum. for realistic chip sizes, these bounds are tighter than those given by arratia et al. finally, we report results on simulations with real dna sequences, showing that even in the presence of 50% false negative errors, a target of cosmid length can be recovered with less than 0.1% miscalled bases.
identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data. mounting evidence shows that many protein complexes are conserved in evolution. here we use conservation to find complexes that are common to yeast s. cerevisiae and bacteria h. pylori. our analysis combines protein interaction data, that are available for each of the two species, and orthology information based on protein sequence comparison. we develop a detailed probabilistic model for protein complexes in a single species, and a model for the conservation of complexes between two species. using these models, one can recast the question of finding conserved complexes as a problem of searching for heavy subgraphs in an edge- and node-weighted graph, whose nodes are orthologous protein pairs.we tested this approach on the data currently available for yeast and bacteria and detected 11 significantly conserved complexes. several of these complexes match very well with prior experimental knowledge on complexes in yeast only, and serve for validation of our methodology. the complexes suggest new functions for a variety of uncharacterized proteins. by identifying a conserved complex whose yeast proteins function predominantly in the nuclear pore complex, we propose that the corresponding bacterial proteins function as a coherent cellular membrane transport system. we also compare our results to two alternative methods for detecting complexes, and demonstrate that our methodology obtains a much higher specificity.
rna biology and the genome (abstract only). the sequence of vertebrate genome is expressed by rna splicing producing mrna. interpreting the genome requires understanding the sequences recognized by the nuclear factors and spliceosomia executing removal of introns. the status of this area of science will be reviewed. conversely, genome sequences can be searched for sequences which specify rna splicing and are common of many genes. the availability of genome sequences from a variety of species will make the latter approach much more powerful. the recently discovered rna interference (rnai) process is evolutionarily old and related processes are important for control of expression of repetitive genes in some organisms. rnai can be initiated by conversion of double strand rna into 21-23 nucleotide rnas which can base pair with mrnas and direct their cleavage. these short rnas may also direct silencing of genes by other mechanisms. over half of the genome of many organisms is composed of repetitive sequences and it is possible that rnai may silence these sequences.
matching simulation and experiment (extended abstract): a new simplified model for simulating protein folding. simulations of simplified protein folding models have provided much insight into solving the protein folding problem. we propose here a new off-lattice bead model, capable of simulating several different fold classes of small proteins. we present the sequence for an &agr;/&bgr; protein resembling the igg-binding proteins l and g. the thermodynamics of the folding process for this model are characterized using the multiple multi-histogram method combined with constant-temperature langevin simulations. the folding is shown to be highly cooperative, with chain collapse nearly accompanying folding. two parallel folding pathways are shown to exist on the folding free energy landscape. one pathway contains an intermediate&mdash;similar to experiments on protein g, and one pathway contains no intermediates&mdash;similar to experiments on protein l. the folding kinetics are characterized by tabulating mean-first passage times, and we show that the onset of glasslike kinetics occurs at much lower temperatures than the folding temperature. this model is expected to be useful in many future contexts; investigating questions of the role of local versus non-local interactions in various fold classes, addressing the effect of sequence mutations affecting secondary structure propensities, and providing a computationally feasible model for studying the role of solvation forces in protein folding.
multiple sequence alignment based on profile alignment of intermediate sequences. despite considerable efforts, it remains difficult to obtain accurate multiple sequence alignments. by using additional hits from database search of the input sequences, a few strategies have been proposed to significantly improve alignment accuracy, including the construction of profiles from the hits while performing profile alignment, the inclusion of high scoring hits into the input sequences, the use of intermediate sequence search to link distant homologs, and the use of secondary structure information. we develop an algorithm that integrates these strategies to further improve alignment accuracy by modifying the pair-hmm approach in probcons to incorporate profiles of intermediate sequences from database search and utilize secondary structure predictions as in spem. we test our algorithm on a few sets of benchmark multiple alignments, including balibase, homstrad, prefab and sab-mark, and show that it significantly outperforms mafft and probcons, which are among the best multiple alignment algorithms that do not utilize additional information, and spem, which is among the best multiple alignment algorithms that utilize additional hits from database search. the improvement in accuracy over spem can be as much as 5 to 10% when aligning divergent sequences. a software program that implements this approach (ispalign) is at http://faculty.cs.tamu.edu/shsze/ispalign.
an algorithm to enumerate all sorting reversals. the problem of estimating evolutionary distance from differences in gene order has been distilled to the problem of finding the reversal distance between two signed permutations. during the last decade, much progress was made both in computing reversal distance and in finding a minimum sequence of sorting reversals. for most problem instances, however, many minimum sequences of sorting reversals exist, and obtaining the complete set can be useful in exploring the space of genome rearrangements (e.g., in pursuit of solutions to higher-level problems). the problem of finding all minimum sequences of sorting reversals reduces easily to the problem of finding all sorting reversals of one permutation with respect to another. we derive an efficient algorithm to solve this latter problem, and present experimental results indicating that our algorithm offers a dramatic improvement over the best known alternative. it should be noted that in asymptotic terms the new algorithm does not represent a significant improvement: it requires o(n3) time (where n is the permutation size), while the problem can now be solved trivially in &thgr;(n3) time.
combining phylogenetic and hidden markov models in biosequence analysis. a few models have appeared in recent years that consider not only the way substitutions occur through evolutionary history at each site of a genome, but also the way the process changes from one site to the next. these models combine phylogenetic models of molecular evolution, which apply to individual sites, and hidden markov models, which allow for changes from site to site. besides improving the realism of ordinary phylogenetic models, they are potentially very powerful tools for inference and prediction---for gene finding, for example, or prediction of secondary structure. in this paper, we review progress on combined phylogenetic and hidden markov models and present some extensions to previous work. our main result is a simple and efficient method for accommodating higher-order states in the hmm, which allows for context-sensitive models of substitution---that is, models that consider the effects of neighboring bases on the pattern of substitution. we present experimental results indicating that higher-order states, autocorrelated rates, and multiple functional categories all lead to significant improvements in the fit of a combined phylogenetic and hidden markov model, with the effect of higher-order states being particularly pronounced.
computational identification of evolutionarily conserved exons. phylogenetic hidden markov models (phylo-hmms) have recently been proposed as a means for addressing a multi-species version of the ab initio gene prediction problem. these models allow sequence divergence, a phylogeny, patterns of substitution, and base composition all to be considered simultaneously, in a single unified probabilistic model. here, we apply phylo-hmms to a restricted version of the gene prediction problem in which individual exons are sought that are evolutionarily conserved across a diverse set of species. we discuss two new methods for improving prediction performance: (1) the use of context-dependent phylogenetic models, which capture phenomena such as a strong cpg effect in noncoding regions and a preference for synonymous rather than nonsynonymous substitutions in coding regions; and (2) a novel strategy for incorporating insertions and deletion (indels) into the state-transition structure of the model, which captures the different characteristic patterns of alignment gaps in coding and noncoding regions. we also discuss the technique, previously used in pairwise gene predictors, of explicitly modeling conserved noncoding sequence to help reduce false positive predictions. these methods have been incorporated into an exon prediction program called exoniphy, and tested with two large data sets. experimental results indicate that all three methods produce significant improvements in prediction performance. in combination, they lead to prediction accuracy comparable to that of some of the best available gene predictors, despite several limitations of our current models.
designing multiple simultaneous seeds for dna similarity search. the challenge of similarity search in massive dna sequence databases has inspired major changes in blast-style alignment tools, which accelerate search by inspecting only pairs of sequences sharing a common short "seed," or pattern of matching residues. some of these changes raise the possibility of improving search performance by probing sequence pairs with several distinct seeds, any one of which is sufficient for a seed match. however, designing a set of seeds to maximize their combined sensitivity to biologically meaningful sequence alignments is computationally difficult, even given recent advances [16, 6] in designing single seeds.this work describes algorithmic improvements to seed design that address the problem of designing a set of n seeds to be used simultaneously. we give a new local search method to optimize the sensitivity of seed sets. the method relies on efficient incremental computation of the probability that an alignment contains a match to a seed π, given that it has already failed to match any of the seeds in a set π. we demonstrate experimentally that multi-seed designs, even with relatively few seeds, can be significantly more sensitive than even optimized single-seed designs.
ab initio whole genome shotgun assembly with mated short reads. next generation sequencing (ngs) technologies are capable of reading millions of short dna sequences both quickly and cheaply. while these technologies are already being used for resequencing individuals once a reference genome exists, it has not been shown if it is possible to use them for ab initio genome assembly. in this paper, we give a novel network flow-based algorithm that, by taking advantage of the high coverage provided by ngs, accurately estimates the copy counts of repeats in a genome. we also give a second algorithm that combines the predicted copy-counts with mate-pair data in order to assemble the reads into contigs. we run our algorithms on simulated read data from e. coli and predict copy-counts with extremely high accuracy, while assembling long contigs.
using a mixture of probabilistic decision trees for direct prediction of protein function. we study the direct relationship between basic protein properties and their function. our goal is to develop a new tool for functional prediction that can be used to complement and support other techniques based on sequence or structure information. in order to define this new measure of similarity between proteins we collected a set of 453 features and properties that characterize proteins and are believed to be correlated and related to structural and functional aspects of proteins. among these properties are the composition and fraction of different groups of amino acids, predicted secondary structure content, molecular weight, average hydrophobicity, isoelectric point and others, as well as a set of properties that are extracted from database records of known protein sequences, such as subcellular location, tissue specificity, and others.we introduce the mixture model of probabilistic decision trees to learn the set of potentially complex relationships between features and function. to study these correlations, trees are created and tested on the pfam sequence-based classification of proteins and the ec classification of enzyme families. the model is very effective in learning highly diverged protein families or families that are not defined based on sequence. the resulting tree structure indicates the properties that are strongly correlated with structural and functional aspects of protein families, and can be used to suggest a concise definition of a protein family.
modeling transcription programs: inferring binding site activity and dose-response model optimization. the modeling of transcription regulation programs is a major focus of today's biology. the challenge is to utilize diverse high-throughput data (gene expression, promoter binding site localization assays, protein expression) in order to infer the mechanistic models of transcription control. we propose a new model which integrates transcription factor-gene affinities, protein abundance and gene expression levels. transcription factor binding site activity is represented by a dose-affinity-response function, and regulation is assumed to be a combinatorial function of the activities of the binding sites in the gene's promoter sites.we develop algorithms that infer the model given complete data and give a fast polynomial time algorithm under reasonable assumptions. we also show how to assess initial values of missing data (notably protein abundance) using a novel framework for active motif detection, which may be of independent interest. we test the various components of the framework on gene expression data related to carbohydrate metabolism in yeast. the results demonstrate the high specificity and sensitivity of the approach and its advantages over extant motif activity detection methods. we are also able to predict new active motifs in the galactose pathway.a key feature of our method is the global approach to transcription factor activity and to the relation between this activity and promoter signals. we use dozens of genes, with many different promoter signals and expression levels in order to draw conclusions on the function of a single transcription factor. this provides us the robustness necessary in order to overcome the considerable level of noise in the data.
using motion planning to study rna folding kinetics. we propose a novel, motion planning based approach to approximately map the energy landscape of an rna molecule. our method is based on the successful probabilistic roadmap motion planners that we have previously successfully applied to protein folding. the key advantage of our method is that it provides a sparse map that captures the main features of the landscape and which can be analyzed to compute folding kinetics. in this paper, we provide evidence that this approach is also well suited to rna. we compute population kinetics and transition rates on our roadmaps using the master equation for a few moderately sized rna and show that our results compare favorably with results of other existing methods.
zinc finger gene clusters and tandem gene duplication. zinc finger genes in mammalian genomes are frequently found to occur in clusters with cluster members appearing in a tandem array on the chromosome. it has been suggested that in situ gene duplication events are primarily responsible for the evolution of such clusters. the problem of inferring the series of duplication events responsible for producing clustered families is different from the standard phylogeny problem. in this paper we study this inference problem using a graph called duplication model that captures the series of duplication events while taking into account the observed order of the genes on the chromosome. we provide algorithms to reconstruct a duplication model for a given data set. we use our method to hypothesise the series of duplication events that may have produced the znf45 family that appears on human chromosome 19.
pdb_isl: an intermediate sequence library for protein structure assignment. for large scale structural assignment to sequences, as in computational structural genomics, a fast yet sensitive homology search procedure is essential. a new approach using intermediate sequences was tested as a shortcut to iterative multiple sequence search methods such as psi-blast and hidden markov models. a library containing potential intermediate sequences for proteins of known structure (pdb_isl) was constructed. the sequences in the library were collected from a large sequence database using the sequences of the domains of proteins of known structure as the query sequences and the program psi-blast. sequences of proteins of unknown structure can be matched to distantly related proteins of known structure by using any pairwise sequence comparison methods to find homologues in pdb_isl. searches of pdb_isl were calibrated, and the number of correct matches found at a given error rate was the same as that found by psi_blast. the advantage of this library is that it uses pairwise sequence comparison methods, such as fasta or blast2, and can, therefore, be searched easily and, in many cases, much more quickly than an iterative multiple sequence comparison method. the procedure is roughly twenty times faster than psi-blast for small genomes and several hundred times for large genomes such as c. elegans. sequences can be submitted to the pdb_isl servers at http://stash.mrc-lmb.cam.ac.uk/pdb_isl/ ftp://ftp.ebi.ac.uk/pub/databases/pdb_isl/
a dimensionality reduction approach to modeling protein flexibility. proteins are involved either directly or indirectly in all biological processes in living organisms. it is now widely accepted that conformational changes of proteins can critically affect their ability to bind other molecules and that any progress in modeling protein motion and flexibility will contribute to the understanding of key biological functions. however, modeling protein flexibility has proven a very difficult task. experimental laboratory methods such as x-ray crystallography produce rather few structures, while computational methods such as molecular dynamics are too slow for routine use with large systems. a medium sized protein typically has a few thousands of degrees of freedom. this paper shows how to obtain a reduced basis representation of protein flexibility. we use the principal component analysis method, a dimensionality reduction technique, to transform the original high dimensional representation of protein motion into a lower dimensional representation that captures the dominant modes of motions of the protein. although there is inevitably some loss in accuracy, we show that we can obtain conformations that have been observed in laboratory experiments, starting from different initial conformations and working in a drastically reduced search space.
a gibbs sampling method to detect over-represented motifs in the upstream regions of co-expressed genes. microarray experiments can reveal useful information on the transcriptional regulation. we try to find regulatory elements in the region upstream of translation start of coexpressed genes. here we present a modification to the original gibbs sampling algorithm [12]. we introduce a probability distribution to estimate the number of copies of the motif in a sequence. the second modification is the incorporation of a higher-order background model. we have successfully tested our algorithm on several data sets. first we show results on two selected data set: sequences from plants containing the g-box motif and the upstream sequences from bacterial genes regulated by o2-responsive protein fnr. in both cases the motif sampler is able to find the expected motifs. finally, the sampler is tested on 4 clusters of coexpressed genes from a wounding experiment in arabidopsis thaliana. we find several putative motifs that are related to the pathways involved in the plant defense mechanism.
toward a proteome atlas for c. elegans. the availability of complete genome sequences suggests new approaches for biological research to complement conventional genetics and biochemistry. in this context, the goals of this laboratory are to generate a comprehensive protein-protein interaction, or interactome, map for c. elegans and develop new concepts to integrate this map with other functions such as expression profiles (transcriptome), global phenotypic analysis (phenome), localization of expression projects localizome, etc... the resulting atlas of integrated maps should be valuable for the development of a systems biology approach to the study of development.
a more efficient approximation scheme for tree alignment. we present a new polynomial time approximation scheme (ptas) for tree alignment, which is an important variant of multiple sequence alignment. as in the existing ptass in the literature, the basic approach of our algorithm is to partition the given tree into overlapping components of a constant size and then apply local optimization on each such component. but the new algorithm uses a clever partitioning strategy and achieves a better efficiency for the same performance ratio. for example, to achieve approximation ratios 1.6 and 1.5, the best existing ptas has to spend time o(kdn5) and o(kdn9), respectively, where n is the length of each leaf sequence and d,k are the depth and number of leaves of the tree, while the new ptas only has to spend time o(kdn4) and o(kdn5). moreover, the performance of the ptas is more sensitive to the size of the components, which basically determines the running time, and we obtain an improved approximation ratio for each size. some experiments of the algorithm on simulated and real data are also given.