waashk/dblp huggingface dataset:
transforming men into mice: the nadeau-taylor chromosomal breakage model revisited. although analysis of genome rearrangements was pioneered by dobzhansky and sturtevant 65 years ago, we still know very little about the rearrangement events that produced the existing varieties of genomic architectures. the genomic sequences of human and mouse provide evidence for a larger number of rearrangements than previously thought and shed some light on previously unknown features of mammalian evolution. in particular, they reveal extensive re-use of breakpoints from the same relatively short regions. our analysis implies the existence of a large number of very short "hidden" synteny blocks that were invisible in comparative mapping data and were not taken into account in previous studies of chromosome evolution. these blocks are defined by closely located breakpoints and are often hard to detect. our result is in conflict with the widely accepted random breakage model of chromosomal evolution. we suggest a new "fragile breakage" model of chromosome evolution that postulates that breakpoints are chosen from relatively short fragile regions that have much higher propensity for rearrangements than the rest of the genome.
repeat classification and fragment assembly. repetitive sequences make up a significant fraction of almost any genome and an important and still open question in bioinformatics is how to represent all repeats in dna sequences. we propose a radically new approach to repeat classification that is motivated by the fundamental topological notion of quotient spaces. a torus or klein bottle are examples of quotient spaces that can be obtained from a square by gluing some points. our new repeat classification algorithm is based on the observation that the alignment-induced quotient space of a dna sequence compactly represents all sequence repeats. this observation leads to a simple and efficient solution of the repeat classification problem as well as new approaches to fragment assembly and multiple alignment.
a new approach to fragment assembly in dna sequencing. for the last twenty years fragment assembly in dna sequencing followed the &ldquo;overlap - layout - consensus&rdquo; paradigm that is used in all currently available assembly tools. although this approach proved to be useful in assembling clones, it faces difficulties in genomic shotgun assembly: the existing algorithms make assembly errors and are often unable to resolve repeats even in prokaryotic genomes. biologists are well-aware of these errors and are forced to carry additional experiments to verify the assembled contigs. we abandon the classical &ldquo;overlap - layout - consensus&rdquo; approach in favor of a new eulerian superpath approach that, for the first time, resolves the problem of repeats in fragment assembly. our main result is the reduction of the fragment assembly to a variation of the classical eulerian path problem. this reduction opens new possibilities for repeat resolution and allows one to generate error-free solutions of the large-scale fragment assembly problems. the major improvement of euler over other algorithms is that it resolves all repeats except long perfect repeats that are theoretically impossible to resolve without additional experiments.
structured motifs search. in this paper we describe an algorithm for the localization of structured models, i.e. sequences of (simple) motifs and distance constraints. it basically combines standard pattern matching procedures with a constraint satisfaction solver, and it has the ability, not present in similar tools, to search for partial matches. a significant feature of our approach, especially in terms of efficiency for the application context, is that the (potentially) exponentially many solutions to the considered problem are represented in compact form as a graph. moreover, the time and space necessary to build the graph are linear in the number of occurrences of the component patterns.
probabilities for having a new fold on the basis of a map of all protein sequences. it is a major problem in the study of protein structure to predict which proteins have new, currently unknown structural folds. in an attempt to address this problem we studied the location of all proteins with solved structures within the map of all known protein sequences provided by protomap. the mutual distances in this map among solved structures are used to derive a probabilistic model from which we infer an estimate for the probability of an unsolved protein to have a new fold. the probabilities were based on data from scop release 1.37. the results were evaluated against the more recent scop pre-release 1.41. our predicted probabilities for unsolved proteins to have a new fold are very well correlated with the proportion of new folds among recently released structures. thus, information about the structure of proteins can be inferred from a global relational view of protein sequences. finally, the same procedure was applied to estimate probabilities on the basis of scop 1.41. a list of the highest scoring proteins is provided: these are about 80 non-membranous proteins that belong to clusters with more than 5 proteins and achieve the highest probability to have a new fold. a rational selection for 3d determination of those targets is expected to accelerate the pace of new fold discovery.
sequencing-by-hybridization at the information-theory bound: an optimal algorithm. in a recent paper [pfu99) we have introduced a novel probing scheme for dna sequencing by hybridization (sbh). the new gapped-probe scheme combines natural and universal bases in a well defined periodic pattern. it was shown in [pfu99] that the performance of the gapped-probe scheme (in terms of the length of a sequence that can be uniquely reconstructed using a given library size of probes) is significantly better than the standard scheme based on oligomer probes. in this paper we present and analyze a new, more powerful, sequencing algorithm for the gapped-probe scheme. we prove that the new algorithm exploits the full potential of the sbh technology with high-confidence performance, that comes within a small constant factor (about 2) of the information-theory bound. moreover, this performance is achieved while maintaining running time linear in the target sequence length.
imposing specificity by regulated localization (abstract only). many biologically important enzymes &mdash; rna polymerases, rna splicing enzymes, ubiquinating enzymes, certain kinases and proteases &mdash; are &ldquo;`regulated&rdquo;' by being brought to one or another of many potential substrates by auxiliary docking proteins (e.g. transcriptional activators). these regulatory interactions require interactions between simple adhesive (but specific) surfaces. this kind of regulation is highly `evolvable' : new and expanded meanings to signals are readily generated by simple changes in protein surfaces.
string barcoding: uncovering optimal virus signatures. there are many critical situations when one needs to rapidly identify an unidentified pathogen from among a given set of previously sequenced pathogens. dna or rna hybridization chips can be designed for such identifications. each cell in the chip can report the presence or absence of a specific substring of dna in the unidentified pathogen. properly designed, the collection of reports obtained from the cells can uniquely identify any pathogen in the set, or determine that the unidentified pathogen is not in the set. there is a limit to the number of cells on a chip, and a range of substring lengths that a cell can handle. so, given the full sequences of a set of pathogens, the problem is to design the chip by selecting the smallest set of substrings of the appropriate lengths, so that each pathogen in the set has a unique set of cells that report a substring. for any given pathogen, the set of reporting cells is its signature, and hence the entire system is a "barcode" system for the pathogens.previous work addressed this problem [1], but focused on pathogens of bacterial size, and hence had to make many compromises for the sake of efficiency. the substrings lengths were severely restricted, and no optimality or near-optimality was guaranteed. in this paper, we focus on viral-size pathogens. we show that for genomes of this size, it is practical to solve the barcode design problem optimally, or near-optimally, without artificially constraining the problem. we also efficiently find barcodes that provide a level of redundancy, tolerating a number of errors or mutations. the key technical ideas are the use of suffix trees to identify the critical substrings, integer-linear programming (ilp) to express the minimization problem, and a simple idea that dramatically reduces the size of the ilp, allowing it to be solved efficiently by the commercial ilp solver cplex. we report extensive tests of our approach on various collections of virus dna and rna sequences.
scoring two-species local alignments to try to statistically separate neutrally evolving from selected dna segments. we construct several score functions for use in locating unusually conserved regions in a genome-wide search of aligned dna from two species. we test these functions on regions of the human genome aligned to the mouse genome. these score functions are derived from properties of neutrally evolving sites on the mouse and human genome, and can be adjusted to the local background rate of conservation. the aim of these functions is to try to identify regions of the human genome that are conserved by evolutionary selection, because they have an important function, rather than by chance. we use them to get a very rough estimate of the amount of dna in the human genome that is under selection.
biological and computational annotation of the drosophila genome sequence. the nucleotide sequence of the drosophila melanogaster genome is now available and efforts are ongoing to improve its accuracy and annotation. the value of these sequence data will be enormously enhanced if we can provide for each gene information on: (1) the structure and expression pattern of its transcripts; (2) the mechanisms and logic used to control their expression; and (3) the functions of their protein products. my presentation will be directed toward the challenges of obtaining and interpreting such information for the fruit fly. gene sequence and expression pattern databases will be extremely powerful tools. however, the function of a protein in a multicellular organism depends on context and will almost certainly need to be determined by experimental analysis. collection of the required large datasets will be difficult and neither the intellectual framework nor experimental tools for analyzing complex gene networks are currently in place. nevertheless, there is reason for cautious optimism that the complete genomic sequence of organisms will enable the necessary global approaches to study gene function and regulation. the conservation of gene structure and function during evolution will allow for the linking and sharing of information garnered in different experimental systems. but what data should be collected and how to interpret these data are much less clear. i will describe recent attempts by the berkeley drosophila genome project to address some of these issues.
early eukaryote evolution based on mitochondrial gene order breakpoints. we present a general heuristic for the median problem for induced breakpoints on genomes with unequal gene content and incorporate this into a routine for estimating optimal gene orders for the ancestral genomes in a fixed phylogeny. the routine is applied to a phylogenetic study of an up-to-date set of completely sequenced protist mitochondrial genomes, confirming some of the recent sequence-based groupings which have been proposed and, conversely, confirming the usefulness of the breakpoint method as a phylogenetic tool even for small genomes.
chromosomal breakpoint re-use in the inference of genome sequence rearrangement. in order to apply gene-order rearrangement algorithms to the comparison of genome sequences, pevzner and tesler [9] bypass gene finding and ortholog identification, and use the order of homologous blocks of unannotated sequence as input. the method excludes blocks shorter than a threshold length and ignores small block-internal rearrangements. here we investigate possible biases introduced by eliminating and amalgamating short blocks, focusing on the notion of "breakpoint re-use" introduced by these authors. analytic and simulation methods show that re-use is very sensitive to threshold size and to parameters of the rearrangement process. as is pertinent to the comparison of mammalian genomes, large thresholds in the context of high rates of small rearrangements risk randomizing the comparison completely. we suggest a number of mathematical, algorithmic and statistical lines for further developing the pevzner-tesler approach.
towards predicting coiled-coil protein interactions. protein-protein interactions play a central role in many cellular functions, and as whole-genome data accumulates, computational methods for predicting these interactions become increasingly important. computational methods have already proven to be a useful first step for rapid genome-wide identification of putative protein structure and function, but research on the problem of computationally determining biologically relevant partners for given protein sequences is just beginning. in this paper, we approach the problem of predicting protein-protein interactions by focusing on the 2- stranded coiled-coil motif. we introduce a computational method for predicting coiled-coil protein interactions, and give a novel framework that is able to use both genomic sequence data and experimental data in making these predictions. cross-validation tests show that the method is able to predict many aspects of protein-protein interactions mediated by the coiled-coil motif, and suggest that this methodology can be used as the basis for genome-wide prediction of coiled-coil protein interactions.
discriminative motifs. this paper takes a new view of motif discovery, addressing a common problem in existing motif finders. a motif is treated as a feature of the input promoter regions that leads to a good classifier between these promoters and a set of background promoters. this perspective allows us to adapt existing methods of feature selection, a well studied topic in machine learning, to motif discovery. we develop a general algorithmic framework that can be specialized to work with a wide variety of motif models, including consensus models with degenerate symbols or mismatches, and composite motifs. a key feature of our algorithm is that it measures over-representation while maintaining information about the distribution of motif instances in individual promoters. the assessment of a motif's discriminative power is normalized against chance behaviour by a probabilistic analysis. we apply our framework to two popular motif models, and are able to detect several known binding sites in sets of co-regulated genes in yeast.
approximation of protein structure for fast similarity measures. it is shown that structural similarity between proteins can be decided well with much less information than what is used in common similarity measures. the full cα representation contains redundant information because of the inherent chain topology of proteins and a limit on their compactness due to excluded volume. a wavelet analysis on random chains and proteins justifies approximating subchains by their centers of mass. for not too compact chain-like structures in general, and proteins in particular, similarity measures that use this approximation are highly correlated to the exact similarity measures and are therefore useful, e.g., as fast filters. experimental results with such simplified similarity measures in two applications, nearest neighbor search and automatic structural classification show a significant speed up.
class prediction and discovery using gene expression data. classification of patient samples is a crucial aspect of cancer diagnosis and treatment. we present a method for classifying samples by computational analysis of gene expression data. we consider the classification problem in two parts: class discovery and class prediction. class discovery refers to the process of dividing samples into reproducible classes that have similar behavior or properties, while class prediction places new samples into already known classes. we describe a method for performing class prediction and illustrate its strength by correctly classifying bone marrow and blood samples from acute leukemia patients. we also describe how to use our predictor to validate newly discovered classes, and we demonstrate how this technique could have discovered the key distinctions among leukemias if they were not already known. this proof-of-concept experiment paves the way for a wealth of future work on the molecular classification and understanding of disease.
from promoter sequence to expression: a probabilistic framework. we present a probabilistic framework that models the process by which transcriptional binding explains the mrna expression of different genes. our joint probabilistic model unifies the two key components of this process: the prediction of gene regulation events from sequence motifs in the gene's promoter region, and the prediction of mrna expression from combinations of gene regulation events in different settings. our approach has several advantages. by learning promoter sequence motifs that are directly predictive of expression data, it can improve the identification of binding site patterns. it is also able to identify combinatorial regulation via interactions of different transcription factors. finally, the general framework allows us to integrate additional data sources, including data from the recent binding localization assays. we demonstrate our approach on the cell cycle data of spellman et al., combined with the binding localization information of simon et al. we show that the learned model predicts expression from sequence, and that it identifies coherent co-regulated groups with significant transcription factor motifs. it also provides valuable biological insight into the domain via these co-regulated "modules" and the combinatorial regulation effects that govern their behavior.
probabilistic hierarchical clustering for biological data. biological data, such as gene expression profiles or protein sequences, is often organized in a hierarchy of classes, where the instances assigned to "nearby" classes in the tree are similar. most approaches for constructing a hierarchy use simple local operations, that are very sensitive to noise or variation in the data. in this paper, we describe probabilistic abstraction hierarchies (pah) [11], a general probabilistic framework for clustering data into a hierarchy, and show how it can be applied to a wide variety of biological data sets. in a pah, each class is associated with a probabilistic generative model for the data in the class. the pah clustering algorithm simultaneously optimizes three things: the assignment of data instances to clusters, the models associated with the clusters, and the structure of the pah approach is that it utilizes global optimization algorithms for the last two steps, substantially reducing the sensitivity to noise and the propensity to local maxima. we show how to apply this framework to gene expression data, protein sequence data, and hiv protease sequence data. we also show how our framework supports hierarchies involving more than one type of data. we demonstrate that our method extracts useful biological knowledge and is substantially more robust than hierarchical agglomerative clustering.
a discriminative model for identifying spatial cis-regulatory modules. transcriptional regulation is mediated by the coordinated binding of transcription factors to the upstream region of genes. in higher eukaryotes, the binding sites of cooperating transcription factors are organized into short sequence units, called cis-regulatory modules. in this paper we propose a method for identifying modules of transcription factor binding sites in a set of co-regulated genes, using only the raw sequence data as input. our method is based on a novel probabilistic model that describes the mechanism of cis-regulation, including the binding sites of cooperating transcription factors, the organization of these binding sites into short sequence modules, and the regulation of a gene by its modules. we show that our method is successful in discovering planted modules in simulated data and known modules in yeast. more importantly, we applied our method to a large collection of human gene sets, and found 83 significant cis-regulatory modules, which included 36 known motifs and many novel ones. thus, our results provide one of the first comprehensive compendiums of putative cis-regulatory modules in human.
using motion planning to study protein folding pathways. we present a framework for studying protein folding pathways and potential landscapes which is based on techniques recently developed in the robotics motion planning community. in particular, our work uses probabilistic roadmap (prm) motion planning techniques which have proven to be very successful for problems involving high-dimensional configuration spaces. our results applying prm techniques to several small proteins (60 residues) are very encouraging. the framework enables one to easily and efficiently compute folding pathways from any denatured starting state to the native fold. this aspect makes our approach ideal for studying global properties of the protein's potential landscape. for example, our results show that folding pathways from different starting denatured states sometimes share some common `gullies', mainly when they are close to the native fold. such global issues are difficult to simulate and study with other methods. our focus in this work is to study the protein folding mechanism assuming we know the native fold. therefore, instead of performing fold prediction, we aim to study issues related to the folding process, such as the formation of secondary and tertiary structure, and the dependence on the initial conformation. our results indicate that for some proteins, secondary structure clearly forms first while for others the tertiary structure is obtained more directly, and moreover, these situations seem to be differentiated in the distributions of the conformations sampled by our technique. we also find that the formation order is independent of the starting denatured conformation. we validate our results by comparing the secondary structure formation order on our paths to known pulse-labeling experimental results. this indicates the promise of our approach for studying proteins for which experimental results are not available.