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.
