We begin with an overview of the Drosophila genome project, whose  goal is the sequencing and comparison of 12 fruit fly genomes. In  particular, we discuss transposable elements. These are self- replicating sequences that play a major role in shaping the structure  and function of genomes. Our methods for studying transposable  elements lead naturally to the analysis of split systems and their  associated phylogenetic networks. We discuss various aspects of the  neighbor-net algorithm, which is a widely used method for obtaining  phylogenetic networks from split systems. We show that neighbor-net  is a greedy algorithm for the traveling-salesman problem and explain  its connection to the popular neighbor-joining algorithm. We also  prove that neighbor-net is statistically consistent, and in doing so  obtain a new proof that the traveling-salesman problem can be solved  in polynomial time for Kalmanson matrices. This result is closely  related to results we have recently obtained on the robustness of the  neighbor-joining algorithm. Our application of neighbor-net to the  split system we obtain from transposable elements in Drosophila  reveals interesting insights about a set of species that may have  undergone lineage sorting.

This is joint work with Anat Caspi, Dan Levy, and Radu Mihaescu.

Tuesday, April 24, 2007
3:00 pm - 4:15 pm

3330 Walnut Street
307 Levine Hall