waashk/dblp huggingface dataset:
efficient algorithms for lateral gene transfer problems. this paper develops a model for lateral gene transfer events (a.k.a. horizontal gene transfer events) between a set of gene trees t1, t2, &hellip;, tk and a species tree s. to the best of our knowledge, this model possesses a higher degree of biological and mathematical soundness than any other model proposed in the literature. among other biological considerations, the model respects the partial order of evolution implied by s. within our model, we identify an activity parameter that measures the number of genes that are allowed to be simultaneously active in the genome of a taxa and show that finding the most parsimonious scenario that reconciles the disagreeing gene trees with the species tree is doable in polynomial time when the activity level and number of transfers are small, but intractable in general. to the best of our knowledge, all other models proposed in the literature assume implicitly that the activity is one. finally, using a dataset of bacterial gene sequences from [4], our implementations found 5 optimal scenarios; one of which is the scenario proposed by the authors in [4].
association mapping of complex diseases with ancestral recombination graphs: models and efficient algorithms. association, or ld (linkage disequilibrium), mapping is an intensely-studied approach to gene mapping (genome-wide or in candidate regions) that is widely hoped to be able to efficiently locate genes influencing both complex and mendelian traits. the logic underlying association mapping implies that the best possible mapping results would be obtained if the genealogical history of the sampled individuals were explicitly known. such a history would be in the form of an "ancestral recombination graph (arg)". but despite the conceptual importance of genealogical histories to association mapping, few practical association mapping methods have explicitly used derived genealogical aspects of args. two notable exceptions are [35] and [23]. in this paper we develop an association mapping method that explicitly constructs and samples minargs (args that minimize the number of recombinations). we develop an arg sampling method that provably samples minargs uniformly at random, and that is practical for moderate sized datasets. we also develop a different, faster, arg sampling method that still samples from a well-defined subspace of args, and that is practical for larger sized datasets. we present novel efficient algorithms on extensions of the "phenotype likelihood" problem, a key step in the method in [35]. we also prove that computing the phenotype likelihood for a different natural extension of the penetrance model in [35] is np-hard, answering a question unresolved in that paper. finally, we put all of these results into practice, and examine how well the implemented methods perform, compared to the results in [35]. the empirical results show great speed ups, and definite but sometimes small, improvements in mapping accuracy. speed is particularly important in doing genome-wide scans for causative mutations.
optimizing for success: a new score function for distantly related protein sequence comparison. the exponential growth of the sequence data produced by the genome projects motivates the development of better ways of inferring structural and functional information about those newly sequenced proteins. looking for homologies between these probe protein sequences and other protein sequences in the database has proved to be one of the most useful current techniques. this procedure, known as sequence comparison, relies on the use of an appropriate score function that discriminates homologs from non-homologs. current score functions have difficulty identifying distantly-related homologs with low sequence similarity. as a result, there is an increased demand for a new score function that yields statistically-significant higher scores for all the pairs of homologous protein sequences including such distantly-related homologs. we present a new method for generating a score function by optimizing it for successful discrimination between homologous and unrelated proteins. the new score function (optima) out-performs other commonly used substitution matrices for the detection of distantly related protein sequences.
using bayesian networks to analyze expression data. dna hybridization arrays simultaneously measure the expression level for thousands of genes. these measurements provide a &ldquo;snapshot&rdquo; of transcription levels within the cell. a major challenge in computational biology is to uncover, from such measurements, gene/protein interactions and key biological features of cellular systems. in this paper, we propose a new framework for discovering interactions between genes based on multiple expression measurements this framework builds on the use of bayesian networks for representing statistical dependencies. a bayesian network is a graph-based model of joint multi-variate probability distributions that captures properties of conditional independence between variables. such models are attractive for their ability to describe complex stochastic processes, and for providing clear methodologies for learning from (noisy) observations. we start by showing how bayesian networks can describe interactions between genes. we then present an efficient algorithm capable of learning such networks and statistical method to assess our confidence in their features. finally, we apply this method to the s. cerevisiae cell-cycle measurements of spellman et al. [35] to uncover biological features
a structural em algorithm for phylogenetic inference. a central task in the study of evolution is the reconstruction of a phylogenetic tree from sequences of current-day taxa. a well supported approach to tree reconstruction performs maximum likelihood (ml) analysis. unfortunately, searching for the maximum likelihood phylogenetic tree is computationally expensive. in this paper, we describe a new algorithm that uses structural-em for learning maximum likelihood trees. this algorithm is similar to the standard em method for estimating branch lengths, except that during iterations of this algorithms the topology is improved as well as the branch length. the algorithm performs iterations of two steps. in the e-step, we use the current tree topology and branch lengths to compute expected sufficient statistics, which summarize the data. in the m-step, we search for a topology that maximizes the likelihood with respect to these expected sufficient statistics. as we show, searching for better topologies inside the m-step can be done efficiently, as opposed to standard search over topologies. we prove that each iteration of this procedure increases the likelihood of the topology, and thus the procedure must converge. we evaluate our new algorithm on both synthetic and real sequence data, and show that it is both dramatically faster and finds more plausible trees than standard search for maximum likelihood phylogenies.
large scale reconstruction of haplotypes from genotype data. critical to the understanding of the genetic basis for complex diseases is the modeling of human variation. most of this variation can be characterized by single nucleotide polymorphisms (snps) which are mutations at a single nucleotide position. to characterize an individual's variation, we must determine an individual's haplotype or which nucleotide base occurs at each position of these common snps for each chromosome. in this paper, we present results for a highly accurate method for haplotype resolution from genotype data. our method leverages a new insight into the underlying structure of haplotypes which shows that snps are organized in highly correlated "blocks". the majority of individuals have one of about four common haplotypes in each block. our method partitions the snps into blocks and for each block, we predict the common haplotypes and each individual's haplotype. we evaluate our method over biological data. our method predicts the common haplotypes perfectly and has a very low error rate (0.47%) when taking into account the predictions for the uncommon haplotypes. our method is extremely efficient compared to previous methods, (a matter of seconds where previous methods needed hours). its efficiency allows us to find the block partition of the haplotypes, to cope with missing data and to work with large data sets such as genotypes for thousands of snps for hundreds of individuals. the algorithm is available via webserver at http://www.cs.columbia.edu/compbio/hap.
optimal sequencing by hybridization in rounds. sequencing by hybridization (sbh) is a method for reconstructing a sequence over a small finite alphabet from a collection of probes (substrings). substring queries can be arranged on an array (sbh chip) and then a combinatorial method is used to construct the sequence from its collection of probes. technological constraints limit the number of substring queries that can be placed on a single sbh chip. we develop an idea of margaritis and skiena and propose an algorithm that uses a series of small sbh chips to sequence long strings while the number of probes used matches the information theoretical lower bound up to a constant factor.
algorithms for inferring cis-regulatory structures and protein interaction networks. a major focus of functional genomics today is the discovery of the interactions between genes and proteins that regulate the transcription of genes and the responses of cells to external signals. the speaker will describe his recent efforts with several coworkers to solve pieces of this puzzle. the work divides into several parts: a new approach to the recognition of transcription-factor binding sites, based on the principle that transcription factors divide naturally into families such as the leucine zippers and the zinc fingers, and that the binding site motifs for transcription factors within the same family have common features. these features may be obscure at the sequence level, but can be characterized at a higher level of description. by discovering and modeling such meta-sequence features one can improve the sensitivity and specificity with which binding sites can be determined for transcription factors within a family. [5], [6] an algorithm and an associated web-based tool for finding recurrent cis-regulatory modules in the promoter regions of human genes. each such module consists of a set of transcription factors that often bind to the same promoter regions and collectively enhance or inhibit the transcription of the corresponding genes. [4] an algorithm for minimizing the number of gene perturbation experiments required to reconstruct signal transduction pathways whose regulatory structures can be described within the mathematical framework of chain functions. [1] algorithms for discovering protein complexes and regulatory pathways that are conserved in evolution, using protein sequence data and protein-protein interaction data for two or more organisms. [2], [3].
applied computational genomics: polymorphism prediction, data mining and genomic analysis. with the "completion" of the first genome, the daily analysis of genomic variation and the transcriptome, and new technologies amassing proteome data, the need for computational tools, inspired by biomedical insight and need are being developed by many groups to help everybody reduce this data to knowledge. to attain understanding from this data, several things are now required for progress; applied computational tools, access to phenotype presenting patients/biological material (and their genotype), and experts to assimilate this information. in this talk, i will describe efforts within our laboratory to develop and then validate some applied computational tools that are then used by our expert collaborators and us. these include: 1) computer algorithms and codes that inspect the genome (coding and intronic) for highly probable simple sequence repeat and single nucleotide polymorphisms; 2) techniques and applications to better identify information in text databases; 3) software to integrate data from some of the many valuable public databases with experimental data (expression and polymorphism), and 4) software to do integrated analysis and interactive visualization of genomic sequence dat.each of our software applications is applied to biomedical problems to validate their utility and verify their accuracy, which can only be done by returning to the wet laboratory. the biomedical areas under investigation include cancer, cardiac disease, development, inflammation and infection. this approach has led to gene discoveries, phenotype causing polymorphisms and has inspired research directions for which the final answer is not yet in.bioinformatics tools often can generate many more "leads" than are possible to pursue with existing technology. this has required us to develop some new technologies and laboratory techniques. for example, we have developed a method and apparatus that is in daily use for the synthesis of custom, software-directed high-density oligonucleotide arrays used for re-sequencing, methlyation analysis and comparative genomic hybridization. this device, called doc (digital optical chemistry), enables us to manufacture "affymetrix-style" arrays with up to 192,000 features. other apparatus, such as high-throughput oligo synthesizers, hyperspectral imaging scanners/microscopes and array spotting robots were also created as needed.this presentation will focus on our applied computational tools and the biomedical observations made with them and touch on how some of the hardware technologies have accelerated that process.much of the software and databases we develop are available for public use via our www site at http://innovation.swmed.edu/. this work is supported by the nih, the state of texas and the p.o'b. montgomery distinguished chair.
separtating repeats in dna sequence assembly. one of the key open problems in large-scale dna sequence assembly is the correct reconstruction of sequences that contain repeats. a long repeat can confound a sequence assembler into falsely overlaying fragments that sample its copies, effectively compressing out the repeat in the reconstructed sequence. we call the task of correcting this compression by separating the overlaid fragments into the distinct copies they sample, the repeat separation problem. we present a rigorous formulation of repeat separation in the general setting without prior knowledge of consensus sequences of repeats or their number of copies. our formulation decomposes the task into a series of four subproblems, and we design probabilistic tests or combinatorial algorithms that solve each subproblem. the core subproblem separates repeats using the so-called k-median problem in combinatorial optimization, which we solve using integer linear-programming. experiments with an implementation show we can separate fragments that are overlaid at 10 times the coverage with very few mistakes in a few seconds of computation, even when the sequencing error rate and the error rate between copies are identical. to our knowledge this is the first rigorous and fully general approach to separating repeats that directly addresses the problem.
aligning alignments exactly. a basic computational problem that arises in both the construction and local-search phases of the best heuristics for multiple sequence alignment is that of aligning the columns of two multiple alignments. when the scoring function is the sum-of-pairs objective and induced pairwise alignments are evaluated using linear gap-costs, we call this problem aligning alignments. while seemingly a straightforward extension of two-sequence alignment, we prove it is actually np-complete. as explained in the paper, this provides the first demonstration that minimizing linear gap-costs, in the context of multiple sequence alignment, is inherently hard.we also develop an exact algorithm for aligning alignments that is remarkably efficient in practice, both in time and space. even though the problem is np-complete, computational experiments on both biological and simulated data show we can compute optimal alignments for all benchmark instances in two standard datasets, and solve very-large random instances with highly-gapped sequences.
finding motifs in the twilight zone. we introduce the notion of a multiprofile and use it for finding subtle motifs in dna sequences. multiprofiles generalize the notion of a profile and allow one to detect subtle consensus sequences that escape detection by the standard profiles. our multiprofiler algorithm outperforms other leading motif finding algorithms in a number of synthetic models. moreover, it can be shown that in some previously studied motif models, multiprofiler is capable of pushing the performance envelope to its theoretical limits.
maximum likelihood resolution of multi-block genotypes. we present a new algorithm for the problems of genotype phasing and block partitioning. our algorithm is based on a new stochastic model, and on the novel concept of probabilistic common haplotypes. we formulate the goals of genotype resolving and block partitioning as a maximum likelihood problem, and solve it by an em algorithm. when applied to real biological snp data, our algorithm outperforms two state of the art phasing algorithms. our algorithm is also considerably more sensitive and accurate than a previous method in predicting and identifying disease association.
invited presentation: introns and modules in ancient conserved genes (abstract only). we study the correlation between introns and modules, compact regions of protein structure, in genes whose products have a known 3-dimensional structre and which are homologous between bacteria and eukaryotes. using two definitions of modules, we show that phase zero introns, those that lie between the codons, are significantly correlated with the boundaries of modules while introns that lie in phases one and two, that interrupt the codons are not so correlated. furthermore, intron positions that are philogenetically ancient, matching between two kingdomes, are more correlated with module boundaries than are other positions. we will discuss the significance of these findings, which suggest that some of the phase zero introns are residues of the original construction of the genes while the phase one and two introns may have been added later in evolution. 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
finding recurrent sources in sequences. many genomic sequences and, more generally, (multivariate) time series display tremendous variability. however, often it is reasonable to assume that the sequence is actually generated by or assembled from a small number of sources, each of which might contribute several segments to the sequence. that is, there are h hidden sources such that the sequence can be written as a concatenation of k > h pieces, each of which stems from one of the h sources. we define this (k,h)-segmentation problem and show that it is np-hard in the general case. we give approximation algorithms achieving approximation ratios of 3 for the l1 error measure and √5 for the l2 error measure, and generalize the results to higher dimensions. we give empirical results on real (chromosome 22) and artificial data showing that the methods work well in practice.
evolutionary features of genomes as disclosed by comparative analysis of complete genome sequences (abstract only). our comparisons of complete genome sequences revealed that the genome structures have been extensively shuffled among eubacteria, particularly when the orders of orthologous genes were examined. moreover, archaebacterial and eukaryotic genome structures were found to be unstable, too, as were the cases of eubacteria. we then turned our attention to operon structures, which were expected to be well conserved during evolution because of their regulatory importance. surprisingly enough, however, we found that even within operons, gene orders have not been conserved, with exception to only a few cases such as ribosomal operons. when we reconstructed the ancestral genome structure of eubacteria and archaebacteria, and examined the relative instability of the genome structures among eubacteria, we found that there were differences in the degree of the genome instability among the examined species. the genome instability appears to be correlated with the number of insertion sequences. interestingly enough, the intensity of the intrastrand bias of nucleotide composition (g-c skew) was found to be affected by the genome instability, implying that accumulation of strand-specific mutations depends heavily upon the stability of a genome. these findings imply that the gene orders have not been essential for survival of microbes in long-term evolution, and that the evolutionary instability of the genome structures is an intrinsic nature common to eubacteria, archaebacteria and eukaryotes. for eukaryotic genomes, we found that a lot of gene fusion events might have happened in the early evolution of eukaryotes so as to compensate for the loss of bacterial operon structures. the evolutionary instability of the genome structures can be one of the most important factors in understanding the evolutionary processes of the genome evolution.
efficient algorithms for protein sequence design and the analysis of certain evolutionary fitness landscapes. protein sequence design is a natural inverse problem to protein structure prediction: given a target structure in three dimensions, we wish to design an amino acid sequence that is likely fold to it. a model of sun, brem, chan, and dill casts this problem as an optimization on a space of sequences of hydrophobic (h) and polar (p) monomers; the goal is to find a sequence which achieves a dense hydrophobic core with few solvent-exposed hydrophobic residues. sun et al. developed a heuristic method to search the space of sequences, without a guarantee of optimality or near-optimality; hart subsequently raised the computational tractability of constructing an optimal sequence in this model as an open question. here we resolve this question by providing an efficient algorithm to construct optimal sequences; our algorithm has a polynomial running time, and performs very efficiently in practice. we illustrate the implementation of our method on structures drawn from the protein data bank. we also consider extensions of the model to larger amino acid alphabets, as a way to overcome the limitations of the binary h/p alphabet. we show that for a natural class of arbitrarily large alphabets, it remains possible to design optimal sequences efficiently. finally, we analyze some of the consequences of this sequence design model for the study of evolutionary fitness landscapes. a given target structure may have many sequences that are optimal in the model of sun et al.; following a notion raised by the work of j. maynard smith, we can ask whether these optimal sequences are ``connected'''' by successive point mutations. we provide a polynomial-time algorithm to decide this connectedness property, relative to a given target structure. we develop the algorithm by first solving an analogous problem expressed in terms of submodular functions, a fundamental object of study in combinatorial optimization.
reconciliation problems for duplication, loss and horizontal gene transfer. this paper presents a model of reconciling a species tree and a gene tree in an extended duplication-loss model. in the first part the definition of a model is introduced. in the second the horizontal transfer is defined and a new polynomial reconciliation algorithm is presented. we prove np-completeness of the important problem related to the reconstruction of the species relationships with transfers from a given set of gene family trees. some new problems are stated. we present a simple biological example.