[Lowerbounds, Upperbounds]

Algorithms are everywhere.

ALADDIN WORKSHOP ON FLEXIBLE NETWORK DESIGN
November 4-5, 2005
Princeton University

Network Design with its many variants is one of the most active mathematical research areas involving researchers from Theoretical Science, Graph Theory, Operations Research, Discrete Optimization, Game Theory and Information Theory.

The goal of this workshop is to focus on this active area of applications of algorithms to understand current trends, identify understudied areas, and formulate new directions for further investigation. To this end, the workshop participants include an eclectic mix of experts from real-world network design and deployment, graph algorithms, network coding, algorithmic mechanism design applied to pricing problems in networks, and configuration and routing of networks.

REGISTRATION AND ADDITIONAL INFORMATION

There is no fee to attend this workshop, but advance registration is required. For more details about the workshop and to register online, please visit http://www.aladdin.cs.cmu.edu/workshops/netdes/index.html.

QUESTIONS?

For questions about registration, please contact Susan Hrishenko at Carnegie Mellon University, (email susan027@cs.cmu.edu or phone 412-268-7317). For questions about local arrangements, please contact Mitra Kelly at Princeton University (email mkelly@cs.princeton.edu or phone 609-258-4562).

Title: Reconstructing Evolutionary Trees Optimally

Speaker: Srinath Sridhar, CSD

Location: NSH 1507
Time: 12-1 pm
Date: Friday, October 28th, 2005

Abstract:

Evolutionary trees are fundamental to our understanding of the mechanisms of nature. They have been used to solve many important problems, such as tracing the evolution of diverse species and tracking historical human migration patterns. Over the last decade, there has been a tremendous
amount of research in the area bringing together theoreticians and biologists. In this talk, I will focus on reconstructing evolutionary trees optimally by finding the smallest (most parsimonious) tree for an input set of DNA sequences. We will consider an important special case of the problem that is equivalent to finding the minimum Steiner tree in Hamming space. In this talk, I will formulate the problem, prove a simple lower bound on the size of the smallest tree and outline an algorithm to reconstruct it. Finally, I will show experimental results using DNA from humans (multiple ethnic groups) and other primates.