PubMed Health⌕ Search

Biomedical subjects

Ron Shamir

Publications and source records attributed to Ron Shamir.

At least 37 records · Page 2Linked to original sources
PubMed2005

The incomplete perfect phylogeny haplotype problem.

The problem of resolving genotypes into haplotypes, under the perfect phylogeny model, has been under intensive study recently. All studies so far handled missing data entries in a heuristic manner. We prove that the perfect phylogeny haplotype problem is NP-complete when some of the data entries are missing, even when the phylogeny is rooted. We define a biologically motivated probabilistic model for genotype generation and for the way missing data occur. Under this model, we provide an algorithm, which takes an expected polynomial time. In tests on simulated data, our algorithm quickly resolves the genotypes under high rates of missing entries.

Algorithms↗
PubMed2004

GERBIL: Genotype resolution and block identification using likelihood.

The abundance of genotype data generated by individual and international efforts carries the promise of revolutionizing disease studies and the association of phenotypes with individual polymorphisms. A key challenge is providing an accurate resolution (phasing) of the genotypes into haplotypes. We present here results on a method for genotype phasing in the presence of recombination. Our analysis is based on a stochastic model for recombination-poor regions ("blocks"), in which haplotypes are generated from a small number of core haplotypes, allowing for mutations, rare recombinations, and errors. We formulate genotype resolution and block partitioning as a maximum-likelihood problem and solve it by an expectation-maximization algorithm. The algorithm was implemented in a software package called GERBIL (genotype resolution and block identification using likelihood), which is efficient and simple to use. We tested GERBIL on four large-scale sets of genotypes. It outperformed two state-of-the-art phasing algorithms. The phase algorithm was slightly more accurate than GERBIL when allowed to run with default parameters, but required two orders of magnitude more time. When using comparable running times, GERBIL was consistently more accurate. For data sets with hundreds of genotypes, the time required by phase becomes prohibitive. We conclude that GERBIL has a clear advantage for studies that include many hundreds of genotypes and, in particular, for large-scale disease studies.

Chromosome Mapping↗
PubMed2004

Accurate identification of alternatively spliced exons using support vector machine.

MOTIVATION: Alternative splicing is a major component of the regulatory action on mammalian transcriptomes. It is estimated that over half of all human genes have more than one splice variant. Previous studies have shown that alternatively spliced exons possess several features that distinguish them from constitutively spliced ones. Recently, we have demonstrated that such features can be used to distinguish alternative from constitutive exons. In the current study, we used advanced machine learning methods to generate robust classifier of alternative exons. RESULTS: We extracted several hundred local sequence features of constitutive as well as alternative exons. Using feature selection methods we find seven attributes that are dominant for the task of classification. Several less informative features help to slightly increase the performance of the classifier. The classifier achieves a true positive rate of 50% for a false positive rate of 0.5%. This result enables one to reliably identify alternatively spliced exons in exon databases that are believed to be dominated by constitutive exons.

Algorithms↗
PubMed2004

In silico identification of transcriptional regulators associated with c-Myc.

The development of powerful experimental strategies for functional genomics and accompanying computational tools has brought major advances in the delineation of transcriptional networks in organisms ranging from yeast to human. Regulation of transcription of eukaryotic genes is to a large extent combinatorial. Here, we used an in silico approach to identify transcription factors (TFs) that form recurring regulatory modules with c-Myc, a protein encoded by an oncogene that is frequently disregulated in human malignancies. A recent study identified, on a genomic scale, human genes whose promoters are bound by c-Myc and its heterodimer partner Max in Burkitt's lymphoma cells. Using computational methods, we identified nine TFs whose binding-site signatures are highly overrepresented in this promoter set of c-Myc targets, pointing to possible functional links between these TFs and c-Myc. Binding sites of most of these TFs are also enriched on the set of mouse homolog promoters, suggesting functional conservation. Among the enriched TFs, there are several regulators known to control cell cycle progression. Another TF in this set, EGR-1, is rapidly activated by numerous stress challenges and plays a central role in angiogenesis. Experimental investigation confirmed that c-Myc and EGR-1 bind together on several target promoters. The approach applied here is general and demonstrates how computational analysis of functional genomics experiments can identify novel modules in complex networks of transcriptional regulation.

Animals↗
PubMed2004

