on IDEAL Article DEFOG: A Practical Scheme for Deciphering Families of Genes (2009)
Tania Fuchs, Barbora Malecova, Chaim Linhart, Roded Sharan, Miriam Khen, Dmitry Shmulevich, ...
*These authors contributed equally to this work. To whom correspondence and reprint requests should be addressed. Fax: +972-3-6405384.
Pages 1–9 Discovering Statistically Significant Biclusters in Gene Expression Data (2009)
Amos Tanay, Roded Sharan, Ron Shamir
In gene expression data, a bicluster is a subset of the genes exhibiting consistent patterns over a subset of the conditions. We propose a new method to detect significant biclusters in large...
Large scale sequencing by hybridization (2009)
Sequencing by Hybridization is a method for reconstructing a DNA sequence based on its k-mer content. This content, called the spectrum of the sequence, can be obtained from hybridization with a...
Gad Kimmel, Michael I. Jordan, Eran Halperin, Ron Shamir, Richard M. Karp
Population stratification can be a serious obstacle in the analysis of genomewide association studies. We propose a method for evaluating the significance of association scores in whole-genome...
Torque: topology-free querying of protein interaction networks (2009)
Bruckner, Sharon, Hüffner, Falk, Karp, Richard M., Shamir, Ron, Sharan, Roded
Torque is a tool for cross-species querying of protein–protein interaction networks. It aims to answer the following question: given a set of proteins constituting a known complex or a pathway in...
Allegro: Analyzing expression and sequence in concert to discover regulatory programs (2009)
Halperin, Yonit, Linhart, Chaim, Ulitsky, Igor, Shamir, Ron
A major goal of system biology is the characterization of transcription factors and microRNAs (miRNAs) and the transcriptional programs they regulate. We present Allegro, a method for de-novo...
Motivation: Microarray-based gene expression studies have great potential but are frequently difficult to interpret due to their overwhelming dimensions. Recent studies have shown that the analysis...
Because of rapid progress in genotyping techniques, many large-scale, genomewide disease-association studies are now under way. Typically, the disorders examined are multifactorial, and, therefore,...
Human Cells, Ran Elkon, Chaim Linhart, Roded Sharan, Ron Shamir, Yosef Shiloh
Dissection of regulatory networks that control gene transcription is one of the greatest challenges of functional genomics. Using human genomic sequences, models for binding sites of known...
Gad Kimmel, Roded Sharan, Ron Shamir
informs ® doi 10.1287/ijoc.1040.0088 © 2004 INFORMS The study of haplotypes and their diversity in a population is central to disease-association research. We study several problems arising in...
Rotem Sorek, Ron Shamir, Gil Ast
How prevalent is functional alternative splicing in the
Complexity classi cation of some edge modi cation problems � (2008)
Assaf Natanzon, Ron Shamir, Roded Sharan
In an edge modi cation problem one has to change the edge set of a given graph as little as possible so as to satisfy a certain property. We prove the NP-hardness of a variety of edge modi cation...
Gad Kimmel, Roded Sharan, Ron Shamir
The study of haplotypes and their diversity in a population is central to disease association research. We study several problems arising in haplotype block partitioning. Our objective function is...
REVIEW Network-based prediction of protein function (2008)
Roded Sharan, Igor Ulitsky, Ron Shamir
Functional annotation of proteins is a fundamental problem in the post-genomic era. The recent availability of protein interaction networks for many model species has spurred on the development of...
Michal Ozery-flato, Ron Shamir
Abstract. We prove that sorting by reciprocal translocations can be done in O(n 3/2p log(n)) for an n-gene genome. Our algorithm is an adaptation of the Tannier et. al algorithm for sorting by...
Sorting by translocations via reversals theory (2008)
Michal Ozery-flato, Ron Shamir
Abstract. The understanding of genome rearrangements is an important endeavor in comparative genomics. A major computational problem in this field is finding a shortest sequence of genome...
188 No. 93 Pe’er et al. Incomplete Directed Perfect Phylogeny (2008)
Perfect phylogeny is one of the fundamental models for studying evolution. We investigate the following variant of the problem: The input is an n × m species-characters matrix. The characters are...
Accepted (Day Month Year) (2008)
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....
Chapter 1 Degenerate Primer Design: Theoretical Analysis and the HYDEN program 1 (2008)
A PCR primer sequence is called degenerate if some of its positions have several possible bases. The degeneracy of the primer is the number of unique sequence combinations it contains. We study the...
SPIKE – a database, visualization and analysis tool of cellular signaling pathways (2008)
Elkon, Ran, Vesterman, Rita, Amit, Nira, Ulitsky, Igor, Zohar, Idan, Weisz, Mali, ...
Abstract Background Biological signaling pathways that govern cellular physiology form an intricate web of tightly regulated interlocking processes. Data on these regulatory networks are accumulating...
Improved Algorithms for the Random Cluster (2008)
Graph Model, Ron Shamir, Dekel Tsur
Abstract We model noisy clustering data using random graphs: Clusters correspond to disjoint sets of vertices. Two vertices from the same set (resp., different sets) share an edge with probability p...
A randomization test for controlling population stratification in (2008)
Gad Kimmel, Michael I. Jordan, Eran Halperin, Ron Shamir, Richard M
whole-genome association studies
Ulitsky, Igor, Gat-Viks, Irit, Shamir, Ron
Abstract MetaReg http://acgt.cs.tau.ac.il/metareg/application.html is a computational tool that models cellular networks and integrates experimental results with such models. MetaReg represents...
Daniela Raijman, Ron Shamir, Amos Tanay
In comparative genomics one analyzes jointly evolutionarily related species in order to identify conserved and diverged sequences and to infer their function. While such studies enabled the detection...
Regulatory networks define phenotypic classes of human stem cell lines (2008)
Müller, Franz-Josef, Laurent, Louise C., Kostka, Dennis, Ulitsky, Igor, Williams, Roy, Lu, Christina, ...
Stem cells are defined as self-renewing cell populations that can differentiate into multiple distinct cell types. However, hundreds of different human cell lines from embryonic, fetal and adult...
Ulitsky, Igor, Gat-Viks, Irit, Shamir, Ron
MetaReg http://acgt.cs.tau.ac.il/metareg/application.html webcite is a computational tool that models cellular networks and integrates experimental results with such models. MetaReg represents...
Genome Biology 2008, 9:R1 doi:10.1186/gb-2008-9-1-r1 (2008)
Igor Ulitsky, Igor Ulitsky, Irit Gat-viks, Ron Shamir
This Provisional PDF corresponds to the article as it appeared upon acceptance. Copyedited and fully formatted PDF and full text (HTML) versions will be made available soon. MetaReg: A platform for...
Linhart, Chaim, Halperin, Yonit, Shamir, Ron
We present a threefold contribution to the computational task of motif discovery, a key component in the effort of delineating the regulatory map of a genome: (1) We constructed a comprehensive...
An Algorithm Combining Discrete and Continuous Methods for Optical Mapping (2007)
Richard Karp Itsik, Richard M. Karp, Ron Shamir
Optical mapping is a novel technique for generating the restriction map of a DNA molecule by observing many single, partially digested copies of it, using uorescence microscopy. The real-life problem...
An Algorithm Combining Discrete and Continuous Methods for Optical Mapping (2007)
Richard M. Karp, Itsik Pe'er, Ron Shamir
Optical mapping is a novel technique for generating the restriction map of a DNA molecule by observing many single, partially digested copies of it, using uorescence microscopy. The real-life problem...
Perfect Completion and Deletion in Random Graphs (2007)
In the Perfect Completion problem one wishes to add the fewest possible edges to a graph in order to obtain a perfect graph. How large can the size of the added edge set be compared to the size of...
Roded Sharan, Trey Ideker, Brian Kelley, Ron Shamir, Richard M. Karp
Mounting evidence shows that many protein complexes are conserved in evolution. Here we use conservation to nd complexes that are common to the yeast S. cerevisiae and the bacteria H. pylori. Our...
Accepted (Day Month Year) (2007)
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....
Population Stratication Gad Kimmel (2007)
Analysis Block Scores, Block Identi Cation, Roded Sharan, Ron Shamir
The study of haplotypes and their diversity in a population is central to disease association research. We study several problems arising in haplotype block partitioning. Our objective function is...
Haim Kaplan, Ron Shamir, E. Tarjan
Abstract. We study the parameterizedcomplexity of three NP-hard graph completionproblems. The MINIMUM FILL-IN problem is to decide if a graph can be triangulated by adding at most k edges. We develop...
and Bar-Ilan University (2007)
Martin Charles Golumbic, Haim Kaplan, Ron Shamir
The Physical Mapping Problem is to reconstruct the relative position of fragments (clones) of DNA along the genome from information on their pairwise overlaps. We show that two simplified versions of...
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O((k
Martin Charles Golumbic, Haim Kaplan, Ron Shamir, Ron Shamir
The graph sandwich problem for property \Pi is defined as follows: Given two graphs G 1
Haim Kaplan, Ron Shamir, E. Tarjan
Abstract. We give a quadratic-time algorithm for nding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and...
The restriction scaffold problem (2007)
Amir Ben-dor, Richard M. Karp, Benno Schwikowski, Ron Shamir
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...
Ran Elkon, Chaim Linhart, Roded Sharan, Ron Shamir, Yosef Shiloh
# These authors contributed equally to this work. Correspondence should be addressed to Y.S.
Abstract. A graph G = (V; E) is a tolerance graph if there is a set I = fIv j v 2 V g of closed real intervals and a set = fv j v 2 V g of positive real numbers such that (x; y) 2 E, jIx \ Iy j...
Positive selection 1 A test for positive Darwinian selection (2007)
Tal Pupko, Roded Sharan, Ron Shamir, Dan Graur
The neutral theory of molecular evolution maintains that most sequence variation among genomes has no direct relevance to adaptation [1]. The rapidly-growing amount of genomic data makes it possible...
Pages S172--S180 The degenerate primer design problem (2007)
A PCR primer sequence is called degenerate if some of its positions have several possible bases. The degeneracy of the primer is the number of unique sequence combinations it contains. We study the...
Pavol Hell, Ron Shamir, Roded Sharan
In this paper we study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a...
How Prevalent is Functional Alternative Splicing in the (2007)
Human Genome Rotem, Rotem Sorek, Ron Shamir, Gil Ast
this article can be found at doi: 10.1016/j.tig.2003.12.004 Corresponding author: Gil Ast (gilast@post.tau.ac.il)
Computational Problems in Perfect Phylogeny Haplotyping: Xor-Genotypes and Tag SNPs (2007)
Tag Snps, Tamar Barzuza, Jacques S. Beckmann, Itsik Pe'er, Ron Shamir
The perfect phylogeny model for haplotype evolution has been successfully applied to haplotype resolution from genotype data. In this study we explore the application of the perfect phylogeny model...
Multi-level Modeling and Inference of Transcription Regulation (2007)
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...
Tal Pupko, Ron Shamir, Roded Sharan
Perfect phylogeny is one of the fundamental models for studying evolution. We investigate the following variant of the model: The input is a species-characters matrix. The characters are binary and...
BIOINFORMATICS APPLICATIONS NOTE PIVOT: Protein Interactions VisualizatiOn Tool (2007)
Nir Orlev, Ron Shamir, Yosef Shiloh
Summary: PIVOT is a visualization tool for proteinprotein interactions. It allows the user to create personal datasets of interactions by combining information from private and public data sources....
Functional genomic delineation of TLR-induced transcriptional networks (2007)
Elkon, Ran, Linhart, Chaim, Halperin, Yonit, Shiloh, Yosef, Shamir, Ron
Abstract Background The innate immune system is the first line of defense mechanisms protecting the host from invading pathogens such as bacteria and viruses. The innate immunity responses are...
GEVALT: An integrated software tool for genotype analysis (2007)
Davidovich, Ofir, Kimmel, Gad, Shamir, Ron
Abstract Background Genotype information generated by individual and international efforts carries the promise of revolutionizing disease studies and the association of phenotypes with alleles and...
Identification of functional modules using network topology and high-throughput data (2007)
Abstract Background With the advent of systems biology, biological knowledge is often represented today by networks. These include regulatory and metabolic networks, protein-protein interaction...
Identification of functional modules using network topology and
Refinement and expansion of signaling pathways: The osmotic response network in yeast (2007)
The analysis of large-scale genome-wide experiments carries the promise of dramatically broadening our understanding on biological networks. The challenge of systematic integration of experimental...
Assessing the number of ancestral alternatively spliced exons in the human genome (2006)
Sorek, Rotem, Dror, Gideon, Shamir, Ron
Abstract Background It is estimated that between 35% and 74% of all human genes undergo alternative splicing. However, as a gene that undergoes alternative splicing can have between one and dozens of...
BMC Genomics BioMed Central (2006)
Rotem Sorek, Gideon Dror, Ron Shamir, Open Access
Research article Assessing the number of ancestral alternatively spliced exons in the human genome
A catalog of stability-associated sequence elements in 3' UTRs of yeast mRNAs (2005)
Shalgi, Reut, Lapidot, Michal, Shamir, Ron, Pilpel, Yitzhak
Abstract Background In recent years, intensive computational efforts have been directed towards the discovery of promoter motifs that correlate with mRNA expression profiles. Nevertheless, it is...
EXPANDER– an integrative program suite for microarray data analysis (2005)
Shamir, Ron, Maron-Katz, Adi, Tanay, Amos, Linhart, Chaim, Steinfeld, Israel, Sharan, Roded, ...
Abstract Background Gene expression microarrays are a prominent experimental tool in functional genomics which has opened the opportunity for gaining global, systems-level understanding of...
Elkon, Ran, Rashi-Elkeles, Sharon, Lerenthal, Yaniv, Linhart, Chaim, Tenne, Tamar, Amariglio, Ninette, ...
Abstract Background Gene-expression microarrays and RNA interferences (RNAi) are among the most prominent techniques in functional genomics. The combination of the two holds promise for systematic,...
The Factor Graph Network Model for Biological Systems (2005)
Irit Gat-viks, Amos Tanay, Daniela Raijman, Ron Shamir
Abstract. We introduce an extended computational framework for studying biological systems. Our approach combines formalization of existing qualitative models that are in wide but informal use today,...
A Block-Free Hidden Markov Model for Genotypes and Its Application to Disease Association (2005)
We present a new stochastic model for genotype generation. The model offers a compromise between rigid block structure and no structure altogether: It reflects a general blocky structure of...
Biclustering Algorithms: A Survey (2005)
Amos Tanay, Roded Sharan, Ron Shamir
Analysis of large scale geonomics data, notably gene expression, has initially focused on clustering methods. Recently, biclustering techniques were proposed for revealing submatrices showing unique...
Bmc Bioinformatics, Amos Tanay, Chaim Linhart, Roded Sharan, Ron Shamir, Adi Maron-katz, ...
This Provisional PDF corresponds to the article as it appeared upon acceptance. The fully-formatted PDF version will become available shortly after the date of publication, from the URL listed below....
Tag SNP selection in genotype data for maximizing SNP prediction accuracy (2005)
Halperin, Eran, Kimmel, Gad, Shamir, Ron
Motivation: The search for genetic regions associated with complex diseases, such as cancer or Alzheimer's disease, is an important challenge that may lead to better diagnosis and treatment. The...
Roded Sharan, Trey Ideker, Brian Kelley, Ron Shamir, Richard M. Karp
Mounting evidence shows that many protein complexes are conserved in evolution. Here we use conservation to find complexes that are common to yeast S. Cerevisiae and bacteria H. pylori. Our analysis...
Reconstructing chain functions in genetic networks (2004)
Irit Gat-viks, Richard M. Karp, Ron Shamir, Roded Sharan
Abstract. The following problems arise in the analysis of biological networks: We have a boolean function of n variables, each of which has some default value. An experiment fixes the values of any...
£Corresponding author The Degenerate Primer Design Problem: Theory and Applications (2004)
1 A PCR primer sequence is called degenerate if some of its positions have several possible bases. The degeneracy of the primer is the number of unique sequence combinations it contains. We study the...
Ran Elkon, Karen I. Zeller, Chaim Linhart, Chi V. Dang, Ron Shamir, Yosef Shiloh
silico identification of transcriptional regulators
BIOINFORMATICS ORIGINAL PAPER (2004)
Genome Analysis, Gideon Dror, Rotem Sorek, Ron Shamir
Accurate identification of alternatively spliced exons using support vector machine
A fully dynamic algorithm for modular decomposition and recognition of cographs (2004)
The problem of dynamically recognizing a graph property calls for efficiently deciding if an input graph satisfies the property under repeated modifications to its set of vertices and edges. The...
A Simpler and Faster 1.5-Approximation Algorithm for Sorting by Transpositions (2004)
An important problem in genome rearrangements is sorting permutations by transpositions. Its complexity is still open, and two rather complicated 1.5-approximation algorithms for sorting linear...
Modeling and Analysis of Heterogeneous Regulation in Biological Networks (2004)
Irit Gat-viks, Amos Tanay, Ron Shamir
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...
Cluster Graph Modification Problems (2004)
Ron Shamir, Roded Sharan, Dekel Tsur
In a clustering problem one has to partition a set of elements into homogeneous and well-separated subsets. From a graph theoretic point of view, a cluster graph is a vertex-disjoint union of...
AMBA's analysis results are available for use interactively [4] and the software is also available as part of the EXPANDER software [1]. (3) We explore the evolution of cis-regulatory programs...
The incomplete perfect phylogeny haplotype problem (2004)
Abstract. 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...
c ○ Imperial College Press THE INCOMPLETE PERFECT PHYLOGENY HAPLOTYPE PROBLEM (2004)
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....
A Non-EST-Based Method for Exon-Skipping Prediction (2004)
Sorek, Rotem, Shemesh, Ronen, Cohen, Yuval, Basechess, Ortal, Ast, Gil, Shamir, Ron
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...
PIVOT: protein interactions visualization tool (2004)
Orlev, Nir, Shamir, Ron, Shiloh, Yosef
Summary: PIVOT is a visualization tool for protein-protein interactions. It allows the user to create personal datasets of interactions by combining information from private and public data sources....
Accurate identification of alternatively spliced exons using support vector machine (2004)
Dror, Gideon, Sorek, Rotem, Shamir, Ron
Motivation: Alternative splicing is a major component of the regulation acting on mammalian transcriptomes. It is estimated that over half of all human genes have more than one splice variant....
PIVOT: Protein Interacions VisualizatiOn Tool (2004)
Orlev, Nir, Shamir, Ron, Shiloh, Yosef
Summary: 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...
In silico identification of transcriptional regulators associated with c-Myc (2004)
Elkon, Ran, Zeller, Karen I., Linhart, Chaim, Dang, Chi V., Shamir, Ron, Shiloh, Yosef
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...
PIVOT: protein interactions visualization tool (2004)
Orlev, Nir, Shamir, Ron, Shiloh, Yosef
Summary: PIVOT is a visualization tool for protein-protein interactions. It allows the user to create personal datasets of interactions by combining information from private and public data sources....
Accurate identification of alternatively spliced exons using support vector machine (2004)
Dror, Gideon, Sorek, Rotem, Shamir, Ron
Motivation: Alternative splicing is a major component of the regulation acting on mammalian transcriptomes. It is estimated that over half of all human genes have more than one splice variant....
Computational Molecular Biology (2003)
Istrail, Sorin (ed.), Pevzner, Pavel (ed.), Shamir, Ron (ed.)
0-444-51384-1
Two notes on genome rearrangements (2003)
Michal Ozery-flato, Ron Shamir
Abstract. A central problem in genome rearrangement is nding a most parsimonious rearrangement scenario using certain rearrangement operations. An important problem of this type is sorting a signed...
CLICK and EXPANDER: a system for clustering and visualizing gene expression data (2003)
Roded Sharan, Adi Maron-Katz, Ron Shamir
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 modeling of transcription regulation programs is a major focus of today's biology. The challenge is to utilize diverse high-throughput data (gene expression, promoter binding site...
Handling Long Targets and Errors in Sequencing by Hybridization (2003)
Eran Halperin, Shay Halperin, Tzvika Hartman, Ron Shamir
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...
Designing a Multiroute Synthesis Scheme in Combinatorial Chemistry (2003)
Adi Akavia Hanoch, Hanoch Senderowitz, Alon Lerner, Ron Shamir
This paper is organized as follows: In the Methodology Section, we describe a model of the multiroute synthesis process; present the problem that we study, max string synthesis; and describe a...
Identifying Blocks and Sub-Populations in Noisy SNP Data (2003)
Gad Kimmel Roded, Roded Sharan, Ron Shamir
We study several problems arising in haplotype block partitioning.
A simpler 1.5-approximation algorithm for sorting by transpositions (2003)
An important problem in genome rearrangements is sorting permutations by transpositions. Its complexity is still open, and two rather complicated 1.5-approximation algorithms for sorting linear...
Identifying blocks and sub-populations in noisy SNP data (2003)
Gad Kimmel, Roded Sharan, Ron Shamir
Abstract. We study several problems arising in haplotype block partitioning. Our objective function is the total number of distinct haplotypes in blocks. We show that the problem is NP-hard when...
CLICK and EXPANDER: A System for Clustering and Visualizing Gene (2003)
Expression Data Roded, Roded Sharan, Adi Maron-katz, Ron Shamir
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...
Two notes on genome rearrangements (2003)
Michal Ozery-flato, Ron Shamir
Abstract. A central problem in genome rearrangement is finding a most parsimonious rearrangement scenario using certain rearrangement operations. An important problem of this type is sorting a signed...
Peer, Itsik, Arbili, Naama, Liu, Yi, Enck, Colby, Gelfand, Craig A., Shamir, Ron
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...
CLICK and EXPANDER: a system for clustering and visualizing gene expression data (2003)
Sharan, Roded, Maron-Katz, Adi, Shamir, Ron
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...
Elkon, Ran, Linhart, Chaim, Sharan, Roded, Shamir, Ron, Shiloh, Yosef
Dissection of regulatory networks that control gene transcription is one of the greatest challenges of functional genomics. Using human genomic sequences, models for binding sites of known...
DEFOG: A Practical Scheme for Deciphering Families of Genes (2002)
Fuchs,Tania, Malecova,Barbora, Linhart,Chaim, Sharan,Roded, Khen,Miriam, Herwig,Ralf, ...
We developed a novel efficient scheme, DEFOG (for "deciphering families of genes"), for determining sequences of numerous genes from a family of interest. The scheme provides a powerful means to...
DEFOG: A Practical Scheme for Deciphering Families of Genes (2002)
Fuchs, Tania, Malecova, Barbora, Linhart, Chaim, Sharan, Roded, Khen, Miriam, Herwig, Ralf, ...
We developed a novel efficient scheme, DEFOG (for "deciphering families of genes"), for determining sequences of numerous genes from a family of interest. The scheme provides a powerful means to...
Cluster graph modification problems (2002)
Ron Shamir, Roded Sharan, Dekel Tsur
In a clustering problem one has to partition a set of elements into homogeneous and well-separated subsets. From a graph theoretic point of view, a cluster graph is a vertex-disjoint union of...
Incomplete directed perfect phylogeny (2002)
Tal Pupko, Ron Shamir, Roded Sharan
Abstract. Perfect phylogeny is one of the fundamental models for studying evolution. We investigate the following variant of the model: The input is a species-characters matrix. The characters are...
Large scale sequencing by hybridization (2002)
Sequencing by Hybridization is a method for reconstructing a DNA sequence based on its k-mer content. This content, called the spectrum of the sequence, can be obtained from hybridization with a...
Improved algorithms for the random cluster graph model (2002)
The following probabilistic process models the generation of noisy clustering data: Clusters correspond to disjoint sets of vertices in a graph. Each two vertices from the same set are connected by...
Cluster graph modification problems (2002)
Ron Shamir, Roded Sharan, Dekel Tsur
Abstract. In a clustering problem one has to partition a set of elements into homogeneous and well-separated subsets. From a graph theoretic point of view, a cluster graph is a vertex-disjoint union...
Cluster graph modification problems (2002)
Ron Shamir, Roded Sharan, Dekel Tsur
In a clustering problem one has to partition a set of elements into homogeneous and well-separated subsets. From a graph theoretic point of view, a cluster graph is a vertex-disjoint union of...
Large scale sequencing by hybridization (2002)
Sequencing by Hybridization is a method for reconstructing a DNA sequence based on its k-ruer content. This content, called the spectrum of the sequence, can be obtained from hybridization with a...
Improved algorithms for the random cluster graph model (2002)
We model noisy clustering data using random graphs: Clusters correspond to disjoint sets of vertices. Two vertices from the same set (resp., different sets) share an edge with probability p (resp., r...
Algorithmic approaches to clustering gene expression data (2002)
Technologies for generating high-density arrays of cDNAs and oligonucleotides are developing rapidly, and changing the landscape of biological and biomedical research. They enable, for the rst time,...
Biclustering gene expression data (2002)
Amos Tanay, Roded Sharan, Ron Shamir
In gene expression data, a bicluster is a subset of the genes exhibiting consistent patterns over a subset of the conditions. We propose a new method to detect significant biclusters in large...
A fully dynamic algorithm for recognizing and representing proper interval graphs (2002)
Pavol Hell, Ron Shamir, Roded Sharan
In this paper we study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a...
The Degenerate Primer Design Problem (2002)
Ron Shamir, Beverly Sackler, Prof Ron Shamir
A PCR primer sequence is called degenerate if some of its positions have several possible bases. The degeneracy of the primer is the number of unique sequence combinations it contains. We study the...
Improved Algorithms for the Random Cluster Graph Model (2002)
Ron Shamir Dekel, Ron Shamir, Dekel Tsur
We model noisy clustering data using random graphs: Clusters correspond to disjoint sets of vertices. Two vertices from the same set (resp., di#erent sets) share an edge with probability p (resp., r...
A fully dynamic algorithm for recognizing and representing proper interval graphs (2002)
Pavol Hell, Ron Shamir, Roded Sharan
Abstract In this paper we study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed...
Large scale sequencing by hybridization (2002)
Sequencing by Hybridization is a method for reconstructing a DNA sequence based on its k-mer content. This content, called the spectrum of the sequence, can be obtained from hybridization with a...
Discovering statistically significant biclusters in gene expression data (2002)
Tanay, Amos, Sharan, Roded, Shamir, Ron
In gene expression data, a bicluster is a subset of the genes exhibiting consistent patterns over a subset of the conditions. We propose a new method to detect significant biclusters in large...
The degenerate primer design problem (2002)
A PCR primer sequence is called degenerate if some of its positions have several possible bases. The degeneracy of the primer is the number of unique sequence combinations it contains. We study the...
Improved algorithms for the random cluster graph model (2002)
We model noisy clustering data using random graphs: Clusters correspond to disjoint sets of vertices. Two vertices from the same set (resp., different sets) share an edge with probability p (resp., r...
Cluster graph modification problems (2002)
Ron Shamir, Roded Sharan, Dekel Tsur
In a clustering problem one has to partition a set of elements into homogeneous and well-separated subsets. From a graph theoretic point of view, a cluster graph is a vertex-disjoint union of...
Computational expansion of genetic networks (2001)
We present a new methodology for computational analysis of gene and protein networks. The aim is to generate new educated hypotheses on gene functions and on the logic of the biological network...
Computational expansion of genetic networks (2001)
We present a new methodology for computational analysis of gene and protein networks. The aim is to generate new educated hypotheses on gene functions and on the logic of the biological network...
A clustering algorithm based on graph connectivity (2000)
We have developed a novel algorithm for cluster analysis that is based on graph theoretic techniques. A similarity graph is defined and clusters in that graph correspond to highly connected...
CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis (2000)
Novel DNA microarray technologies enable the monitoring of expression levels of thousands of genes simultaneously. This allows a global view on the transcription levels of many (or all) genes when...
CLICK: A Clustering Algorithm for Gene Expression Analysis (2000)
Introduction Novel DNA microarray technologies enable the monitoring of expression levels of thousands of genes simultaneously. This allows for the first time a global view on the transcription...
CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis (2000)
Novel DNA microarray technologies enable the monitoring of expression levels of thousands of genes simultaneously. This allows a global view on the transcription levels of many (or all) genes when...
An Algorithm for Clustering cDNA Fingerprints (2000)
Erez Hartuv Armin, Armin O. Schmitt, Jörg Lange, Sebastian Meier-ewert, Hans Lehrach, Ron Shamir
this paper have been presented at the Third International Conference on Computational Molecular Biology (RECOMB '99) (Hartuv et al., 1999)
A Fast Algorithm for Joint Reconstruction of Ancestral Amino Acid Sequences (2000)
Pupko, Tal, Pe, Itsik, Shamir, Ron, Graur, Dan
A dynamic programming algorithm is developed for maximum-likelihood reconstruction of the set of all ancestral amino acid sequences in a phylogenetic tree. To date, exhaustive algorithms that find...
Faster subtree isomorphism (1999)
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O((k 1.5 / log k)n)-time algorithm for...
Bounded degree interval sandwich problems (1999)
The problems of Interval Sandwich (IS) and Intervalizing Colored Graphs (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous...
Clustering Gene Expression Patterns (1999)
Amir Ben-Dor, Ron Shamir, Zohar Yakhini
Recent advances in biotechnology allow researchers to measure expression levels for thousands of genes simultaneously, across different conditions and over time. Analysis of data produced by such...
Complexity Classification of Some Edge Modification Problems (1999)
Assaf Natanzon, Ron Shamir, Roded Sharan
In an edge modification problem one has to change the edge set of a given graph as little as possible so as to satisfy a certain property. We prove the NP-hardness of a variety of edge modification...
Faster Subtree Isomorphism (1999)
Ron Shamir, Dekel Tsur, Dekel Tsur
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O( k 1:5 log k n)-time algorithm for...
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs (1999)
Pavol Hell Ron, Ron Shamir, Roded Sharan
. In this paper we study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a...
Construction of Physical Maps From Oligonucleotide Fingerprints Data (1999)
A new algorithm for the construction of physical maps from hybridization fingerprints of short oligonucleotide probes has been developed. Extensive simulations in high-noise scenarios show that the...
Construction of Physical Maps From Oligonucleotide Fingerprints Data (1999)
A new algorithm for the construction of physical maps from hybridization fingerprints of short oligonucleotide probes has been developed. Extensive simulations in high-noise scenarios show that the...
Ron Shamir, Itsik Pe'er, Lecturers Ron Shamir, Scribe Zivan Ori, Gil Arditi
11.28> c 4 de ! abc 4 c 3 c 2 c 1 de) ffl Transpositions (two parts change places, for example abcd ! acbd) How do these operations take place? If two areas in a chromosome have a prettyhigh...
Algorithms for Molecular Biology - Lecture 12 (1999)
this document we will briefly discuss several topics:
Ron Shamir, Itsik Pe'er, Lecturers Ron Shamir, Scribe Zivan Ori, Gil Arditi
7> de # abc 4 c 3 c 2 c 1 de) . Transpositions (two parts change places, for example abcd # acbd) How do these operations take place? If two areas in a chromosome have a pretty high homology, they...
Complexity Classification of Some Edge Modification Problems (1999)
Assaf Natanzon, Ron Shamir, Roded Sharan
. In an edge modification problem one has to change the edge set of a given graph as little as possible so as to satisfy a certain property. We prove in this paper the NP-hardness of a variety of...
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs (1999)
Pavol Hell, Ron Shamir, Roded Sharan
. In this paper we study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a...
F14.11> abc 4 c 3 c 2 c 1 de) ffl Transpositions (two parts change places, for example abcd ! acbd) How do these operations take place? If two areas in a chromosome have a pretty high homology,...
Faster Subtree Isomorphism (1999)
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O((k / log k)n)-time algorithm for this...
An Algorithm for Clustering cDNAs for Gene Expression Analysis (1999)
Erez Hartuv, Armin Schmitt, Jörg Lange, Sebastian Meier-Ewert, Hans Lehrach, Ron Shamir
We have developed a novel algorithm for cluster analysis that is based on graph theoretic techniques. A similarity graph is defined and clusters in that graph correspond to highly connected...
A Clustering Algorithm based on Graph Connectivity (1999)
We have developed a novel algorithm for cluster analysis that is based on graph theoretic techniques. A similarity graph is defined and clusters in that graph correspond to highly connected...
Bounded Degree Interval Sandwich Problems (1999)
The problems of Interval Sandwich (IS) and Intervalizing Colored Graphs (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous...
Optimizing the BAC-End Strategy for Sequencing the Human Genome (1999)
The rapid increase in human genome sequencing effort and the emergence of several alternative strategies for large-scale sequencing raise the need for a thorough comparison of such strategies. This...
Algorithms for Molecular Biology - Lecture 12 (1999)
this document we will briefly discuss several topics:
Algorithms for Molecular Biology - Lecture 10 (1999)
nning a number of STS probes against numerous clones results in a matrix cell M i,j with the entry 1 (0) representing a positive (negative) result of probe j against clone i,Figure 10.1 gives an...
Faster subtree isomorphism (1999)
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O((k 1.5 / log k)n)-time algorithm for...
Faster subtree isomorphism (1999)
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O((k 1.5 /log k)n)-time algorithm for...
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem (1998)
Assaf Natanzon Ron, Ron Shamir, Roded Sharan
In the minimum fill-in problem, one wishes to find a set of edges of smallest size, whose addition to a given graph will make it chordal. The problem has important applications in numerical algebra...
Construction of Physical Maps From Oligonucleotide Fingerprints Data (1998)
A new algorithm for the construction of physical maps from hybridization fingerprints of short oligonucleotide probes has been developed. Extensive simulations in high-noise scenarios show that the...
A Polynomial Approximation Algorithm for the Minimum Fill-In Problem (1998)
Assaf Natanzon, Ron Shamir, Roded Sharan
In the minimum fill-in problem, one wishes to find a set of edges of smallest size, whose addition to a given graph will make it chordal. The problem has important applications in numerical algebra...
The median problems for breakpoints are NP-complete (1998)
The breakpoint distance between two n-permutations is the number of pairs that appear consecutively in one but not in the other. In the median problem for breakpoints one is given a set of...
The maximum subforest problem: Approximation and exact algorithms (Extended Abstract) (1998)
We study the maximum subforest problem: Given a tree G and a set of trees H, find a subgraph G'of G such that G' does not contain a subtree isomorphic to a tree from H, and the number of...
Algorithms for Optical Mapping (1998)
Optical mapping is a novel technique for determining the restriction sites on a DNA molecule by directly observing a number of partially digested copies of the molecule under a light microscope. The...
Algorithms for Optical Mapping (1998)
Optical mapping is a novel technique for determining the restriction sites on a DNA molecule by directly observing a number of partially digested copies of the molecule under a light microscope. The...
Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals (1998)
Haim Kaplan, Ron Shamir, Robert E. Tarjan
We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its...
The median problems for breakpoints are NP-complete (1998)
The breakpoint distance between two n-permutations is the number of pairs that appear consecutively in one but not in the other. In the median problem for breakpoints one is given a set of...
The maximum subforest problem: Approximation and exact algorithms (1998)
Abstract We study the maximum subforest problem: Given a tree G and a set of trees H, find a subgraph G0 of G such that G0 does not contain a subtree isomorphic to a tree from H, and the number of...
The maximum subforest problem: Approximation and exact algorithms (1998)
We study the maximum subforest problem: Given a tree G and a set of trees H, find a subgraph G ′ of G such that G ′ does not contain a subtree isomorphic to a tree from H, and the number of edges...
Faster Subtree Isomorphism (1997)
We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O( k 1:5 log k n)- time algorithm for...
Realizing Interval Graphs With Size And Distance Constraints (1997)
. We study the following problem: Given an interval graph, does it have a realization which satisfies additional constraints on the distances between interval endpoints? This problem arises in...
Satisfiability Problems on Intervals and Unit Intervals (1997)
For an interval graph with some additional order constraints between pairs of non-intersecting intervals, we give a linear time algorithm to determine if there exists a realization which respects the...
Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals (1997)
Haim Kaplan, Ron Shamir, Robert E. Tarjan
We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its...
Realizing Interval Graphs With Size And Distance Constraints (1997)
.<F3.792e+05> We study the following problem: given an interval graph, does it have a realization which satisfies additional constraints on the distances between interval endpoints? This...
Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques (1996)
We study two related problems motivated by molecular biology: ffl Given a graph G and a constant k, does there exist a supergraph G 0 of G which is a unit interval graph and has clique size at most...
Bibliography on Physical Mapping (1996)
near-time algorithms to test chordality of graphs, text acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Computing, 14:254--255, 1985. [75] P. Buneman. A...
Physical Maps and Interval Sandwich Problems: Bounded Degrees Help (1996)
The problems of Interval Sandwich (IS) and Intervalizing Colored Graphs (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous...
Four strikes against physical mapping of DNA (1995)
Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, Ron Shamir
Physical Mapping is a central problem in molecular biology and the human genome project. The problem is to reconstruct the relative position of fragments of DNA along the genome from information on...
Four Strikes Against Physical Mapping of DNA (1995)
Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, Ron Shamir
Physical Mapping is a central problem in molecular biology and the human genome project. The problem is to reconstruct the relative position of fragments of DNA along the genome from information on...
Interval Graphs with Side Constraints (1995)
Itsik Pe'er, The Raymond, Beverly Sackler, Prepared Dr, Ron Shamir
We study problems of determining whether a given interval graph has a realization which satisfies additional given constraints. Such problems occur frequently in applications where entities are...
Interval Graphs with Side (and Size) Constraints (1995)
. We study problems of determining whether a given interval graph has a realization which satisfies additional given constraints. Such problems occur frequently in applications where entities are...
The domatic number problem on some perfect graph families (1994)
An extremely simple, linear time algorithm is given for constructing a domatic partition in totally balanced hypergraphs. This simplifies and generalizes previous algorithms for interval and strongly...
Pathwidth, Bandwidth and Completion Problems to Proper Interval Graphs with Small Cliques (1994)
We study two related problems motivated by molecular biology: ffl Given a graph G and a constant k, does there exist a supergraph G 0 of G which is a unit interval graph and has clique size at most...
Haim Kaplan, Ron Shamir, Robert E. Tarjan
We study the parameterized complexity of several NP-Hard graph completion problems: The MINIMUM FILL-IN problem is to decide if a graph can be triangulated by adding at most k edges. We develop an...
Algorithms and Complexity of Sandwich Problems in Graphs (extended ) (1994)
Martin Charles Golumbic, Haim Kaplan, Ron Shamir, Ramat Gan Israel
.Given two graphs G 1 = (V, E 1 ) and G = (V, E 2 ) such that E 1 ` E 2 , is there a graph G = (V, E) such that E 1 ` E ` E 2 which belongs to a specified graph family? Such problems generalize...
Complexity and Algorithms for Reasoning About Time: A Graph-Theoretic Approach (1992)
Martin Charles Golumbic, Ron Shamir
Temporal events are regarded here as intervals on a time line. This paper deals with problems in reasoning about such intervals when the precise topological relationship between them is unknown or...
On the efficiency of the simplex method /--by Ron Shamir. (1984)
Thesis (Ph. D. in Industrial Engineering and Operations Research)--University of California, Berkeley, May 1984.
A computational method for resequencing long DNA targets by universal oligonucleotide arrays
Pe'er, Itsik, Arbili, Naama, Shamir, Ron
Universal arrays contain all possible oligonucleotides of a certain length, typically 6–10 bases. They can determine in a single experiment all substrings of that length that occur along a target...
Advanced computational techniques for re-sequencing DNA with polymerase signaling assay arrays
Pe’er, Itsik, Arbili, Naama, Liu, Yi, Enck, Colby, Gelfand, Craig A., Shamir, Ron
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...
Tanay, Amos, Sharan, Roded, Kupiec, Martin, Shamir, Ron
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....
Elkon, Ran, Linhart, Chaim, Sharan, Roded, Shamir, Ron, Shiloh, Yosef
Dissection of regulatory networks that control gene transcription is one of the greatest challenges of functional genomics. Using human genomic sequences, models for binding sites of known...
A Global View of the Selection Forces in the Evolution of Yeast Cis-Regulation
Tanay, Amos, Gat-Viks, Irit, Shamir, Ron
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,...
A Non-EST-Based Method for Exon-Skipping Prediction
Sorek, Rotem, Shemesh, Ronen, Cohen, Yuval, Basechess, Ortal, Ast, Gil, Shamir, Ron
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...
In silico identification of transcriptional regulators associated with c-Myc
Elkon, Ran, Zeller, Karen I., Linhart, Chaim, Dang, Chi V., Shamir, Ron, Shiloh, Yosef
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...
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...
Conservation and evolvability in regulatory networks: The evolution of ribosomal regulation in yeast
Tanay, Amos, Regev, Aviv, Shamir, Ron
Transcriptional modules of coregulated genes play a key role in regulatory networks. Comparative studies show that modules of coexpressed genes are conserved across taxa. However, little is known...
Elkon, Ran, Rashi-Elkeles, Sharon, Lerenthal, Yaniv, Linhart, Chaim, Tenne, Tamar, Amariglio, Ninette, ...
Microarray and RNAi technologies were applied to dissect a transcriptional network induced by DNA damage in human cells, revealing that two pivotal stress-induced transcription factors (NFκB and...
A catalog of stability-associated sequence elements in 3' UTRs of yeast mRNAs
Shalgi, Reut, Lapidot, Michal, Shamir, Ron, Pilpel, Yitzhak
By analyzing 3' UTR sequences and mRNA decay profiles in yeast, 53 sequence motifs have been identified that may be implicated in stabilization or destabilization of mRNA.
EXPANDER – an integrative program suite for microarray data analysis
Shamir, Ron, Maron-Katz, Adi, Tanay, Amos, Linhart, Chaim, Steinfeld, Israel, Sharan, Roded, ...
A computational method for resequencing long DNA targets by universal oligonucleotide arrays
Pe'er, Itsik, Arbili, Naama, Shamir, Ron
Universal arrays contain all possible oligonucleotides of a certain length, typically 6–10 bases. They can determine in a single experiment all substrings of that length that occur along a target...
Advanced computational techniques for re-sequencing DNA with polymerase signaling assay arrays
Pe’er, Itsik, Arbili, Naama, Liu, Yi, Enck, Colby, Gelfand, Craig A., Shamir, Ron
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...
Tanay, Amos, Sharan, Roded, Kupiec, Martin, Shamir, Ron
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....
Elkon, Ran, Linhart, Chaim, Sharan, Roded, Shamir, Ron, Shiloh, Yosef
Dissection of regulatory networks that control gene transcription is one of the greatest challenges of functional genomics. Using human genomic sequences, models for binding sites of known...
A Global View of the Selection Forces in the Evolution of Yeast Cis-Regulation
Tanay, Amos, Gat-Viks, Irit, Shamir, Ron
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,...
A Non-EST-Based Method for Exon-Skipping Prediction
Sorek, Rotem, Shemesh, Ronen, Cohen, Yuval, Basechess, Ortal, Ast, Gil, Shamir, Ron
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...
In silico identification of transcriptional regulators associated with c-Myc
Elkon, Ran, Zeller, Karen I., Linhart, Chaim, Dang, Chi V., Shamir, Ron, Shiloh, Yosef
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...
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...
Conservation and evolvability in regulatory networks: The evolution of ribosomal regulation in yeast
Tanay, Amos, Regev, Aviv, Shamir, Ron
Transcriptional modules of coregulated genes play a key role in regulatory networks. Comparative studies show that modules of coexpressed genes are conserved across taxa. However, little is known...
Elkon, Ran, Rashi-Elkeles, Sharon, Lerenthal, Yaniv, Linhart, Chaim, Tenne, Tamar, Amariglio, Ninette, ...
Microarray and RNAi technologies were applied to dissect a transcriptional network induced by DNA damage in human cells, revealing that two pivotal stress-induced transcription factors (NFκB and...
A catalog of stability-associated sequence elements in 3' UTRs of yeast mRNAs
Shalgi, Reut, Lapidot, Michal, Shamir, Ron, Pilpel, Yitzhak
By analyzing 3' UTR sequences and mRNA decay profiles in yeast, 53 sequence motifs have been identified that may be implicated in stabilization or destabilization of mRNA.
EXPANDER – an integrative program suite for microarray data analysis
Shamir, Ron, Maron-Katz, Adi, Tanay, Amos, Linhart, Chaim, Steinfeld, Israel, Sharan, Roded, ...
A global view of pleiotropy and phenotypically derived gene function in yeast
Dudley, Aimée Marie, Janse, Daniel Maarten, Tanay, Amos, Shamir, Ron, Church, George McDonald
Pleiotropy, the ability of a single mutant gene to cause multiple mutant phenotypes, is a relatively common but poorly understood phenomenon in biology. Perhaps the greatest challenge in the analysis...
Tanay, Amos, Steinfeld, Israel, Kupiec, Martin, Shamir, Ron
Biological systems are orchestrated by heterogeneous regulatory programs that control complex processes and adapt to a dynamic environment. Recent advances in high-throughput experimental methods...
Quantification of protein half-lives in the budding yeast proteome
Belle, Archana, Tanay, Amos, Bitincka, Ledion, Shamir, Ron, O’Shea, Erin K.
A complete description of protein metabolism requires knowledge of the rates of protein production and destruction within cells. Using an epitope-tagged strain collection, we measured the half-life...
A Fast Method for Computing High-Significance Disease Association in Large Population-Based Studies
Because of rapid progress in genotyping techniques, many large-scale, genomewide disease-association studies are now under way. Typically, the disorders examined are multifactorial, and, therefore,...
Network-based prediction of protein function
Sharan, Roded, Ulitsky, Igor, Shamir, Ron
Functional annotation of proteins is a fundamental problem in the post-genomic era. The recent availability of protein interaction networks for many model species has spurred on the development of...
The biological interpretation of genetic interactions is a major challenge. Recently, Kelley and Ideker proposed a method to analyze together genetic and physical networks, which explains many of the...
Refinement and expansion of signaling pathways: The osmotic response network in yeast
The analysis of large-scale genome-wide experiments carries the promise of dramatically broadening our understanding on biological networks. The challenge of systematic integration of experimental...
Functional genomic delineation of TLR-induced transcriptional networks
Elkon, Ran, Linhart, Chaim, Halperin, Yonit, Shiloh, Yosef, Shamir, Ron
Raijman, Daniela, Shamir, Ron, Tanay, Amos
In comparative genomics one analyzes jointly evolutionarily related species in order to identify conserved and diverged sequences and to infer their function. While such studies enabled the detection...
SPIKE – a database, visualization and analysis tool of cellular signaling pathways
Elkon, Ran, Vesterman, Rita, Amit, Nira, Ulitsky, Igor, Zohar, Idan, Weisz, Mali, ...
Ulitsky, Igor, Gat-Viks, Irit, Shamir, Ron
A new computational tool is presented that allows the integration of high-throughput experimental results with the probabilistic modeling of previously obtained information about cellular systems....
From E-MAPs to module maps: dissecting quantitative genetic interactions using physical interactions
Ulitsky, Igor, Shlomi, Tomer, Kupiec, Martin, Shamir, Ron
Recent technological breakthroughs allow the quantification of hundreds of thousands of genetic interactions (GIs) in Saccharomyces cerevisiae. The interpretation of these data is often difficult,...
Linhart, Chaim, Halperin, Yonit, Shamir, Ron
We present a threefold contribution to the computational task of motif discovery, a key component in the effort of delineating the regulatory map of a genome: (1) We constructed a comprehensive...
Approximation Algorithms For The Median Problem In The Breakpoint Model
The problem of genome rearrangement is a central problem in computational molecular biology. When trying to determine the evolutionary history of three species it gives rise to the median problem...
Allegro: Analyzing expression and sequence in concert to discover regulatory programs
Halperin, Yonit, Linhart, Chaim, Ulitsky, Igor, Shamir, Ron
A major goal of system biology is the characterization of transcription factors and microRNAs (miRNAs) and the transcriptional programs they regulate. We present Allegro, a method for de-novo...
Torque: topology-free querying of protein interaction networks
Bruckner, Sharon, Hüffner, Falk, Karp, Richard M., Shamir, Ron, Sharan, Roded
Torque is a tool for cross-species querying of protein–protein interaction networks. It aims to answer the following question: given a set of proteins constituting a known complex or a pathway in...
SlimPLS: A Method for Feature Selection in Gene Expression-Based Disease Classification
Gutkin, Michael, Shamir, Ron, Dror, Gideon
A major challenge in biomedical studies in recent years has been the classification of gene expression profiles into categories, such as cases and controls. This is done by first training a...