waashk/dblp huggingface dataset:
a random graph approach to nmr sequential assignment. nuclear magnetic resonance (nmr) spectroscopy allows scientists to study protein structure, dynamics, and interactions in solution. a necessary first step for such applications is determining the resonance assignment, mapping spectral data to atoms and residues in the primary sequence. automated resonance assignment algorithms rely on information regarding connectivity (e.g. through-bond atomic interactions) and amino acid type, typically using the former to determine strings of connected residues and the latter to map those strings to positions in the primary sequence. significant ambiguity exists in both connectivity and amino acid type, and different algorithms have combined the information in two phases (find short unambiguous strings then align) or simultaneously (align while extending strings). this paper focuses on the information content available in connectivity alone, allowing for ambiguity rather than handling only unambiguous strings, and complements existing work on the information content in amino acid type.in this paper, we develop a novel random-graph theoretic framework for algorithmic analysis of nmr sequential assignment. our random graph model captures the structure of chemical shift degeneracy (a key source of connectivity ambiguity). we then give a simple and natural randomized algorithm for finding an optimum sequential cover. the algorithm naturally and efficiently reuses substrings while exploring connectivity choices; it overcomes local ambiguity by enforcing global consistency of all choices. we employ our random graph model to analyze our algorithm, and show that it can provably tolerate a relatively large ambiguity while still giving expected optimal performance in polynomial time. to study the algorithm's performance in practice, we tested it on experimental data sets from a variety of proteins and experimental set-ups. the algorithm was able to overcome significant noise and local ambiguity and consistently identify significant sequential fragments.
class discovery in gene expression data. recent studies (alizadeh et al, [1]; bittner et al,[5]; golub et al, [11]) demonstrate the discovery of putative disease subtypes from gene expression data. the underlying computational problem is to partition the set of sample tissues into statistically meaningful classes. in this paper we present a novel approach to class discovery and develop automatic analysis methods. our approach is based on statistically scoring candidate partitions according to the overabundance of genes that separate the different classes. indeed, in biological datasets, an overabundance of genes separating known classes is typically observed. we measure overabundance against a stochastic null model. this allows for highlighting subtle, yet meaningful, partitions that are supported on a small subset of the genes. using simulated annealing we explore the space of all possible partitions of the set of samples, seeking partitions with statistically significant overabundance of differentially expressed genes. we demonstrate the performance of our methods on synthetic data, where we recover planted partitions. finally, we turn to tumor expression datasets, and show that we find several highly pronounced partitions.
dna segmentation as a model selection process. previous divide-and-conquer segmentation analyses of dna sequences do not provide a satisfactory stopping criterion for the recursion. this paper proposes that segmentation be considered as a model selection process. using the tools in model selection, a limit for the stopping criterion on the relaxed end can be determined. the bayesian information criterion, in particular, provides a much more stringent stopping criterion than what is currently used. such a stringent criterion can be used to delineate larger dna domains. a relationship between the stopping criterion and the average domain size is empirically determined, which may aid in the determination of isochore borders.
the noesy jigsaw: automated protein secondary structure and main-chain assignment from sparse, unassigned nmr data. high-throughput, data-directed computational protocols for structural genomics (or proteomics) are required in order to evaluate the protein products of genes for structure and function at rates comparable to current gene-sequencing technology. this paper presents the jigsaw algorithm, a novel high-throughput, automated approach to protein structure characterization with nuclear magnetic resonance (nmr). jigsaw consists of two main components: (1) graph-based secondary structure pattern identification in unassigned heteronuclear nmr data, and (2) assignment of spectral peaks by probabilistic alignment of identified secondary structure elements against the primary sequence. jigsaw''s deferment of assignment until after secondary structure identification differs greatly from traditional approaches, which begin by correlating peaks among dozens of experiments. by deferring assignment, jigsaw not only eliminates this bottleneck, it also allows the number of experiments to be reduced from dozens to four, none of which requires 13c-labeled protein. this in turn dramatically reduces the amount and expense of wet lab molecular biology for protein expression and purification, as well as the total spectrometer time to collect data. our results for three test proteins demonstrate that we are able to identify and align approximately 80 percent of alpha-helical and 60 percent of beta-sheet structure. jigsaw is extremely fast, running in minutes on a pentium-class linux workstation. this approach yields quick and reasonably accurate (as opposed to the traditional slow and extremely accurate) structure calculations, utilizing a suite of graph analysis algorithms to compensate for the data sparseness. jigsaw could be used for quick structural assays to speed data to the biologist early in the process of investigation, and could in principle be applied in an automation-like fashion to a large fraction of the proteome.
interface surfaces for protein-protein complexes. protein-protein interactions, which form the basis for most cellular processes, result in the formation of protein interfaces. believing that the local shape of proteins is crucial, we take a geometric approach and present a definition of an interface surface formed by two or more proteins. we also present an algorithm and study the geometric and topological properties of these surfaces, thus paving the way for future biochemical studies of protein-protein interactions.
multiple organism gene finding by collapsed gibbs sampling. the gibbs sampling method has been widely used for sequence analysis after it was successfully applied to the problem of identifying regulatory motif sequences upstream of genes. since then numerous variants of the original idea have emerged, however in all cases the application has been to finding short motifs in collections of short sequences (typically less than 100 nucleotides long). in this paper we introduce a gibbs sampling approach for identifying genes in multiple large genomic sequences up to hundreds of kilobases long. this approach leverages the evolutionary relationships between the sequences to improve the gene predictions, without explicitly aligning the sequences. we have applied our method to the analysis of genomic sequence from 14 genomic regions, totaling roughly 1.8mb of sequence in each organism. we show that our approach compares favorably with existing ab-initio approaches to gene finding, including pairwise comparison based gene prediction methods which make explicit use of alignments. furthermore, excellent performance can be obtained with as little as 4 organisms, and the method overcomes a number of difficulties of previous comparison based gene finding approaches: it is robust with respect to genomic rearrangements, can work with draft sequence, and is fast (linear in the number and length of the sequences). it can also be seamlessly integrated with gibbs sampling motif detection methods.
gene-finding via tandem mass spectrometry. we propose a new gene-finding methodology that combines high performance liquid chromatograph (hplc)-tandem mass spectrometry experiments with a fast computer algorithm to locate coding regions and introns. proteins are first extracted from cells and digested by enzymes, and then the resulting peptides are separated and analyzed by hplc-tandem mass spectrometry. we designed an algorithm to find dna coding sequences, corresponding to open reading frames (orf), in the genome such that their translated amino acid sequences are optimally correlated with these tandem mass spectra. in this algorithm, we also allow one gap, corresponding to an intron, between two dna coding sequences, such that their concatenation becomes one coding sequence. finally, the algorithm assembles these candidate coding sequences and introns into gene structures. our algorithm was implemented to predict genes on 4 contigs with a total of 123 kbps using two sets of simulated digestion- hplc-tandem mass spectrometry data of 2523 caenorhabditis elegans chromosome iv proteins, digested by trypsin and asp-n respectively. among 15 annotated genes in the forward strand, all 98 exons are hit by the predicted no-gap coding sequences, and 60 out of 83 introns are correctly predicted. we also tested gene structure prediction in a contig containing 3 genes. combining splicing site predictions with predicted coding sequences and introns, we found all 3 gene structures.
gene selection criterion for discriminant microarray data analysis based on extreme value distributions. an important issue commonly encountered in the analysis of microarray data is to decide which and how many genes should be selected for further studies. for discriminant microarray data analyses based on statistical models, such as the logistic regression model, this gene selection can be accomplished by a comparison of the maximum likelihood of the model given the real data, l(d|m), and the expected maximum likelihood of the model given an ensemble of surrogate data, l(d0|m). typically, the computational burden for obtaining l(d0|m) is immense, often exceeding the limits of available resources by orders of magnitude. here, we propose an approach that circumvents such heavy computations by mapping the simulation problem to an extreme value problem, which can be easily solved by numerical simulation. we choose three classification problems from two publicly available microarray datasets to illustrate that approach.
a new approach to analyzing gene expression time series data. we present algorithms for time-series gene expression analysis that permit the principled estimation of unobserved time-points, clustering, and dataset alignment. each expression profile is modeled as a cubic spline (piecewise polynomial) that is estimated from the observed data and every time point influences the overall smooth expression curve. we constrain the spline coefficients of genes in the same class to have similar expression patterns, while also allowing for gene specific parameters. we show that unobserved time-points can be reconstructed using our method with 10-15% less error when compared to previous best methods. our clustering algorithm operates directly on the continuous representations of gene expression profiles, and we demonstrate that this is particularly effective when applied to non-uniformly sampled data. our continuous alignment algorithm also avoids difficulties encountered by discrete approaches. in particular, our method allows for control of the number of degrees of freedom of the warp through the specification of parameterized functions, which helps to avoid overfitting. we demonstrate that our algorithm produces stable low-error alignments on real expression data and further show a specific application to yeast knockout data that produces biologically meaningful results.
notung: dating gene duplications using gene family trees. large scale gene duplication is a major force driving the evolution of genetic functional innovation. whole genome duplications are widely believed to have played an important role in the evolution of the maize, yeast and vertebrate genomes. the use of evolutionary trees to analyze the history of gene duplication and estimate duplication times provides a powerful tool for studying this process. many studies in the molecular evolution literature have used this approach on small data sets, using analyses performed by hand. the rapid growth of genetic sequence data will soon allow similar studies on a genomic scale but such studies will be limited unless the analysis can be automated. even existing data sets admit alternative hypotheses that would be too tedious to consider without automation. in this paper, we describe a toolbox called notung that facilitates large scale analysis, using both rooted and unrooted trees. when tested on trees analyzed in the literature, notung consistently yielded result that agree with the assessments in the original publications. thus, notung provides a basic building block for inferring duplication dates from gene trees automatically and can also be used as an exploratory analysis tool for evaluating alternative hypotheses.
modeling dependencies in protein-dna binding sites. the availability of whole genome sequences and high-throughput genomic assays opens the door for in silico analysis of transcription regulation. this includes methods for discovering and characterizing the binding sites of dna-binding proteins, such as transcription factors. a common representation of transcription factor binding sites is a position specific score matrix (pssm). this representation makes the strong assumption that binding site positions are independent of each other. in this work, we explore bayesian network representations of binding sites that provide different tradeoffs between complexity (number of parameters) and the richness of dependencies between positions. we develop the formal machinery for learning such models from data and for estimating the statistical significance of putative binding sites. we then evaluate the ramifications of these richer representations in characterizing binding site motifs and predicting their genomic locations. we show that these richer representations improve over the pssm model in both tasks.
context-specific bayesian clustering for gene expression data. the recent growth in genomic data and measurement of genome-wide expression patterns allows to examine gene regulation by transcription factors using computational tools. in this work, we present a class of mathematical models that help in understanding the connections between transcription factors and functional classes of genes based on genetic and genomic data. these models represent the joint distribution of transcription factor binding sites and of expression levels of a gene in a single model. learning a combined probability model of binding sites and expression patterns enables us to improve the clustering of the genes based on the discovery of putative binding sites and to detect which binding sites and experiments best characterize a cluster. to learn such models from data, we introduce a new search method that rapidly learns a model according to a bayesian score. we evaluate our method on synthetic data as well as on real data and analyze the biological insights it provides.
probabilistic discovery of overlapping cellular processes and their regulation. many of the functions carried out by a living cell are regulated at the transcriptional level, to ensure that genes are expressed when they are needed. thus, to understand biological processes, it is thus necessary to understand the cell's transcriptional network. in this paper, we propose a novel probabilistic model of gene regulation for the task of identifying overlapping biological processes and the regulatory mechanism controlling their activation. a key feature of our approach is that we allow genes to participate in multiple processes, thus providing a more biologically plausible model for the process of gene regulation. we present an algorithm to learn this model automatically from data, using only genome-wide measurements of gene expression as input. we compare our results to those obtained by other approaches, and show significant benefits can be gained by modeling both the organization of genes into overlapping cellular processes and the regulatory programs of these processes. moreover, our method successfully grouped genes known to function together, recovered many regulatory relationships that are known in the literature, and suggested novel hypotheses regarding the regulatory role of previously uncharacterized proteins.
towards optimally multiplexed applications of universal dna tag systems. we study a design and optimization problem that occurs, for example, when single nucleotide polymorphisms (snps) are to be genotyped using a universal dna tag array. the problem of optimizing the universal array to avoid disruptive cross-hybridization between universal components of the system was addressed in a previous work. however, cross-hybridization can also occur assay-specifically, due to unwanted complementarity involving assay-specific components. here we examine the problem of identifying the most economic experimental configuration of the assay-specific components that avoids cross-hybridization. our formalization translates this problem into the problem of covering the vertices of one side of a bipartite graph by a minimum number of balanced subgraphs of maximum degree 1. we show that the general problem is np-complete. however, in the real biological setting the vertices that need to be covered have degrees bounded by d. we exploit this restriction and develop an o(d)-approximation algorithm for the problem. we also give an o(d)-approximation for a variant of the problem in which the covering subgraphs are required to be vertex-disjoint. in addition, we propose a stochastic model for the input data and use it to prove a lower bound on the cover size. we complement our theoretical analysis by implementing two heuristic approaches and testing their performance on simulated and real snp data.
efficient rule-based haplotyping algorithms for pedigree data. we study haplotype reconstruction under the mendelian law of inheritance and the minimum recombination principleon pedigree data. we prove that the problem of finding a mini-mum-recombinant haplotype configuration (mrhc) is in general np-hard. this is the first complexity result concerning the problem to our knowledge. an iterative algorithm based on blocks of consecutive resolved marker loci (called block-extension) is proposed. it is very efficient and can be used for large pedigrees with a large number of markers, especially for those data sets requiring few recombinants (or recombination events). a polynomial-time exact algorithm for haplotype reconstruction without recombinants is also presented. this algorithm first identifies all the necessary constraints based on the mendelian law and the zero recombinant assumption, and represents them using a system of linear equations over the cyclic group z2. by using a simple method based on gaussian elimination, we could obtain all possible feasible haplotype configurations. we have tested the block-extension algorithm on simulated data generated on three pedigree structures. the results show that the algorithm performs very well on both multi-allelic and biallelic data, especially when the number of recombinants is small.
the restriction scaffold problem. most shotgun sequencing projects undergo a long and costly phase of finishing, in which a partial assembly forms several contigs whose order, orientation and relative distance is unknown. we propose here a new technique that supplements the shotgun assembly data by cheap and simple complete restriction digests of the target. by computationally combining information from the contig sequences and the fragment sizes measured for several different enzymes, we seek to form a "scaffold" on which the contigs will be placed in their correct orientation, order and distance. we give a heuristic search algorithm for solving the problem and report on promising preliminary simulation results. the key to the success of the search scheme is the very rapid solution of its two time-critical subproblems that are solved precisely in linear time.our simulations indicate that with noise levels of some 3% relative error in measuring fragment sizes, using five enzymes, most datasets of 20 contigs can be correctly ordered, and the remaining ones have most of their pairs of neighboring contigs correct. hence, the technique has a potential to provide real help to finishing. even when the target clone remains unfinished, the ability to order and orient the contigs correctly makes the partial assembly both more accessible and more useful for biologists.
an exact solution for finding minimum recombinant haplotype configurations on pedigrees with missing data by integer linear programming. we study the problem of reconstructing haplotype configurations from genotypes on pedigree data with missing alleles under the mendelian law of inheritance and the minimum recombination principle, which is important for the construction of haplotype maps and genetic linkage/association analysis. our previous results show that the problem of finding a minimum-recombinant haplotype configuration (mrhc) is in general np-hard. the existing algorithms for mrhc either are heuristic in nature and cannot guarantee optimality, or only work under some restrictions (on e.g. the size and structure of the input pedigree, the number of marker loci, the number of recombinants in the pedigree, etc.). in addition, most of them cannot handle data with missing alleles and, for those that do consider missing data, they usually do not perform well in terms of minimizing the number of recombinants when a significant fraction of alleles are missing. in this paper, we develop an effective integer linear programming (ilp) formulation of the mrhc problem with missing data and a branch-and-bound strategy that utilizes a partial order relationship (and some other special relationships) among variables to decide the branching order. the partial order relationship is discovered in the preprocessing of constraints by considering unique properties in our ilp formulation. a directed graph is built based on the variables and their partial order relationship. by identifying and collapsing the strongly connected components in the graph, we may greatly reduce the size of an ilp instance. non-trivial (lower and upper) bounds on the optimal number of recombinants are introduced at each branching node to effectively prune the search tree. when multiple solutions exist, a best haplotype configuration is selected based on a maximum likelihood approach. our results on simulated data show that the algorithm could recover haplotypes with 50 loci from a pedigree of size 29 in seconds on a standard pc. its accuracy is more than 99.8% for data with no missing alleles and 98.3% for data with 20% missing alleles in terms of correctly recovered phase information at each marker locus. as an application of our algorithm to real data, we present some test results on reconstructing haplotypes from a genome-scale snp data set consisting of 12 pedigrees that have 0.8% to 14.5% missing alleles.
human and mouse gene structure: comparative analysis and application to exon prediction. we describe a novel analytical approach to gene recognition based on cross-species comparison we first undertook a comparison of orthologous genomic look from human and mouse, studying the extent of similarity in the number, size and sequence of exons and introns we then developed an approach for recognizing genes within such orthologous regions, by first aligning the regions using an iterative global alignment system and then identifying genes based on conservation of exonic features at aligned positions in both species the alignment and gene recognition are performed by new programs called glass and rosetta, respectively rosetta performed well at exact identification of coding exons in 117 orthologous pairs tested.