Revealing modularity and organization in the yeast molecular network by integrated analysis of highly heterogeneous genomewide data.

The dissection of complex biological systems is a challenging task, made difficult by the size of the underlying molecular network and the heterogeneous nature of the control mechanisms involved. Novel high-throughput techniques are generating massive data sets on various aspects of such systems. Here, we perform analysis of a highly diverse collection of genomewide data sets, including gene expression, protein interactions, growth phenotype data, and transcription factor binding, to reveal the modular organization of the yeast system. By integrating experimental data of heterogeneous sources and types, we are able to perform analysis on a much broader scope than previous studies. At the core of our methodology is the ability to identify modules, namely, groups of genes with statistically significant correlated behavior across diverse data sources. Numerous biological processes are revealed through these modules, which also obey global hierarchical organization. We use the identified modules to study the yeast transcriptional network and predict the function of >800 uncharacterized genes. Our analysis framework, SAMBA (Statistical-Algorithmic Method for Bicluster Analysis), enables the processing of current and future sources of biological information and is readily extendable to experimental techniques and higher organisms.

Amino Acids↗
PubMed2004

PIVOT: protein interacions visualizatiOn tool.

Protein Interaction VisualizatiOn Tool (PIVOT) is a visualization tool for protein-protein interactions. It allows the user to create personal data sets of interactions by combining information from private and public data sources. The user can gradually access the interactions' data using a clear interactive map that is focused on the researcher's protein of interest, and is reshaped and expanded in response to his/her queries. It also offers several visual enhancements and intelligent queries that help the user efficiently study it. PIVOT allows the user to search the interactions data set for paths connecting proteins that are expected to co-operate. The user can also employ PIVOT to predict unknown interactions among proteins, based on interactions among their homologous proteins in other species.

Database Management Systems↗
PubMed2004

How prevalent is functional alternative splicing in the human genome?

Comparative analyses of ESTs and cDNAs with genomic DNA predict a high frequency of alternative splicing in human genes. However, there is an ongoing debate as to how many of these predicted splice variants are functional and how many are the result of aberrant splicing (or 'noise'). To address this question, we compared alternatively spliced cassette exons that are conserved between human and mouse with EST-predicted cassette exons that are not conserved in the mouse genome. Presumably, conserved exon-skipping events represent functional alternative splicing. We show that conserved (functional) cassette exons possess unique characteristics in size, repeat content and in their influence on the protein. By contrast, most non-conserved cassette exons do not share these characteristics. We conclude that a significant portion of cassette exons evident in EST databases is not functional, and might result from aberrant rather than regulated splicing.

Alternative Splicing↗
PubMed2004

The canine olfactory subgenome.

We identified 971 olfactory receptor (OR) genes in the dog genome, estimated to constitute approximately 80% of the canine OR repertoire. This was achieved by directed genomic DNA cloning of olfactory sequence tags as well as by mining the Celera canine genome sequences. The dog OR subgenome is estimated to have 12% pseudogenes, suggesting a functional repertoire similar to that of mouse and considerably larger than for humans. No novel OR families were discovered, but as many as 34 gene subfamilies were unique to the dog. "Fish-like" Class I ancient ORs constituted 18% of the repertoire, significantly more than in human and mouse. A set of 122 dog-human-mouse ortholog triplets was identified, with a relatively high fraction of Class I ORs. The elucidation of a large portion of the canine olfactory receptor gene superfamily, with some dog-specific attributes, may help us understand the unique chemosensory capacities of this species.

Animals↗
PubMed2004

Multilevel modeling and inference of transcription regulation.

The understanding of transcription regulation is a major goal of today's biology. The challenge is to utilize diverse high-throughput data in order to infer mechanistic models of transcription control. We propose a new model which integrates transcription factor-gene affinity, protein abundance, and gene expression profiles. The model provides a detailed, yet computationally tractable description of the relations between transcription factors, their binding sites at gene promoters, and the combinatorial regulation of transcription. At the core, our model manipulates dose-affinity-response functions that associate transcription factor concentrations and transcription factor-DNA affinities to determine the rate of transcription factor-DNA reactions. We study computational problems that arise in optimizing such models and develop polynomial algorithms for certain problems. We show how to assess missing values (notably protein abundance) and describe a novel framework to infer models from currently available data. On budding yeast carbohydrate metabolism data, our results demonstrate the sensitivity and specificity of the approach. They also suggest new active binding sites and a regulation model for the transcription program of the galactose system.

