waashk/dblp huggingface dataset:
overlapping pools for high throughput targeted resequencing. resequencing genomic dna from pools of individuals is an effective strategy to detect new variants in targeted regions and compare them between cases and controls. there are numerous ways to assign individuals to the pools on which they are to be sequenced. the naïve, disjoint pooling scheme (many individuals to one pool) in predominant use today, offers insight into allele frequencies, but does not offer the identity of an allele carrier. we present a framework for overlapping pool design, where each individual sample is resequenced in several pools (many individuals to many pools). upon discovering a variant, the set of pools where this variant is observed reveals the identity of its carrier. we formalize the mathematical framework for such pool designs, and list the requirements from such designs. next, we build on the theory of error-correcting codes to design arrangements that overcome pitfalls of pooled sequencing. specifically, three practical concerns of low coverage sequencing are investigated: (1) false positives due to errors introduced during amplification and sequencing; (2) false negatives due to undersampling particular alleles aggravated by non-uniform coverage; and consequently (3) ambiguous identification of individual carriers in the presence of errors. we show that in practical parameters of resequencing studies, our designs guarantee high probability of unambiguous singleton carrier identification, while maintaining the features of naïve pools in terms of sensitivity, specificity, and the ability to estimate allele frequencies. we demonstrate the ability of our designs by extracting rare variations on pooled short read data of 12 individuals from the 1000 genome pilot 3 project.
new perspectives on gene family evolution: losses in reconciliation and a link with supertrees. reconciliation between a set of gene trees and a species tree is the most commonly used approach to infer the duplication and loss events in the evolution of gene families, given a species tree. when a species tree is not known, a natural algorithmic problem is to infer a species tree such that the corresponding reconciliation minimizes the number of duplications and/or losses. in this paper, we clarify several theoretical questions and study various algorithmic issues related to these two problems. (1) for a given gene tree t and species tree s, we show that there is a single history explaining t and consistent with s that minimizes gene losses, and that this history also minimizes the number of duplications. we describe a simple linear-time and space algorithm to compute this parsimonious history, that is not based on the lowest common ancestor (lca) mapping approach; (2) we show that the problem of computing a species tree that minimizes the number of gene duplications, given a set of gene trees, is in fact a slight variant of a supertree problem; (3) we show that deciding if a set of gene trees can be explained using only apparent duplications can be done efficiently, as well as computing a parsimonious species tree for such gene trees. we also characterize gene trees that can be explained using only apparent duplications in terms of compatible triplets of leaves.
a statistical framework for the functional analysis of metagenomes. metagenomicstudies consider the genetic makeup of microbial communities as a whole, rather than their individual member organisms. the functional and metabolic potential of microbial communities can be analyzed by comparing the relative abundance of gene families in their collective genomic sequences (metagenome) under different conditions. such comparisons require accurate estimation of gene family frequencies. we present a statistical framework for assessing these frequencies based on the lander-waterman theory developed originally for whole genome shotgun (wgs) sequencing projects. we also provide a novel method for assessing the reliability of the estimations which can be used for removing seemingly unreliable measurements. we tested our method on a wide range of datasets, including simulated genomes and real wgs data from sequencing projects of whole genomes. results suggest that our framework corrects inherent biases in accepted methods and provides a good approximation to the true statistics of gene families in wgs projects.
detection of locally over-represented go terms in protein-protein interaction networks. high-throughput methods for identifying protein-protein interactions produce increasingly complex and intricate interaction networks. these networks are extremely rich in information, but extracting biologically meaningful hypotheses from them and representing them in a human-readable manner is challenging. we propose a method to identify gene ontology terms that are locally over-represented in a subnetwork of a given biological network. specifically, we propose two methods to evaluate the degree of clustering of proteins associated to a particular go term and describe four efficient methods to estimate the statistical significance of the observed clustering. we show, using monte carlo simulations, that our best approximation methods accurately estimate the true p-value, for random scale-free graphs as well as for actual yeast and human networks. when applied to these two biological networks, our approach recovers many known complexes and pathways, but also suggests potential functions for many subnetworks.
boosting protein threading accuracy. protein threading is one of the most successful protein structure prediction methods. most protein threading methods use a scoring function linearly combining sequence and structure features to measure the quality of a sequence-template alignment so that a dynamic programming algorithm can be used to optimize the scoring function. however, a linear scoring function cannot fully exploit interdependency among features and thus, limits alignment accuracy.this paper presents a nonlinear scoring function for protein threading, which not only can model interactions among different protein features, but also can be efficiently optimized using a dynamic programming algorithm. we achieve this by modeling the threading problem using a probabilistic graphical model conditional random fields (crf) and training the model using the gradient tree boosting algorithm. the resultant model is a nonlinear scoring function consisting of a collection of regression trees. each regression tree models a type of nonlinear relationship among sequence and structure features. experimental results indicate that this new threading model can effectively leverage weak biological signals and improve both alignment accuracy and fold recognition rate greatly.
searching protein 3-d structures in linear time. finding similar structures from 3-d structure databases of proteins is becoming more and more important issue in the post-genomic molecular biology. to compare 3-d structures of two molecules, biologists mostly use the rmsd (root mean square deviation) as the similarity measure. we propose new theoretically and practically fast algorithms for the fundamental problem of finding all the substructures of structures in a structure database of chain molecules (such as proteins), whose rmsds to the query are within a given constant threshold. we first propose a breakthrough linear-expected-time algorithm for the problem, while the previous best-known time complexity was o(nlogm), where n is the database size and m is the query size. for the expected time analysis, we propose to use the random-walk model (or the ideal chain model) as the model of average protein structures. we furthermore propose a series of preprocessing algorithms that enable faster queries. we checked the performance of our linear-expected-time algorithm through computational experiments over the whole pdb database. according to the experiments, our algorithm is 3.6 to 28 times faster than previously known algorithms for ordinary queries. moreover, the experimental results support the validity of our theoretical analyses.
cross species expression analysis of innate immune response. the innate immune response is the first line of host defense against infections. this system employs a number of different types of cells which in turn activate different sets of genes. microarray studies of human and mouse cells infected with various pathogens identified hundreds of differentially expressed genes. however, combining these datasets to identify common and unique response patterns remained a challenge. we developed methods based on probabilistic graphical models to combine expression experiments across species, cells and pathogens. our method analyzes homologous genes in different species concurrently overcoming problems related to noise and orthology assignments. using our method we identified both core immune response genes and genes that are activated in macrophages in both human and mouse but not in dendritic cells, and vice versa. our results shed light on immune response mechanisms and on the differences between various types of cells that are used to fight infecting bacteria.supporting website: http://www.cs.cmu.edu/~lyongu/pub/immune/
an adaptive and memory efficient algorithm for genotype imputation. genome wide association studies have proven to be a highly successful method for identification of genetic loci for complex phenotypes in both humans and model organisms. these large scale studies rely on the collection of hundreds of thousands of single nucleotide polymorphisms (snps) across the genome. standard high-throughput genotyping technologies capture only a fraction of the total genetic variation. recent efforts have shown that it is possible to "impute" with high accuracy the genotypes of snps that are not collected in the study provided that they are present in a reference data set which contains both snps collected in the study as well as other snps. we here introduce a novel hmm based technique to solve the imputation problem that addresses several shortcomings of existing methods. first, our method is adaptive which lets it estimate population genetic parameters from the data and be applied to model organisms that have very different evolutionary histories. compared to traditional methods, our method is up to ten times more accurate on model organisms such as mouse. second, our algorithm scales in memory usage in the number of collected markers as opposed to the number of known snps. this issue is very relevant due to the size of the reference data sets currently being generated. we compare our method over mouse and human data sets to existing methods and show that each has either comparable or better performance and much lower memory usage. the method is available for download at http://genetics.cs.ucla.edu/eminim .
the multi-state perfect phylogeny problem with missing and removable data: solutions via integer-programming and chordal graph theory. the multi-state perfect phylogeny problem is an extension of the binary perfect phylogeny problem, allowing characters to take on more than two states. in this paper we consider three problems that extend the utility of the multi-state perfect phylogeny model: the missing data (md) problem where some entries in the input are missing and the question is whether (bounded) values for the missing data can be imputed so that the resulting data has a multi-state perfect phylogeny; the character-removal (cr) problem where we want to minimize the number of characters to remove from the data so that the resulting data has a multi-state perfect phylogeny; and the missing-data character-removal (mdcr) problem where the input has missing data and we want to impute values for the missing data to minimize the solution to the resulting character-removal problem.we detail integer linear programming (ilp) solutions to these problems for the special case of three permitted states per character and report on extensive empirical testing of these solutions. then we develop a general theory to solve the md problem for an arbitrary number of permitted states, using chordal graph theory and results on minimal triangulation of non-chordal graphs. this establishes new necessary and sufficient conditions for the existence of a perfect phylogeny with (or without) missing data. we implement the general theory using integer linear programming, although other optimization methods are possible. we extensively explore the empirical behavior of the general solution, showing that the methods are very practical for data of size and complexity that is characteristic of many current applications in phylogenetics. some of the empirical results for the md problem with an arbitrary number of permitted states are very surprising, suggesting the existence of additional combinatorial structure in multi-state perfect phylogenies.
a probabilistic graphical model for ab initio folding. despite significant progress in recent years, ab initio folding is still one of the most challenging problems in structural biology. this paper presents a probabilistic graphical model for ab initio folding, which employs conditional random fields (crfs) and directional statistics to model the relationship between the primary sequence of a protein and its three-dimensional structure. different from the widely-used fragment assembly method and the lattice model for protein folding, our graphical model can explore protein conformations in a continuous space according to their probability. the probability of a protein conformation reflects its stability and is estimated from psi-blast sequence profile and predicted secondary structure. experimental results indicate that this new method compares favorably with the fragment assembly method and the lattice model.
evaluating between-pathway models with expression data. between-pathway models (bpms) are network motifs consisting of pairs of putative redundant pathways. in this paper, we show how adding another source of high-throughput data, microarray gene expression data from knockout experiments, allows us to identify a compensatory functional relationship between genes from the two bpm pathways. we evaluate the quality of the bpms from four different studies, and we describe how our methods might be extended to refine pathways.
incorporating nucleosomes into thermodynamic models of transcription regulation. transcriptional control is central to many cellular processes and consequently, much effort has been devoted to understanding its underlying mechanisms. recently, it has become evident that the organization of nucleosomes along promoter regions has an important role in transcriptional control, since most transcription factors cannot bind to sequences bound by nucleosomes, and thus compete with nucleosomes for dna access. this competition is governed by the relative concentrations of nucleosomes and transcription factors and by their respective sequence binding preferences. even though competition of nucleosomes and transcription factors may have significant effects on transcription, a mechanistic understanding of its quantitative consequences for gene expression is still missing. here we employ a thermodynamic framework based on fundamental principles of statistical mechanics to theoretically explore the effect that different nucleosome organizations along promoters have on the activation dynamics of promoters in response to varying concentrations of the regulating transcription factors. we show that even simple landscapes of nucleosome organization reproduce experimental results regarding the effect of nucleosomes as general repressors and as generators of obligate binding cooperativity between transcription factors. our modeling framework also allows us to characterize the effects that various sequence elements of promoters will have on the induction threshold and on the shape of the promoter activation curves.
on the relationship between dna periodicity and local chromatin structure. dna periodicity and its relationship to the formation of nucleosomes has been investigated extensively using autocorrelation and fourier transform methods. we provide a precise treatment of the mathematical foundation for this type of analysis, and we apply the resulting method to quantify dinucleotide periodicity in several datasets. we begin by demonstrating, via simulation, the sensitivity of our method relative to previous methods. we then provide evidence of pervasive ~10 bp periodicity in s. cerevisiae, with stronger periodicity in sequences associated with positioned nucleosomes. in human, although repeat-masked sequences do not exhibit significant periodicity on average, we find that experimentally determined nucleosome positions show a periodicity of the aa dinucleotide similar to that found in s. cerevisiae. furthermore, transcription start sites in the human genome are marked by a sharp drop in the 10 bp periodicity of the aa dinucleotide, while occupied ctcf sites are surrounded by a local increase.
identification and frequency estimation of inversion polymorphisms from haplotype data. structural rearrangements, including copy-number alterations and inversions, are increasingly recognized as an important contributor to human genetic variation. copy number variants are readily measured via array-based techniques like comparative genomic hybridization, but copy-neutral variants such as inversion polymorphisms remain difficult to identify without whole genome sequencing. we introduce a method to identify inversion polymorphisms and estimate their frequency in a population using readily available single nucleotide polymorphism (snp) data. our method uses a probabilistic model to describe a population as a mixture of forward and inverted chromosomes and identifies putative inversions by characteristic differences in haplotype frequencies around inversion breakpoints. on simulated data, our method accurately predicts inversions with frequencies as low as 25% in the population and reliably estimates inversion frequencies over a wide range. on the human hapmap phase 2 data, we predict between 88 and 142 inversion polymorphisms with frequency ranging from 20 to 92 percent. many of these correspond to known inversions or have other evidence supporting them, and the predicted inversion frequencies largely agree with the limited information presently available.
how many bootstrap replicates are necessary?. phylogenetic bootstrapping (bs) is a standard technique for inferring confidence values on phylogenetic trees that is based on reconstructing many trees from minor variations of the input data, trees called replicates. bs is used with all phylogenetic reconstruction approaches, but we focus here on the most popular, maximum likelihood (ml). because ml inference is so computationally demanding, it has proved too expensive to date to assess the impact of the number of replicates used in bs on the quality of the support values. for the same reason, a rather small number (typically 100) of bs replicates are computed in real-world studies. stamatakis et al. recently introduced a bs algorithm that is 1---2 orders of magnitude faster than previous techniques, while yielding qualitatively comparable support values, making an experimental study possible.in this paper, we propose stopping criteria, that is, thresholds computed at runtime to determine when enough replicates have been generated, and report on the first large-scale experimental study to assess the effect of the number of replicates on the quality of support values, including the performance of our proposed criteria. we run our tests on 17 diverse real-world dna, single-gene as well as multi-gene, datasets, that include between 125 and 2,554 sequences. we find that our stopping criteria typically stop computations after 100---500 replicates (although the most conservative criterion may continue for several thousand replicates) while producing support values that correlate at better than 99.5% with the reference values on the best ml trees. significantly, we also find that the stopping criteria can recommend very different numbers of replicates for different datasets of comparable sizes.our results are thus two-fold: (i) they give the first experimental assessment of the effect of the number of bs replicates on the quality of support values returned through bootstrapping; and (ii) they validate our proposals for stopping criteria. practitioners will no longer have to enter a guess nor worry about the quality of support values; moreover, with most counts of replicates in the 100---500 range, robust bs under ml inference becomes computationally practical for most datasets. the complete test suite is available at http://lcbb.epfl.ch/bs.tar.bz2 and bs with our stopping criteria is included in raxml 7.1.0.
protein fragment swapping: a method for asymmetric, selective site-directed recombination. this paper presents a new approach to site-directed recombination, swapping combinations of selected discontiguous fragments from a source protein in place of corresponding fragments of a target protein. by being both asymmetric (differentiating source and target) and selective (swapping discontiguous fragments), our method focuses experimental effort on a more restricted portion of sequence space, constructing hybrids that are more likely to have the properties that are the objective of the experiment. furthermore, since the source and target need to be structurally homologous only locally (rather than overall), our method supports swapping fragments from functionally important regions of a source into a target "scaffold"; e.g., to humanize an exogenous therapeutic protein. a protein fragment swapping plan is defined by the residue position boundaries of the fragments to be swapped; it is assessed by an average potential score over the resulting hybrid library, with singleton and pairwise terms evaluating the importance and fit of the swapped residues. while we prove that it is np-hard to choose an optimal set of fragments under such a potential score, we develop an integer programming approach, which we call swagmer, that works very well in practice. we demonstrate the effectiveness of our method in two types of swapping problem: selective recombination between beta-lactamases and activity swapping between glutathione transferases. we show that the selective recombination approach generates a better plan (in terms of resulting potential score) than a traditional site-directed recombination approach. we also show that in both cases the optimized experiment is significantly better than one that would result from stochastic methods.
storage and retrieval of individual genomes. a repetitive sequence collection is one where portions of a base sequence of length n are repeated many times with small variations, forming a collection of total length n. examples of such collections are version control data and genome sequences of individuals, where the differences can be expressed by lists of basic edit operations. flexible and efficient data analysis on a such typically huge collection is plausible using suffix trees. however, suffix tree occupies o(n logn) bits, which very soon inhibits in-memory analyses. recent advances in full-text self-indexing reduce the space of suffix tree to o(n log¿) bits, where ¿ is the alphabet size. in practice, the space reduction is more than 10-fold, for example on suffix tree of human genome. however, this reduction factor remains constant when more sequences are added to the collection.we develop a new family of self-indexes suited for the repetitive sequence collection setting. their expected space requirement depends only on the length n of the base sequence and the number s of variations in its repeated copies. that is, the space reduction factor is no longer constant, but depends on n/n.we believe the structures developed in this work will provide a fundamental basis for storage and retrieval of individual genomes as they become available due to rapid progress in the sequencing technologies.