Title: Graph Modification Problems and their Applications to Genomic Research
Many problems in computational biology can be modeled using graphs. In this talk I will describe two such problems. In the first, the graph undergoes dynamic changes. In the second, some edges must be added so as to satisfy a desired property.
I will first describe a near optimal algorithm for the problem of recognizing and representing dynamically changing proper interval graphs, which has applications in physical mapping of DNA. The input to the problem consists of a series of modifications to be performed on a graph, where a modification can be a deletion or an addition of a vertex or an edge. The objective is to maintain a representation of the graph as long as it remains a proper interval graph, and to detect when it ceases to be so. The algorithm operates in O(log n) worst-case time per edge insertion or deletion. The second part will introduce the perfect phylogeny model for studying evolution and discuss the problem of phylogeny reconstruction from incomplete data. I will present a near optimal algorithm for the problem, improving over extant work. The algorithm relies on a graph sandwich reformulation of the problem and data structures for dynamically maintaining graph connectivity. Joint work, in parts with P. Hell, I. Pe'er and R. Shamir. The results in this talk are part of the Ph.D. thesis of Roded Sharan, done under the supervision of Ron Shamir.