November – 2005 ^December

The human genome, the hereditary material we pass on to our progeny, can be seen as a three billion letter string over a DNA alphabet of four. We can currently understand 1.5% of this mass, mostly in the form of genes, DNA substrings that explain how to build proteins, the quintessential constituents of every living cell.

The remainder 98.5% of our genome was deemed as "junk". This picture changed recently when we first obtained the genome sequence of other species. By comparing these genomes to our own we were able to pinpoint the locations of a staggering one million additional human subsequences that must be important to the human cell but do not code for genes. The functions of these regions remain largely unknown, and their sheer volume overwhelms any comprehensive experimental approach.

Coupled with preliminary results from the lab for small sets of these substrings, this data offers a tremendous opportunity to contribute key biological observations using computational approaches. I will discuss several of our own works, aimed at understanding what these subsequence do, and how they came into being.

The talk will assume no prior knowledge in Biology.

TSPs have been intensively researched in undirected graphs. A bit less known is the research for TSPs in directed graphs, although also here quite a bit of research has been done. We will consider the classical minimum variant and also the maximum variant which is also known as the "taxicab ripoff problem".

joint work with: Haim Kaplan, Nira Shafrir and Maxim Sviridenko

The internet is increasingly used to transmit data of real-time applications such as audio and video. Thus, the provisioning of Quality-of-Service over the internet is becoming of key importance. In this work we consider the problem of the online admission and routing of connection requests, each one requesting the reservation of end-to-end bandwidth between the communicating parties. This problem is many times referred to as the "call control problem". We give novel online randomized algorithms on general network topologies, that with high probability achieve at least a polylogarithmic fraction of the optimal solution.

The decisions of our new algorithms do not depend on the current load of {em all} network links, as in previous algorithms for general network topologies (the Awerbuch, Azar, Plotkin algorithm of 1993). Instead, their admission decisions depend only on link loads along a single path between the communicating parties. They can thus be performed in a distributed hop-by-hop manner through the network. Furthermore, our algorithms can handle concurrent requests in the network. These properties make our algorithms applicable in the framework of existing internet protocols.

Joint work with Harald Raecke.

Direct or indirect inter-residue interactions in proteins are often reflected by mutations at one site that compensate for mutations at another site. Various bioinformatic methods have been developed for detecting such correlated mutations in order to obtain information about intra- and inter-protein interactions. Herein, we show by carrying out a correlated mutation analysis for non-interacting proteins that the signal due to inter-residue interactions is of similar magnitude to the 'noise' that arises from other evolutionary processes related to common ancestry. A new method for detecting correlated mutations is presented that reduces this evolutionary noise by taking into account evolutionary distances in the protein family. It is shown that this method yields better signal-to-noise ratios and, thus, can much better resolve, for example, correlated mutations that reflect true inter-residue interactions.

Elkin, Emek, Spielman and Teng showed recently that every graph can be probabilistically embedded into a distribution over its spanning trees with polylogarithmic expected distortion, narrowing the gap left by Alon, Karp, Peleg and West that established a logarithmic lower bound in 1995. This lower bound holds even for the class of series-parallel graphs as Gupta, Newman, Rabinovich and Sinclair proved in 1999.

In this work we close this gap for series-parallel graphs, namely, we prove that every $n$-vertex series-parallel graph can be probabilistically embedded into a distribution over its spanning trees with expected stretch $O(\log{n})$ for every two vertices. We gain our upper bound by presenting a polynomial time probabilistic algorithm that constructs spanning trees with low expected stretch. This probabilistic algorithm can be derandomized to yield a deterministic polynomial time algorithm for constructing a spanning tree of a given series-parallel graph $G$, whose communication cost is at most $O(\log{n})$ times larger than that of $G$ .

Bio:
Yuval is a Ph.D. student at the Department of Computer Science and Applied Mathematics in the Weizmann Institute of Science. His fields of interest include combinatorial optimization, graph theory and coping with NP-hardness. He is conducting his research under the advice of Prof. David Peleg. Yuval has a B.A. in computer science from the Technion (summa cum laude) and an M.Sc. from the Weizmann Institute of Science. He is on the Feinberg Graduate School Dean's list of honor for 2005.

Let $G=(V,E)$ be a graph and let $S$ be a subset of $V$. The $S$-connectivity $\lambda_S(u,v;G)$ of $u$ and $v$ in $G$ is the maximum number of $uv$-paths that no two of them have an edge or a node in $S-{u,v}$ in common. We consider the following problem on undirected graphs:

Connectivity Augmentation Problem (CAP): Instance: A graph $G=(V,E)$, a node subset $S \subseteq V$, and an integer requirement function $r(u,v)$ on $V \times V$. Objective: Add a minimum size set $F$ of new edges to $G$ so that $\lambda_S(u,v;G+F) \geq r(u,v)$ for all $u,v \in V$.

Three extensively studied particular choices of $S$ are: the edge-CAP ($S=\emptyset$), the node-CAP ($S=V$), and the element-CAP ($r(u,v)=0$ whenever $u \in S$ or $v \in S$). A polynomial algorithm for edge-CAP was developed by Andras Frank. We consider the element-CAP and the node-CAP, that are NP-hard even for $r(u,v) \in \{0,2\}$.

We show a $7/4$-approximation algorithm for the element-CAP, improving the previously best known $2$-approximation. The approximation ratio is based on a new lower bound on the number of edges needed to cover a skew-supermodular set function.

For the node-CAP we establish an approximation threshold indicating that the node-CAP is unlikely to have a polylogarithmic approximation.

If the time a allows I will also describe a tight $O(\log n)$-approximation for arbitrary $S \neq V$ (this part is a joint work with Guy Kortsarz).

Bio:
Education:D.Sc. Applied Mathematics, Technion, Haifa, Israel
Postdocs:
1. Dept. of Combinatorics and Optimization, Univ. of Waterloo, Canada
2. Max-Planck-Institute fur Informatik, Saarbrucken, Germany.
Since March 2000: Lecturer at the CS Dept. at the Open University of Israel.
Since Nov. 2004: Chair of the CS Dept. at the Open University of Israel.

FIELDS OF INTEREST:
Approximation and exact algorithms, hardness of approximation; network design, connectivity augmentation, feedback set problems, cover and packing problems, scheduling problems, facility location problems,Combinatorial Optimization, Combinatorics, Graph Theory.

In the nearest neighbor search problem, we are required to preprocess a database X in order to quickly answer queries of the following type: Given a new item y, find the (approximate) closest item in X. In this talk I'll present an algorithm for this problem when the distances between the items in X form a "low dimensional" metric. Another application of our technique is distributed and linear storage representations of the pairwise distances in X. The main technical tool being used is a fast algorithm for constructing hierarchical nets in low dimensional finite metric spaces

Joint work with S. Har-Peled

BIO:

Manor Mendel teaches computer science at the Open University of Israel. His main research interests focus on geometric methods in the design of approximation algorithms, with emphasis on the theory of embeddings of finite metric spaces.