waashk/dblp huggingface dataset:
reconstructing the phylogeny of mobile elements. the study of mobile element evolution yields valuable insights into the mechanism and history of genome rearrangement, and can help answer questions about our evolutionary history. however, because the mammalian genome contains millions of copies of mobile elements exhibiting a complex evolutionary history, traditional phylogenetic methods are ill-suited to reconstructing their history. new phylogenetic reconstruction algorithms which exploit the unique properties of mobile elements and handle large numbers of repeats are therefore necessary to better understand both mobile elements' evolution and our own. we describe a randomized algorithm for phylogenetic reconstruction that scales easily to a million or more elements. we apply our algorithm to human and chimpanzee alu and l1 elements, and to sine elements from 61 species, finding 32 new l1, 111 new sine, and over 1000 new alu subfamilies. our results suggest that the history of mobile elements is significantly more complex than we currently understand.
rearrangements in genomes with centromeres part i: translocations. a centromere is a special region in the chromosome that plays a vital role during cell division. every new chromosome created by a genome rearrangement event must have a centromere in order to survive. this constraint has been ignored in the computational modeling and analysis of genome rearrangements to date. unlike genes, the different centromeres are indistinguishable, they have no orientation, and only their location is known. a prevalent rearrangement event in the evolution of multi-chromosomal species is translocation, i.e., the exchange of tails between two chromosomes. a translocation may create a chromosome with no centromere in it. in this paper we study for the first time centromeres-aware genome rearrangements. we present a polynomial time algorithm for computing a shortest sequence of translocations transforming one genome into the other, where all of the intermediate chromosomes must contain centromeres. we view this as a first step towards analysis of more general genome rearrangement models that take centromeres into consideration.
design of compact, universal dna microarrays for protein binding microarray experiments. our group has recently developed a compact, universal protein binding microarray (pbm) that can be used to determine the binding preferences of transcription factors (tfs) [1]. this design represents all possible sequence variants of a given length k (i.e., all k-mers) on a single array, allowing a complete characterization of the binding specificities of a given tf. here, we present the mathematical foundations of this design based on de bruijn sequences generated by linear feedback shift registers. we show that these sequences represent the maximum number of variants for any given set of array dimensions (i.e., number of spots and spot lengths), while also exhibiting desirable pseudorandomness properties. moreover, de bruijn sequences can be selected that represent gapped sequence patterns, further increasing the coverage of the array. this design yields a powerful experimental platform that allows the binding preferences of tfs to be determined with unprecedented resolution.
multivariate segmentation in the analysis of transcription tiling array data. tiling dna microarrays extend current microarray technology by probing the non-repeat portion of a genome at regular intervals in an unbiased fashion. a fundamental problem in the analysis of these data is the detection of genomic regions that are differentially transcribed across multiple conditions. we propose a linear time algorithm based on segmentation techniques and linear modeling that can work at a user-selected false discovery rate. it also attains a four-fold sensitivity gain over the only competing algorithm when applied to a whole genome transcription data set spanning the embryonic development of drosophila melanogaster.
connectedness profiles in protein networks for the analysis of gene expression data. knowledge about protein function is often encoded in the form of large and sparse undirected graphs where vertices are proteins and edges represent their functional relationships. one elementary task in the computational utilization of these networks is that of quantifying the density of edges, referred to as connectedness, inside a prescribed protein set. for instance, many functional modules can be identified because of their high connectedness. since individual proteins can have very different numbers of interactions, a connectedness measure should be well-normalized for vertex degree. namely, its distribution across random sets of vertices should not be affected when these sets are biased for hubs. we show that such degree-robustness can be achieved via an analytical framework based on a model of random graph with given expected degrees. we also introduce the concept of connectedness profile, which characterizes the relation between adjacency in a graph and a prescribed order of its vertices. a straightforward application to gene expression data and protein networks is the identification of tissue-specific functional modules or cellular processes perturbed in an experiment. the strength of the mapping between gene-expression score and interaction in the network is measured by the area of the connectedness profile. deriving the distribution of this area under the random graph enables us to define degree-robust statistics that can be computed in o(m), m being the network size. these statistics can identify groups of microarray experiments that are pathway-coherent, and more generally, vertex attributes that relate to adjacency in a graph.
a fast and accurate algorithm for the quantification of peptides from mass spectrometry data. liquid chromatography combined with mass spectrometry (lc-ms) has become the prevalent technology in high-throughput proteomics research. one of the aims of this discipline is to obtain accurate quantitative information about all proteins and peptides in a biological sample. due to size and complexity of the data generated in these experiments, this problem remains a challenging task requiring sophisticated and efficient computational tools. we propose an algorithm that can quantify even low abundance peptides from lc-ms data. our approach is flexible and can be applied to preprocessed and raw instrument data. it is based on a combination of the sweep line paradigm with a novel wavelet function tailored to detect isotopic patterns. we evaluate our technique on several data sets of varying complexity and show that we are able to rapidly quantify peptides with high accuracy in a sound algorithmic framework.
a feature-based approach to modeling protein-dna interactions. transcription factor (tf) binding to its dna target site is a fundamental regulatory interaction. the most common model used to represent tf binding specificities is a position specific scoring matrix (pssm), which assumes independence between binding positions. in many cases this simplifying assumption does not hold. here, we present feature motif models (fmms), a novel probabilistic method for modeling tf-dna interactions, based on markov networks. our approach uses sequence features to represent tf binding specificities, where each feature may span multiple positions. we develop the mathematical formulation of our models, and devise an algorithm for learning their structural features from binding site data. we evaluate our approach on synthetic data, and then apply it to binding site and chip-chip data from yeast. we reveal sequence features that are present in the binding specificities of yeast tfs, and show that fmms explain the binding data significantly better than pssms.
gimscan: a new statistical method for analyzing whole-genome array cgh data. genetic instability represents an important type of biological markers for cancer and many other diseases. array comparative genome hybridization (acgh) is a high-throughput cytogenetic technique that can efficiently detect genome-wide genetic instability events such as chromosomal gain, loss, and more complex aneuploidity, collectively known as genome imbalance (gim). we propose a new statistical method, genome imbalance scanner (gimscan), for automatically decoding the underlying dna dosage states from acgh data. gimscan captures both the intrinsic (nonrandom) spatial change of genome hybridization intensities, and the prevalent (random) measurement noise during data acquisition; and it simultaneously segments the chromosome and assigns different states to the segmented dna. we tested the proposed method on both simulated data and real data measured from a colorectal cancer population, and we report competitive or superior performance of gimscan in comparison with popular extant methods.
pairwise global alignment of protein interaction networks by matching neighborhood topology. we describe an algorithm, isorank, for global alignment of two protein-protein interaction (ppi) networks. isorank aims to maximize the overall match between the two networks; in contrast, much of previous work has focused on the local alignment problem-- identifying many possible alignments, each corresponding to a local region of similarity. isorank is guided by the intuition that a protein should be matched with a protein in the other network if and only if the neighbors of the two proteins can also be well matched. we encode this intuition as an eigenvalue problem, in a manner analogous to google's pagerank method. we use isorank to compute the first known global alignment between the s. cerevisiae and d. melanogaster ppi networks. the common subgraph has 1420 edges and describes conserved functional components between the two species. comparisons of our results with those of a well-known algorithm for local network alignment indicate that the globally optimized alignment resolves ambiguity introduced by multiple local alignments. finally, we interpret the results of global alignment to identify functional orthologs between yeast and fly; our functional ortholog prediction method is much simpler than a recently proposed approach and yet provides results that are more comprehensive.
an efficient and accurate graph-based approach to detect population substructure. currently, large-scale projects are underway to perform whole genome disease association studies. such studies involve the genotyping of hundreds of thousands of snp markers. one of the main obstacles in performing such studies is that the underlying population substructure could artificially inflate the p-values, thereby generating a lot of false positives. although existing tools cope well with very distinct sub-populations, closely related population groups remain a major cause of concern. in this work, we present a graph based approach to detect population substructure. our method is based on a distance measure between individuals. we show analytically that when the allele frequency differences between the two populations are large enough (in the l2-norm sense), our algorithm is guaranteed to find the correct classification of individuals to sub-populations. we demonstrate the empirical performance of our algorithms on simulated and real data and compare it against existing methods, namely the widely used software method structure and the recent method eigenstrat. our new technique is highly efficient (in particular it is hundreds of times faster than structure), and overall it is more accurate than the two other methods in classifying individuals into sub-populations. we demonstrate empirically that unlike the other two methods, the accuracy of our algorithm consistently increases with the number of snps genotyped. finally, we demonstrate that the efficiency of our method can be used to assess the significance of the resulting clusters. surprisingly, we find that the different methods find population sub-structure in each of the homogeneous populations of the hapmap project. we use our significance score to demonstrate that these substructures are probably due to over-fitting.
locating multiple gene duplications through reconciled trees. we introduce the first exact and efficient algorithm for guigó et al.'s problem that given a collection of rooted, binary gene trees and a rooted, binary species tree, determines a minimum number of locations for gene duplication events from the gene trees on the species tree. we examined the performance of our algorithm using a set of 85 genes trees that contain genes from a total of 136 plant taxa. there was evidence of large-scale gene duplication events in populus, gossypium, poaceae, asteraceae, brassicaceae, solanaceae, fabaceae, and near the root of the eudicot clade. however, error in gene trees can produce erroneous evidence of large-scale duplication events, especially near the root of the species tree. our algorithm can provide hypotheses for precise locations of large-scale gene duplication events with data from relatively few gene trees and can complement other genomic approaches to provide a more comprehensive view of ancient large-scale gene duplication events.
estimating genome-wide copy number using allele specific mixture models. genomic changes such as copy number alterations are thought to be one of the major underlying causes of human phenotypic variation among normal and disease subjects [23,11,25,26,5,4,7,18]. these include chromosomal regions with so-called copy number alterations: instead of the expected two copies, a section of the chromosome for a particular individual may have zero copies (homozygous deletion), one copy (hemizygous deletions), or more than two copies (amplifications). the canonical example is down syndrome which is caused by an extra copy of chromosome 21. identification of such abnormalities in smaller regions has been of great interest, because it is believed to be an underlying cause of cancer. more than one decade ago comparative genomic hybridization (cgh) technology was developed to detect copy number changes in a highthroughput fashion. however, this technology only provides a 10 mb resolution which limits the ability to detect copy number alterations spanning small regions. it is widely believed that a copy number alteration as small as one base can have significant downstream effects, thus microarray manufacturers have developed technologies that provide much higher resolution. unfortunately, strong probe effects and variation introduced by sample preparation procedures have made single-point copy number estimates too imprecise to be useful. cgh arrays use a two-color hybridization, usually comparing a sample of interest to a reference sample, which to some degree removes the probe effect. however, the resolution is not nearly high enough to provide single-point copy number estimates. various groups have proposed statistical procedures that pool data from neighboring locations to successfully improve precision. however, these procedure need to average across relatively large regions to work effectively thus greatly reducing the resolution. recently, regression-type models that account for probe-effect have been proposed and appear to improve accuracy as well as precision. in this paper, we propose a mixture model solution specifically designed for single-point estimation, that provides various advantages over the existing methodology. we use a 314 sample database, constructed with public datasets, to motivate and fit models for the conditional distribution of the observed intensities given allele specific copy numbers. with the estimated models in place we can compute posterior probabilities that provide a useful prediction rule as well as a confidence measure for each call. software to implement this procedure will be available in the bioconductor oligo package (http://www.bioconductor.org).
variational upper bounds for probabilistic phylogenetic models. probabilistic phylogenetic models which relax the site independence evolution assumption often face the problem of infeasible likelihood computations, for example for the task of selecting suitable parameters for the model. we present a new approximation method, applicable for a wide range of probabilistic models, which guarantees to upper bound the true likelihood of data, and apply it to the problem of probabilistic phylogenetic models. the new method is complementary to known variational methods that lower bound the likelihood, and it uses similar methods to optimize the bounds from above and below. we applied our method to aligned dna sequences of various lengths from human in the region of the cftr gene and homologous from eight mammals, and found the upper bounds to be appreciably close to the true likelihood whenever it could be computed. when computing the exact likelihood was not feasible, we demonstrated the proximity of the upper and lower variational bounds, implying a tight approximation of the likelihood.
minimizing and learning energy functions for side-chain prediction. side-chain prediction is an important subproblem of the general protein folding problem. despite much progress in side-chain prediction, performance is far from satisfactory. as an example, the rosetta program that uses simulated annealing to select the minimum energy conformations, correctly predicts the first two side-chain angles for approximately 72% of the buried residues in a standard data set. is further improvement more likely to come from better search methods, or from better energy functions? given that exact minimization of the energy is np hard, it is difficult to get a systematic answer to this question. in this paper, we present a novel search method and a novel method for learning energy functions from training data that are both based on tree reweighted belief propagation (trbp). we find that trbp can find the global optimum of the rosetta energy function in a few minutes of computation for approximately 85% of the proteins in a standard benchmark set. trbp can also effectively bound the partition function which enables using the conditional random fields (crf) framework for learning. interestingly, finding the global minimum does not significantly improve sidechain prediction for an energy function based on rosetta's default energy terms (less than 0.1%), while learning new weights gives a significant boost from 72% to 78%. using a recently modified rosetta energy function with a softer lennard-jones repulsive term, the global optimum does improve prediction accuracy from 77% to 78%. here again, learning new weights improves side-chain modeling even further to 80%. finally, the highest accuracy (82.6%) is obtained using an extended rotamer library and crf learned weights. our results suggest that combining machine learning with approximate inference can improve the state-of-the-art in side-chain prediction.
reconstructing the evolutionary history of complex human gene clusters. clusters of genes that evolved from single progenitors via repeated segmental duplications present significant challenges to the generation of a truly complete human genome sequence. such clusters can confound both accurate sequence assembly and downstream computational analysis, yet they represent a hotbed of functional innovation, making them of extreme interest. we have developed an algorithm for reconstructing the evolutionary history of gene clusters using only human genomic sequence data. this method allows the tempo of large-scale evolutionary events in human gene clusters to be estimated, which in turn will facilitate primate comparative sequencing studies that will aim to reconstruct their evolutionary history more fully.
orchestration of dna methylation. dna methylation plays an important role in gene regulation. in order to gain a better understanding of the rules governing this epigenetic modification, we have used microarray technology to map dna methylation in the human genome. this analysis has helped decipher the dna sequences involved in setting up the basic global methylation pattern in the early embryo and has revealed the full range of methylation changes that occur in a programmed manner during development. these studies also help explain how specific cpg island genes are targeted for de novo methylation in cancer. 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
identification of deletion polymorphisms from haplotypes. numerous efforts are underway to catalog genetic variation in human populations. while the majority of studies of genetic variation have focused on single base pair differences between individuals, i.e. single nucleotide polymorphisms (snps), several recent studies have demonstrated that larger scale structural variation including copy number polymorphisms and inversion polymorphisms are also common. however, direct techniques for detection and validation of structural variants are generally much more expensive than detection and validation of snps. for some types of structural variation, in particular deletions, the polymorphism produces a distinct signature in the snp data. in this paper, we describe a new probabilistic method for detecting deletion polymorphisms from snp data. the key idea in our method is that we estimate the frequency of the haplotypes in a region of the genome both with and without the possibility of a deletion in the region and apply a generalized likelihood ratio test to assess the significance of a deletion. application of our method to the hapmap phase i data revealed 319 candidate deletions, 142 of these overlap with variants identified in earlier studies, while 177 are novel. using phase ii hapmap data we predict 6730 deletions.
constructing level-2 phylogenetic networks from triplets. jansson and sung showed that, given a dense set of input triplets t (representing hypotheses about the local evolutionary relationships of triplets of taxa), it is possible to determine in polynomial time whether there exists a level-1 network consistent with t, and if so, to construct such a network [24]. here, we extend this work by showing that this problem is even polynomial time solvable for the construction of level-2 networks. this shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily nontree-like. this further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. we also implemented the algorithm and applied it to yeast data.
a fragmentation event model for peptide identification by mass spectrometry. we present in this paper a novel fragmentation event model for peptide identification by tandem mass spectrometry. most current peptide identification techniques suffer from the inaccuracies in the predicted theoretical spectrum, which is due to insufficient understanding of the ion generation process, especially the b/y ratio puzzle. to overcome this difficulty, we propose a novel fragmentation event model, which is based on the abundance of fragmentation events rather than ion intensities. experimental results demonstrate that this model helps improve database searching methods. on ltq data set, when we control the false-positive rate to be 5%, our fragmentation event model has a significantly higher true positive rate (0.83) than sequest (0.73). comparison with mascot exhibits similar results, which means that our model can effectively identify the false positive peptide-spectrum pairs reported by sequest and mascot. this fragmentation event model can also be used to solve the problem of missing peak encountered by de novo methods. to our knowledge, this is the first time the fragmentation preference for peptide bonds is used to overcome the missing-peak difficulty.