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...
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...
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...
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...
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,...
Modeling and Analysis of Heterogeneous Regulation in (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...
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...
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...
Journal of Bioinformatics and Computational Biology (2004)
this paper we address the IPPH problem
A Simpler and Faster 1.5-Approximation Algorithm for Sorting by (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...
Computational Problems in Perfect Phylogeny Haplotyping: (2004)
Tag Snps, Tamar Barzuza, Jacques S. Beckmann, 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...
The Canine Olfactory Subgenome (2004)
Tania Fuchs, Chaim Linhart, Ron Shamir, Mark Adams, Francis Kalush, Miriam Khen
We identified 971 olfactory receptor (OR) genes in the dog genome, estimated to constitute f80% of the canine OR repertoire. This was achieved by directed genomic DNA cloning of olfactory sequence...
How Prevalent is Functional Alternative Splicing in the (2004)
this article can be found at doi: 10.1016/j.tig.2003.12.004 Corresponding author: Gil Ast (gilast@post.tau.ac.il)
Faster Subtree Isomorphism (2004)
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...
Maximum Likelihood Resolution of Multi-block Genotypes (2004)
We present a new algorithm for the problems of genotype phasing and block partitioning. Our algorithm is based on a new stochastic model, and on the novel concept of probabilistic common haplotypes....
Incomplete Directed Perfect Phylogeny (2003)
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...
Improved Algorithms for the Random Cluster Graph Model (2003)
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...
Multi-level Modeling and Inference of (2003)
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...
Detecting Excess Radical Replacements in Phylogenetic Trees (2003)
Tal Pupko, Roded Sharan, Masami Hasegawa, Ron Shamir, Dan Graur
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...
Cluster Graph Modification Problems (2003)
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...
CLICK and EXPANDER: A System for Clustering and Visualizing Gene (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...
Identification of Protein Complexes by Comparative Analysis of (2003)
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...
Bioinformatics Applications Note (2003)
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....
Computational Problems in Noisy SNP and Haplotype (2003)
this paper we address several problems that arise in haplotype studies. Our starting point is a very natural optimization criterion: We wish to nd a block partition that minimizes the total number of...
Identifying Blocks and Sub-Populations in Noisy SNP Data (2003)
We study several problems arising in haplotype block partitioning.
Ran Elkon, Chaim Linhart, Roded Sharan, Ron Shamir
Dissection of regulatory networks that control gene transcription is one of the greatest challenges of functional genomics. By utilizing human genomic sequences, models for binding sites of known...
A Fully Dynamic Algorithm for Modular Decomposition and Recognition of Cographs (2003)
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...
Large Scale Sequencing by Hybridization (2003)
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...
The Restriction Scaffold Problem (2003)
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...
Modeling Transcription Programs: Inferring Binding Site (2003)
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 localization...
Computational Molecular Biology (2003)
Istrail, Sorin (ed.), Pevzner, Pavel (ed.), Shamir, Ron (ed.)
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...
Faster Subtree Isomorphism (2002)
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...
Cluster Graph Modification Problems (2002)
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...
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 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...
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...
Haim Kaplan, Ron Shamir, E. Tarjan
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 O(c m)...
A Faster And Simpler Algorithm For Sorting Signed Permutations By Reversals (2002)
Haim Kaplan, Ron Shamir, E. Tarjan
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 Pevzner and...
Bounded Degree Interval Sandwich Problems (2002)
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...
On the Complexity of DNA Physical Mapping (2002)
Martin Charles Golumbic, Ramat Gan Israel, 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...
Four Strikes Against Physical Mapping of DNA (2002)
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...
Graph Sandwich Problems (2002)
Martin Charles Golumbic, Haim Kaplan, Ron Shamir
The graph sandwich problem for property Pi is defined as follows: Given two graphs G ) such that E ` E , is there a graph G = (V; E) such that E which satisfies property Pi? Such problems generalize...
The Domatic Number Problem on Some Perfect Graph Families (2002)
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 (2002)
We study two related problems motivated by molecular biology: ffl Given a graph G and a constant k, does there exist a supergraph G of G which is a unit interval graph and has clique size at most k?...
Positive selection 1 A test for positive Darwinian selection (2002)
Tal Pupko, Roded Sharan, Ron Shamir, Dan Graur
Introduction. 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...
The Restriction Scaffold Problem (2002)
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...
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...
The median problems for breakpoints are NP-complete (2001)
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...
Bioinformatics Discovery Note (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...
Algorithmic Approaches to Clustering Gene Expression Data (2001)
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 first...
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs (2001)
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...
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs (2001)
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...
A Clustering Algorithm based on Graph Connectivity (2000)
We have developed a novel algorithm for cluster analysis that is based on graph theoretic techniques.
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.
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...
An Algorithm Combining Discrete and Continuous Methods for Optical Mapping (2000)
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 for Clustering cDNA Fingerprints (2000)
Erez Hartuv, Armin O. Schmitt, Jo Rg Lange, Hans Lehrach, Ron Shamir
this paper have been presented at the Third International Conference on Computational Molecular Biology (RECOMB '99) (Hartuv et al., 1999)
Approximation Algorithms For The Median Problem In The Breakpoint Model (2000)
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...
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs (2000)
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...
Perfect Completion and Deletion in Random Graphs (1999)
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...
An Algorithm Combining Discrete and Continuous Methods for Optical Mapping (1999)
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...
The median problems for breakpoints are NP-complete (1999)
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...
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...
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...
Algorithms for Optical Mapping (1999)
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...
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...
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...
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...
Satisfiability Problems on Intervals and Unit Intervals (1999)
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...
Interval Graphs with Side (and Size) Constraints (1999)
. 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...
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...
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...
ne in O(n 2 ) time in total, for all the n-1 iterations. 3. Quartet Puzzling: When constructing phylogeny based upon sequences of many proteins, one runs into the problem of not having all proteins...
Multiple Sequence Alignment (1999)
r than align it only to the center. (b) Suppose we use a star centered at a random sequence S i , rather than the true center sequence S c . Prove that this does not give a constant worst-case...
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...