waashk/dblp huggingface dataset:
mining protein family specific residue packing patterns from protein structure graphs. finding recurring residue packing patterns, or spatial motifs, that characterize protein structural families is an important problem in bioinformatics. we apply a novel frequent subgraph mining algorithm to three graph representations of protein three-dimensional (3d) structure. in each protein graph, a vertex represents an amino acid. vertex-residues are connected by edges using three approaches: first, based on simple distance threshold between contact residues; second using the delaunay tessellation from computational geometry, and third using the recently developed almost-delaunay tessellation approach.applying a frequent subgraph mining algorithm to a set of graphs representing a protein family from the structural classification of proteins (scop) database, we typically identify several hundred common subgraphs equivalent to common packing motifs found in the majority of proteins in the family. we also use the counts of motifs extracted from proteins in two different scop families as input variables in a binary classification experiment. the resulting models are capable of predicting the protein family association with the accuracy exceeding 90 percent. our results indicate that graphs based on both almost-delaunay and delaunay tessellations are sparser than the contact distance graphs; yet they are robust and efficient for mining protein spatial motif.
tests for gene clustering. comparing chromosomal gene order in two or more related species is an important approach to studying the forces that guide genome organization and evolution. linked clusters of similar genes found in related genomes are often used to support arguments of evolutionary relatedness or functional selection. however, as the gene order and the gene complement of sister genomes diverge progressively due to large scale rearrangements, horizontal gene transfer, gene duplication and gene loss, it becomes increasingly difficult to determine whether observed similarities in local genomic structure are indeed remnants of common ancestral gene order, or are merely coincidences.a rigorous comparative genomics requires principled methods for distinguishing chance commonalities, within or between genomes, from genuine historical or functional relationships. in this paper, we construct tests for significant groupings against null hypotheses of random gene order, taking incomplete clusters, multiple genomes and gene families into account. we consider both the significance of individual clusters of pre-specified genes, and the overall degree of clustering in whole genomes.
geometric algorithms for the analysis of 2d-electrophoresis gels. in proteomics 2-dimensional gel electrophoresis (2-de) is a separation technique for proteins. the resulting protein spots can be identified by either using picking robots and subsequent mass spectrometry or by visual cross inspection of a new gel image with an already analyzed master gel. difficulties especially arise from inherent noise and irregular geometric distortions in 2-de images. aiming at the automated analysis of large series of 2-de images, or at the even more difficult interlaboratory gel comparisons, the bottleneck is to solve the two most basic algorithmic problems with high quality: identifying protein spots and computing a matching between two images. for the development of the analysis software carol at freie universit&auml;t berlin we have reconsidered these two problems and obtained new solutions which rely on methods from computational geometry. their novelties are: 1. spot detection is also possible for complex regions formed by several &ldquo;merged&rdquo; (usually saturated) spots; 2. user-defined landmarks are not necessary for the matching. furthermore, images for comparison are allowed to represent different parts of the entire protein pattern, which only partially &ldquo;overlap&rdquo;. the implementation is done in a client server architecture to allow queries via the internet. we also discuss and point at related theoretical questions in computational geometry.
recent duplication, evolution and assembly of the human genome. it has been estimated that 5% of the human genome consists of interspersed duplicated material that has arisen over the last 30 million years of evolution. two categories of recent duplicated segments can be distinguished: segmental duplications between non-homologous chromosomes (transchromosomal duplications) and duplications largely restricted to a particular chromosome (chromosome-specific duplications). a large proportion of these duplications exhibit an extraordinarily high degree of sequence identity at the nucleotide level (>95%) spanning large (1--100 kb) genomic distances. through processes of paralogous recombination, these same regions are targets for rapid evolutionary turnover among the genomes of closely related primates. the dynamic nature of these regions in terms of recurrent chromosomal structural rearrangement and their ability to create fusion genes from juxtaposed cassettes suggests that duplicative transposition has been an important force in the evolution of our genome. cycles of segmental duplication over periods of evolutionary time may provide the underlying mechanism for domain accretion and the increased modular complexity of the vertebrate proteome. further, our data suggest that a small fraction of important human genes may have emerged recently through duplication processes and will not possess definitive orthologues in the genomes of model organisms. i will discuss computational methods developed in my laboratory to 1) unambiguously identify recent genomic duplicates within the human genome and 2) to assess their importance in hominoid gene innovation. the impact of this chromosomal architecture for assembly of the final draft sequence will be discussed.
the greedy path-merging algorithm for sequence assembly. two different approaches to determining the human genome are currently being pursued: one is the &ldquo;clone-by-clone&rdquo; approach, employed by the publicly-funded. human genome project, and the other is the &ldquo;whole genome shotgun&rdquo; approach, favored by researchers at celera genomics. an interim strategy employed at celera, called hierarchical assembly, makes use of preliminary data produced by both approaches. this paper introduces the bactig ordering problem, which is a key problem that arises in this context, and presents an efficient heuristic called the greedy path-merginq algorithm that performs well on real data.
approximate matching of secondary structures. several methods have been developed for identifying more or less complex rna structures in a genome. whatever the method is, it is always based on the search of conserved primary and secondary structures. while various efficient methods have been developed for searching motifs of the primary structure, usually represented as regular expressions, few effort has been expended in the efficient search of secondary structure signals. by a helix, we mean a structure defined by a combination of sequence and folding constraints. we present a flexible algorithm that searches for all approximate matches of a helix in a genome. helices are represented by special regular expressions, that we call secondary expressions. the method is based on an alignment graph constructed from several copies of a pushdown automaton, arranged one on top of another. the worst time complexity is o(rpn), where n is the size of the genome, p the size of the secondary expression, and r its number of union symbols. we present our results of searching for specific signals of the trna and rnase p rna in two genomes.
protein similarity from knot theory and geometric convolution. shape similarity is one of the most elusive and intriguing questions of nature and mathematics. proteins provide a rich domain in which to test theories of shape similarity. proteins can match at different scales and in different arrangements. sometimes the detection of common local structure is sufficient to infer global alignment of two proteins; at other times it provides false information. proteins with very low sequence identity may share large substructures, or perhaps just a central core. there are even examples of proteins with nearly identical primary sequence in which α-helices have become β-sheets.shape similarity can be formulated (i) in terms of global metrics, such as rmsd or hausdorff distance, (ii) in terms of subgraph isomorphisms, such as the detection of shared substructures with similar relative locations, or (iii) purely topologically, in terms of the cohomology induced by structure preserving transformations. existing protein structure detection programs are built on the first two types of similarity. the third forms the foundations of knot theory.the thesis of this paper is: protein similarity detection leads naturally to an algorithm operating at the metric, relational, and homotopic scales. the paper introduces a definition of similarity based on atomic motions that preserve local backbone topology without incurring significant distance errors. such motions are motivated by the physical requirements for rearranging subsequences of a protein. similarity detection then seeks rigid body motions able to overlay pairs of substructures, each related by a substructure-preserving motion, without necessarily requiring global structure preservation. this definition is general enough to span a wide range of questions: one can ask for full rearrangement of one protein into another while preserving global topology, as in drug design; or one can ask for rearrangements of sets of smaller substructures, each of which preserves local but not global topology, as in protein evolution.in the appendix, we exhibit an algorithm for answering the general question. that algorithm has the complexity of robot motion planning. in the text, we consider a more common case in which one seeks protein similarity by rearrangements of relatively short peptide segments. we exhibit an algorithm based on writhing numbers that runs in time o(n2) to o(n4). we define and use a new datastructure, called geometric self-convolution, within this algorithm.contributions: we believe that this is the first paper to consider carefully the need for combining metric and homotopic qualities in seeking protein similarity. we provide a parameterized definition of similarity that leads naturally to a metric in protein space. we exhibit algorithms for computing the metric and detecting similarity. we report results obtained with three pairs of proteins, each pair exhibiting different typical characteristics.
from profiles to patterns and back again: a branch and bound algorithm for finding near optimal motif profiles. an important part of deciphering gene regulatory mechanisms is discovering transcription factor binding sites. in many cases, these sites can be detected because they are often overrepresented in genomic sequences. the detection of the overrepresented signals in sequences, or motif-finding has become a central problem in computational biology. there are two major computational frameworks for attacking the motif finding problem which differ in their representation of the signals. the most popular is the profile or pssm (position specific scoring matrix) representation. the goal of these algorithms is to obtain probabilistic representations of the overrepresented signals. another is the consensus pattern or pattern with mismatches representation which represents a signal as discrete consensus pattern and allows some mismatches to occur in each instance of the pattern. the advantage of profiles is the expressiveness of their representation while the advantage of the consensus pattern approach is the existence of efficient algorithms that guarantee discovery of the best patterns. in this paper we present a unified framework for motif finding which encompasses both the profile representation and the consensus pattern representation. we prove that the problem of discovering the best profiles can be solved by considering a degenerate version of the problem of finding the best consensus patterns. the main advantage of our framework is that it motivates a novel algorithm, mitra-pssm, which discovers profiles, yet provides some of the guarantees of discovering the best signals. the algorithm searches for best profiles with respect to information content which is the same criterion of popular algorithms such as meme and consensus. mitra-pssm is specifically designed for searching for profiles in this framework and introduces a novel notion of scoring consensus patterns, discrete information content. mitra-pssm is available for public use via webserver at http://www.calit2.net/compbio/mitra/.
new algorithms for the duplication-loss model. we consider the problem of constructing a species tree given a number of gene trees. in the frameworks introduced by goodman et al. [3], page [10], and guig&oacute;, muchnik, and smith [5] this is formulated as an optimization problem; namely, that of finding the species tree requiring the minimum number of duplications and/ or losses in order to explain the gene trees. in this paper, we introduce the width k duplication-loss and width k duplication problems. a gene tree has width k w.r.t. a species tree, if the species tree can be reconciled with the gene tree using at most k simultaneously active copies of the gene along its branches. we explain w.r.t. to the underlying biological model, why this width is typically very small in comparison to the total number of duplications and losses. we show polynomial time algorithms for finding optimal species trees having bounded width w.r.t. at least one of the input gene trees. furthermore, we present the first algorithm for input gene trees that are unrooted. lastly, we apply our algorithms to a dataset from [5] and show a species tree requiring significantly fewer duplications and fewer duplications/losses than the trees given in the original paper.
discovering temporal relations in molecular pathways using protein-protein interactions. the availability of large-scale protein-protein interaction data provides us with many opportunities to study molecular pathways involving proteins. in this paper we propose to mine temporal relations in molecular pathways by protein-protein interaction data. in particular, we model the assembly pathways of protein complexes with interval graphs and determine the temporal order of joining the pathway for proteins by ordering the vertices in the interaction graph. we develop a tool called xronos to perform such a computation. we then apply xronos to the ribosome assembly pathway and present validation results for the obtained ordering. the results are promising and show the potential usage for xronos in the study of molecular pathways.
dna sequence variation among humans and apes (abstract only). in order to shed light on the rate and mode of evolution of dna sequence evolution in the germ line of humans and chimpanzees, we have sequenced 136 kb around the human zfy gene as well as a total of 180 kb of genomic dna surrounding the zfx and zfy genes on the chimpanzee x and y chromosome, respectively. the comparison of the orthologous sequences on the human and chimpanzee sex chromosomes show that whereas the zfx region display 0.8% substitutional differences between the two species, the zfy region display 1.5% differences. by contrast, insertions and deletions show no difference between the two regions. interestingly, transversions show a much more drastic preponderance in the male germ line than transitions, and the insertion of retroviral-like elements seem to occur more frequently in the male than in the female germ line. while data on nucleotide sequence variation in the human nuclear genome have begun to accumulate through comparative sequencing projects at several diseases-associated genes, little is known about genomic variation in non-coding parts of the human genome and practically nothing about the variation in chimpanzee genome. in order to begin to gauge the extent and pattern of point substitutional variation in the non-transcribed parts of the human genome, we have sequenced 10 kb of non-coding dna in a region of low recombination at xq13.3 from 70 humans representing all major language groups of the world. in addition, the same sequence has been determined from 30 chimpanzees, representing all major subspecies, as well as bonobos. comparison to humans reveals an almost four-fold higher diversity and a three-fold greater age of the most recent common ancestor of the chimpanzee sequences. phylogenetic analyses show the sequences from the different chimpanzee subspecies to be intermixed and the distance between some chimpanzee sequences to be greater than the distance between them and the bonobo sequences. these data, as well as preliminary work in the other great apes, indicate that the human genome is unique in carrying extremely little nucleotide diversity.
engineering a scalable placement heuristic for dna probe arrays. design of dna arrays for very large-scale immobilized polymer synthesis (vlsips) [8] seeks to minimize effects of unintended illumination during mask exposure steps. [9, 14] formulate this requirement as the border minimization problem and give methods for placement (at array sites) and embedding (in the mask sequence) of probes in both synchronous and asynchronous regimes. these previous methods do not address several practical details of the application and, more critically, are not scalable to the o(108) probes contemplated for next-generation probe arrays. in this work, we make two main contributions:we give improved dynamic programming algorithms that perform probe embedding to minimize the number border conflicts while accounting for distance- and position-dependent border conflict weights, as well as the presence of polymorphic probes in the instance. we describe and experimentally validate the "engineering" of a scalable, high-quality asynchronous placement heuristic (which is moreover easily parallelizable) for dna array design. our heuristic is enabled by a novel approach for simultaneous re-placement and optimal re-embedding of an "independent set" of probes within a small window of the array..
analysis techniques for microarray time-series data. we introduce new methods for the analysis of short-term time-series data, and apply them to gene expression data in yeast. these include (1) methods for automated period detection in a predominately cycling data set and (2) phase detection between phase-shifted cyclic data sets. we show how to properly correct for the problem of comparing correlation coefficents between pairs of sequences of different lengths and small alphabets. in particular, we show that the correlation coefficient of sequences over alphabets of size two can exhibit very counter-intuitive behavior when compared with the hamming distance. finally, we address the predictability of known regulators via time-series analysis, and show that less than 20% of known regulatory pairs exhibit strong correlations in the cho/spellman data sets. by analyzing known regulatory relationships, we designed an edge detection function which identified candidate regulations with greater fidelity than standard correlation methods.
rnai, genome ultrastructure, and other unexpected tales from the analysis of genetic silencing. the genetic landscape faced by a living cell is constantly changing. developmental transitions, environmental shifts, and pathogenic invasions lend a dynamic character to both the genome and its activity pattern. a variety of natural mechanisms are utilized by cells adapting to genetic change. these include normal developmental mechanisms and a subset of defense systems for responding to pathogens. at the root of these studies are questions of how a cell can distinguish "self" versus "nonself" and "wanted" versus "unwanted" gene expression.investigations of gene silencing in our lab and elswhere have identified a number of structural features that provide an indication of unwanted nucleic acid. one of these features has been double stranded rna (dsrna). absent during "normal" gene expression, dsrna is an essential component in the life cycle of most viruses. by flagging dsrna as an indicator of unwanted rna replication, and by scrupulously avoiding the production of dsrna during most normal gene expression, the cell acquires a modicum of protection from viral infection. the mechanism by which dsrna segments are utilized to trigger silencing of homologous genes, termed rnai, has been a focus of intensive work at many different institutions over the last seven years. this talk will describe aspects of this mechanism, with particular emphasis on the biological role and chemical logic of the interference reaction. 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
whole-genome comparative annotation and regulatory motif discovery in multiple yeast species. in [13] we reported the genome sequences of s. paradoxus, s. mikatae and s. bayanus and compared these three yeast species to their close relative, s. cerevisiae. genome-wide comparative analysis allowed the identification of functionally important sequences, both coding and non-coding. in this companion paper we describe the mathematical and algorithmic results underpinning the analysis of these genomes.we developed statistical methods for the systematic de-novo identification of regulatory motifs. without making use of co-regulated gene sets, we discovered virtually all previously known dna regulatory motifs as well as several noteworthy novel motifs. with the additional use of gene ontology information, expression clusters and transcription factor binding profiles, we assigned candidate functions to the novel motifs discovered.our results demonstrate that entirely automatic genome-wide annotation, gene validation, and discovery of regulatory motifs is possible. our findings are validated by the extensive experimental knowledge in yeast, confirming their applicability to other genomes.
optimizing exact genetic linkage computations. genetic linkage analysis is a challenging application which requires bayesian networks consisting of thousands of vertices. consequently, computing the likelihood of data, which is needed for learning linkage parameters, using exact inference procedures calls for an extremely efficient implementation that carefully optimizes the order of conditioning and summation operations. in this paper we present the use of stochastic greedy algorithms for optimizing this order. our algorithm has been incorporated into the newest version of superlink, which is currently the fastest genetic linkage program for exact likelihood computations in general pedigrees. we demonstrate an order of magnitude improvement in run times of likelihood computations using our new optimization algorithm, and hence enlarge the class of problems that can be handled effectively by exact computations.