Algorithms↗
PubMed2004

Modeling and analysis of heterogeneous regulation in biological networks.

In this study, we propose a novel model for the representation of biological networks and provide algorithms for learning model parameters from experimental data. Our approach is to build an initial model based on extant biological knowledge and refine it to increase the consistency between model predictions and experimental data. Our model encompasses networks which contain heterogeneous biological entities (mRNA, proteins, metabolites) and aims to capture diverse regulatory circuitry on several levels (metabolism, transcription, translation, post-translation and feedback loops, among them). Algorithmically, the study raises two basic questions: how to use the model for predictions and inference of hidden variables states, and how to extend and rectify model components. We show that these problems are hard in the biologically relevant case where the network contains cycles. We provide a prediction methodology in the presence of cycles and a polynomial time, constant factor approximation for learning the regulation of a single entity. A key feature of our approach is the ability to utilize both high-throughput experimental data, which measure many model entities in a single experiment, as well as specific experimental measurements of few entities or even a single one. In particular, we use together gene expression, growth phenotypes, and proteomics data. We tested our strategy on the lysine biosynthesis pathway in yeast. We constructed a model of more than 150 variables based on an extensive literature survey and evaluated it with diverse experimental data. We used our learning algorithms to propose novel regulatory hypotheses in several cases where the literature-based model was inconsistent with the experiments. We showed that our approach has better accuracy than extant methods of learning regulation.

Algorithms↗
PubMed2004

A global view of the selection forces in the evolution of yeast cis-regulation.

The interaction between transcription factors and their DNA binding sites is key to understanding gene regulation. By performing a genome-wide study of the evolutionary dynamics in yeast promoters, we provide a first global view of the network of selection forces in the evolution of transcription factor binding sites. This analysis gives rise to new models for binding site activity, identifies families of related binding sites, and characterizes the functional similarities among them. We discovered rich and highly optimized selective pressures operating inside and around these families. In several cases, this organization reveals that a single transcription factor has multiple functional modes. We demonstrate how such functional heterogeneity is related to the binding site's affinity and how it is exploited in transcription programs.

Binding Sites↗
PubMed2004

A non-EST-based method for exon-skipping prediction.

It is estimated that between 35% and 74% of all human genes can undergo alternative splicing. Currently, the most efficient methods for large-scale detection of alternative splicing use expressed sequence tags (ESTs) or microarray analysis. As these methods merely sample the transcriptome, splice variants that do not appear in deeply sampled tissues have a low probability of being detected. We present a new method by which we can predict that an internal exon is skipped (namely whether it is a cassette-exon) merely based on its naked genomic sequence and on the sequence of its mouse ortholog. No other data, such as ESTs, are required for the prediction. Using our method, which was experimentally validated, we detected hundreds of novel splice variants that were not detectable using ESTs. We show that a substantial fraction of the splice variants in the human genome could not be identified through current human EST or cDNA data.

Alternative Splicing↗
PubMed2003

Detecting excess radical replacements in phylogenetic trees.

There are a few instances in which positive Darwinian selection has been convincingly demonstrated at the molecular level. In this study, we present a novel test for detecting excess of radical amino-acid replacements. Such excess is usually indicative of positive Darwinian selection, but may also be due to relaxed functional constraints or model misspecification. In our test, each amino-acid replacement is characterized in terms of a physicochemical distance, i.e., the degree of dissimilarity between the exchanged amino-acid residues. By using phylogenetic trees based on protein sequences, our test identifies statistically significant deviations of the mean physicochemical distance from the random expectation, either along a taxonomic lineage or across a subtree. The mean inferred distance is calculated as the average physicochemical distance over all possible ancestral sequence reconstructions weighted by their likelihood. Our method substantially improves over previous approaches by taking into account the stochastic process, tree phylogeny, among-site rate variation, and alternative ancestral reconstructions. We provide a fast linear time algorithm for applying this test to all branches and all subtrees of a given phylogenetic tree. We validate this approach by applying it to two well-studied datasets: the MHC class I glycoproteins serving as a positive control, and the house-keeping gene carbonic anhydrase I serving as a negative control.

Algorithms↗
PubMed2003

Advanced computational techniques for re-sequencing DNA with polymerase signaling assay arrays.

