Are stable instances easy? (2009)
We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. The question then...
ProtoNet: Navigating the Hierarchical Clustering of the Protein Space (2008)
Ori Sasson, Hillel Fleischer, Elon Portugaly, Yonatan Bilu, Nathan Linial, Michal Linial
The ProtoNet site provides an automatic hierarchical clustering of the protein space. The clustering is based on an all-against-all BLAST similarity test. With this similarity measure we proceed to...
On codes from hypergraphs (2008)
We propose a new family of asymptotically good binary codes, generalizing previous constructions of expander codes to ¢-uniform hypergraphs. We also describe an efficient decoding algorithm for...
The evolution of microRNA-regulation in duplicated genes facilitates expression divergence (2008)
Background: The evolution of microRNA regulation in metazoans is a mysterious process: MicroRNA sequences are highly conserved among distal organisms, but on the other hand, there is no evident...
On the functional properties of microRNA-mediated feed forward loops (2008)
Motivation: Recent studies of genomic-scale regulatory networks suggested that a feed-forward loop (FFL) circuitry is a key component of many such networks. This led to a study of the functional...
Faster Algorithms for Optimal Multiple Sequence Alignment based on Pairwise Comparisons ∗ (2008)
Pankaj K. Agarwal, Yonatan Bilu, Rachel Kolodny
Multiple Sequence Alignment (MSA) is one of the most fundamental problems in computational molecular biology. The running time of the best known scheme for finding an optimal alignment, based on...
Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map : H! G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n...
We propose a new family of asymptotically good binary codes, generalizing previous constructions of expander codes to t-uniform hypergraphs. These new codes have a better distancerate tradeoff than...
Yonatan Bilu, Professor Nati Linial, D. K. Scully
On spectral properties of graphs, and their application to clustering
Yonatan Bilu, Tomer Shlomi, Naama Barkai, Eytan Ruppin
Variation in gene expression levels on a genomic scale has been detected among different strains, among closely related species, and within populations of genetically identical cells. What are the...
Yonatan Bilu, Tomer Shlomi, Naama Barkai, Eytan Ruppin
Variation in gene expression levels on a genomic-scale has been detected among different strains, among closely related species and within populations of genetically identical cells. What are the...
Yonatan Bilu, Tomer Shlomi, Naama Barkai
Variation in gene expression levels on a genomic scale has been detected among different strains, among closely related species, and within populations of genetically identical cells. What are the...
The design of transcription-factor binding sites is affected by combinatorial regulation (2005)
Background Transcription factors regulate gene expression by binding to specific cis -regulatory elements in gene promoters. Although DNA sequences that serve as transcription-factor binding sites...
Hofmman's bound on the chromatic number of a graph states that $\chi \geq 1 - \frac {\lambda_1} {\lambda_n}$. Here we show that the same bound, or slight modifications of it, hold for several graph...
Monotone Maps, Sphericity and Bounded Second Eigenvalue (2004)
We consider {\em monotone} embeddings of a finite metric space into low dimensional normed space. That is, embeddings that respect the order among the distances in the original space. Our main...
Lifts, discrepancy and nearly optimal spectral gaps (2004)
We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G...
Monotone Maps, Sphericity and Bounded Second Eigenvalue (2004)
We consider monotone embeddings of a nite metric space into low dimensional normed space. That is, embeddings that respect the order among the distances in the original space. Our main interest is in...
Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap (2003)
We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let $G$ be a graph on $n$ vertices. A 2-lift...
ProtoNet: hierarchical classification of the protein space (2003)
Ori Sasson, Avishay Vaaknin, Hillel Fleischer, Elon Portugaly, Yonatan Bilu, Nathan Linial, ...
The ProtoNet site provides an automatic hierarchical clustering of the SWISS-PROT protein database. The clustering is based on an all-against-all BLAST similarity search. The similarities ’ E-score...
ProtoNet: hierarchical classification of the protein space (2003)
Ori Sasson, Avishay Vaaknin, Hillel Fleischer, Elon Portugaly, Yonatan Bilu, Nathan Linial, ...
The ProtoNet site provides an automatic hierarchical clustering of the SWISS-PROT protein database. The clustering is based on an all-against-all BLAST similarity search. The similarities ’ E-score...
ProtoNet: hierarchical classification of the protein space (2003)
Sasson, Ori, Vaaknin, Avishay, Fleischer, Hillel, Portugaly, Elon, Bilu, Yonatan, Linial, Nathan, ...
The ProtoNet site provides an automatic hierarchical clustering of the SWISS-PROT protein database. The clustering is based on an all-against-all BLAST similarity search. The similarities' E-score is...
A gap in average proof complexity (2002)
We present the first example of a natural distribution on instances of an NP-complete problem, with the following properties. With high probability a random formula from this distribution (a) is...
Sequence similarity is probably the most widely used tool to infer functional linkage between proteins. The fully sequenced, much researched, genome of Saccharomyces cerevisiae gives us on...
Finding a randomly planted assignment in a random 3CNF (2002)
Eli Ben-sasson, Yonatan Bilu, Danny Gutfreund
Abstract We discuss the problem of finding a satisfying assignment for a randomly chosen satisfiable 3- CNF with n variables and \Delta n clauses, where \Delta is much greater than the satisfiability...
Locating Transcription Factors Binding Sites Using a Variable Memory Markov Model (2001)
Yonatan Bilu, Michal Linial, Noam Slonim, Naftali Tishby
We propose a novel method for locating transcription factors binding sites in upstream regions, by employing a variable memory Markov model (VMM) based feature selection method. Using this method we...
ProtoNet: hierarchical classification of the protein space
Sasson, Ori, Vaaknin, Avishay, Fleischer, Hillel, Portugaly, Elon, Bilu, Yonatan, Linial, Nathan, ...
The ProtoNet site provides an automatic hierarchical clustering of the SWISS-PROT protein database. The clustering is based on an all-against-all BLAST similarity search. The similarities' E-score is...
The design of transcription-factor binding sites is affected by combinatorial regulation
A comprehensive analysis of binding site locations in yeast shows that essential genes bind selectively few transcription factors and that novel binding sites tend to appear in promoters that are...
Bilu, Yonatan, Shlomi, Tomer, Barkai, Naama, Ruppin, Eytan
Variation in gene expression levels on a genomic scale has been detected among different strains, among closely related species, and within populations of genetically identical cells. What are the...
ProtoNet: hierarchical classification of the protein space
Sasson, Ori, Vaaknin, Avishay, Fleischer, Hillel, Portugaly, Elon, Bilu, Yonatan, Linial, Nathan, ...
The ProtoNet site provides an automatic hierarchical clustering of the SWISS-PROT protein database. The clustering is based on an all-against-all BLAST similarity search. The similarities' E-score is...
The design of transcription-factor binding sites is affected by combinatorial regulation
A comprehensive analysis of binding site locations in yeast shows that essential genes bind selectively few transcription factors and that novel binding sites tend to appear in promoters that are...
Bilu, Yonatan, Shlomi, Tomer, Barkai, Naama, Ruppin, Eytan
Variation in gene expression levels on a genomic scale has been detected among different strains, among closely related species, and within populations of genetically identical cells. What are the...