^April May – 2008 ^June

Speaker BIO: Dr. Swidan was a fellow in the Technion Excellence program and finished his B.A. in Mathematics at the Technion with Summa Cum Laude. He got his PhD in computer science (bioinformatics) from the Technion. Dr. Swidan was the first post doc to join the newly established Janelia Farms Research campus of the Howard Hughes Medical Institute. Currently, he is the CEO and founder of Olymons (TM), Blessing Machines with Vision (TM), and a fellow in the Edmond J. Safra bioinformatic program at Tel-Aviv University. His research work includes the following topics: image processing and computer vision, combinatorial algorithms and their applications to computational molecular biology, genome rearrangement, comparative genomics, phylogenetic inference, string algorithms, graph algorithms, and patten matching algorithms. Title: Reconstructing repeat-annotated phylogenetic trees Abstract: A new problem in phylogenetic inference is presented, based on recent biological findings indicating a strong association between reversals and repeats. These biological findings are formalized here in a new mathematical model, called repeat-annotated phylogenetic trees (RAPT). We show that, under RAPT, the evolutionary process - including both the tree-topology as well as internal node genome orders - is uniquely determined, a property of major significance both in theory and in practice. Furthermore, the repeats are employed to provide linear-time algorithms for reconstructing both the genomic orders and the phylogeny, which are NP-hard problems under the classical model of sorting by reversals (SBR). For that, a new data structure - namely set-tries - is presented, and is shown to support efficient linear-time insert and find operations. Joint work with Michal Ziv-Ukelson and Ron Pinter. The presentation is self contained.

A conflict-free coloring (CF-coloring) of hypergraph $H=(V,E)$ is a coloring of V such that for any hyperedge e in E there exists a vertex v in e with a unique color in e (i.e., no other vertex of e has the same color as v). The problem was introduced by Even et al. In 2002 and has applications in frequency assignment for cellular networks. We will briefly review the literature. We investigate deterministic online algorithms for the above problem for hypergraphs that arise in geometry (conflict-free coloring collinear points with respect to intervals). The best offline algorithm uses $O(\log n)$ colors, whereas the best online algorithm from Chen et al. uses $O(log^2 n)$ colors. We give the first deterministic online algorithm using $O(\log n)$ colors, in a non-trivial online model. We also provide a tight analysis of the worst-case performance of the greedy algorithm, solving an open problem from Chen et al.

We provide a framework for online CF-coloring any hypergraph in the oblivious adversary model. We use this framework to obtain efficient (order-optimal, i.e. using logarithmic number of colors) randomized online algorithms for CF-coloring some hypergraphs that arise in geometry and model an important version of the frequency assignment task for cellular networks. Our algorithms use fewer random bits and fewer colors than other algorithms in the literature. We also initiate the study of deterministic online CF-coloring with recoloring. The goal is to use few colors, but also resort to recoloring as little as possible. We provide algorithms using $O(\log n)$ colors and doing $O(n)$ recolorings.

Joint work with Amotz Bar-Noy, Svetlana Olonetsky, and Shakhar Smorodinsky

The vertex coloring and maximal independent set (henceforth, MIS) problems are central problems in the field of distributed algorithms and are intensively studied. Currently there are no known deterministic distributed algorithms that solve these problems in polylogarithmic time on general graphs. Goldberg, Plotkin, and Shannon, STOC'87, devised a logarithmic time algorithm for these problems on planar graphs. We devise a technique based on Nash-Williams forests decomposition that enables to compute efficiently a vertex coloring that uses a small number of colors on graphs with bounded arboricity. Then this coloring is used to compute an MIS in sublogarithmic time on this family of graphs. This family includes planar graphs, graphs with bounded genus, and graphs that exclude fixed minors, and thus our result improves and generalizes the twenty-year old result of Goldberg, Plotkin, and Shannon. We also show a nearly tight lower bound for the time required for computing distributed O(a)-coloring and O(a)-forests-decomposition. Based on joint work with Michael Elkin.

Microarrays have evolved over recent years to address a range of genomic measurement tasks. The development of array based genome wide DNA copy number profiling has opened the door to a variety of other applications.

Manufacturing techniques that enable flexible design of probes and complete arrays in various sizes complete the picture to yield a versatile measurement platform.

I will describe the use of microarrays in several collaborative efforts, including studies of the time of replication in S phase (collaboration with HUJI), studies of chromosomal aberrations in cancer (collaborations with NCI and with Oslo University) and of copy number vaiations (CNVs) in normal populations (collaboration with Harvard). The talk will specifically address some of the computational aspects of flexible designs and applications.

We present a new randomized algorithm for finding a maximum matching in H-minor free graphs. For every fixed H, our algorithm runs in ${O}(n^{3\omega/(\omega+3)}) < O(n^{1.326})$ time, where n is the number of vertices of the input graph and $\omega < 2.376$ is the exponent of matrix multiplication. This improves upon the previous $O(n^{1.5})$ time bound obtained by applying the $O(m{n}^{1/2})$-time algorithm of Micali and Vazirani on this important class of graphs. For graphs with bounded genus, which are special cases of H-minor free graphs, we present a randomized algorithm for finding a maximum matching in ${O}(n^{\omega/2}) < O(n^{1.19})$ time. This extends a previous randomized algorithm of Mucha and Sankowski, having the same running time, that finds a maximum matching in planar graphs. We also present a deterministic algorithm with a running time of $O(n^{1+\omega/2}) < O(n^{2.19})$ for counting the number of perfect matchings in graphs with bounded genus. This algorithm combines the techniques used by the algorithms above with the counting technique of Kasteleyn. Using this algorithm we can also count, within the same running time, the number of T-joins in planar graphs. As special cases, we get algorithms for counting Eulerian subgraphs ($T=\phi$) and odd subgraphs ($T=V$) of planar graphs. The proof uses tools from structural graph theory, computational algebra, and linear algebra. Joint work with Uri Zwick.