Re-sequencing, the identification of the specific variants in a sequence of interest compared with a known genomic sequence, is a ubiquitous task in today's biology. Universal arrays, which interrogate all possible oligonucleotides of a certain length in a target sequence, have been suggested for computationally determining a polynucleotide sequence from its oligonucleotide content. We present here new methods that use such arrays for re-sequencing. Our methods are applied to data obtained by the polymerase signaling assay, which arrays single-based primer extension reactions for either universal or partial arrays of pentanucleotides. The computational analysis uses the spectrum alignment algorithm, which is refined and enhanced here in order to overcome noise incurred by the use of such short primers. We present accurate re-sequencing results for both synthetic and amplified DNA molecules.

Algorithms↗
PubMed2003

CLICK and EXPANDER: a system for clustering and visualizing gene expression data.

MOTIVATION: Microarrays have become a central tool in biological research. Their applications range from functional annotation to tissue classification and genetic network inference. A key step in the analysis of gene expression data is the identification of groups of genes that manifest similar expression patterns. This translates to the algorithmic problem of clustering genes based on their expression patterns. RESULTS: We present a novel clustering algorithm, called CLICK, and its applications to gene expression analysis. The algorithm utilizes graph-theoretic and statistical techniques to identify tight groups (kernels) of highly similar elements, which are likely to belong to the same true cluster. Several heuristic procedures are then used to expand the kernels into the full clusters. We report on the application of CLICK to a variety of gene expression data sets. In all those applications it outperformed extant algorithms according to several common figures of merit. We also point out that CLICK can be successfully used for the identification of common regulatory motifs in the upstream regions of co-regulated genes. Furthermore, we demonstrate how CLICK can be used to accurately classify tissue samples into disease types, based on their expression profiles. Finally, we present a new java-based graphical tool, called EXPANDER, for gene expression analysis and visualization, which incorporates CLICK and several other popular clustering algorithms. AVAILABILITY: http://www.cs.tau.ac.il/~rshamir/expander/expander.html

Algorithms↗
PubMed2003

The restriction scaffold problem.

Most shotgun sequencing projects undergo a long and costly phase of finishing, in which a partial assembly forms several contigs whose order, orientation, and relative distance is unknown. We propose here a new technique that supplements the shotgun assembly data by experimentally simple and commonly used complete restriction digests of the target. By computationally combining information from the contig sequences and the fragment sizes measured for several different enzymes, we seek to form a "scaffold" on which the contigs will be placed in their correct orientation, order, and distance. We give a heuristic search algorithm for solving the problem and report on promising preliminary simulation results. The key to the success of the search scheme is the very rapid solution of two time-critical subproblems that are solved to optimality in linear time. Our simulations indicate that with noise levels of some 3% relative error in measuring fragment sizes, using six enzymes, most datasets of 13 contigs spanning 300kb can be correctly ordered, and the remaining ones have most of their pairs of neighboring contigs correct. Hence, the technique has a potential to provide real help to finishing. Even without closing all gaps, the ability to order and orient the contigs correctly makes the partial assembly both more accessible and more useful for biologists.

Computational Biology↗
PubMed2003

Handling long targets and errors in sequencing by hybridization.

Sequencing by hybridization (SBH) is a DNA sequencing technique, in which the sequence is reconstructed using its k-mer content. This content, which is called the spectrum of the sequence, is obtained by hybridization to a universal DNA array. Standard universal arrays contain all k-mers for some fixed k, typically 8 to 10. Currently, in spite of its promise and elegance, SBH is not competitive with standard gel-based sequencing methods. This is due to two main reasons: lack of tools to handle realistic levels of hybridization errors and an inherent limitation on the length of uniquely reconstructible sequence by standard universal arrays. In this paper, we deal with both problems. We introduce a simple polynomial reconstruction algorithm which can be applied to spectra from standard arrays and has provable performance in the presence of both false negative and false positive errors. We also propose a novel design of chips containing universal bases that differs from the one proposed by Preparata et al. (1999). We give a simple algorithm that uses spectra from such chips to reconstruct with high probability random sequences of length lower only by a squared log factor compared to the information theoretic bound. Our algorithm is very robust to errors and has a provable performance even if there are both false negative and false positive errors. Simulations indicate that its sensitivity to errors is also very small in practice.

Computational Biology↗