COLLOQUIUM Department of Computer Science and Engineering University of South Carolina Genome Rearrangements: from Biological Problems to Combinatorial Algorithms (and back) Max Alekseyev Department of Computer Science and Engineering University of California, San Diego Date: May 5, 2008 Time: 1530-1700 (3:30pm-5pm) Place: 300 Main B213 Abstract Comparative genomic studies fueled by recent large-scale sequencing projects have revealed that some classical biological theories may be incomplete or even incorrect. In this talk, I will first describe three controversial and hotly debated topics: whole genome duplications, the random breakage model of chromosome evolution, and mammalian phylogenomics. I will then present three related challenging combinatorial problems: genome halving, breakpoint reuse, and ancestral genomes reconstruction. I have recently addressed these problems within a new "multi-break rearrangements" framework that simplified their analysis and led to efficient algorithmic solutions. I will describe the new framework and the application of new algorithms for sequencing mammalian genomes to the study of the three biologically motivated problems mentioned above. Max Alekseyev is a Postdoctoral Fellow in Computer Science at the University of California, San Diego (UCSD). He received his PhD in Computer Science from UCSD in 2007. Prior to joining UCSD in 2001, he obtained the MS degree in Mathematics from Nizhni Novgorod State University, Russia. His research interests include computational molecular biology, bioinformatics, comparative genomics, graph theory, combinatorics, and discrete algorithms. He is an associate editor of and a regular contributor to the Online Encyclopedia of Integer Sequences (OEIS) where he extended many computationally hard sequences.