Title: “Are There Fragile Regions in the Human Genome?”

Pavel Pevzner, Ronald R. Taylor Distinguished Professor of Computer Science

University of California at San Diego

The Alberto Apostolico Lecture Series was endowed in 2015 to commemorate the life of Professor Alberto Apostolico, late of the Schools of Computational Science & Engineering and Interactive Computing. Prof. Apostolico was an influential figure in the computer science subdiscipline of string algorithms, and his contributions to the field will be honored by those chosen to deliver lectures bearing his name.

Abstract

In 2010-2015, Alberto Apostolico published an influential series of papers on alignment-free string comparison. In 2012, the original approach to alignment-free string comparison (based on comparing k-mers compositions) was extended to analyzing colored de Bruijn graphs to characterize the differences between strings. In this talk, I will discuss applications of the colored de Bruijn graphs to analyzing genome rearrangements.

A fundamental question in chromosome evolution is whether there exist fragile regions (rearrangement hotspots) where chromosomal rearrangements are happening over and over again. I demonstrate that the fragile regions do exist and further show that they are subject to a ``birth and death'' process, implying that fragility has limited evolutionary lifespan. To establish this biological result, I will prove some theorems about the breakpoint graphs, the workhorse of genome rearrangement studies. I will further illustrate that both breakpoint graphs and de Bruijn graphs are special cases of a more general notion of A-Bruijn graphs that found many applications in computational biology.

Bio

Pavel Pevzner is Ronald R. Taylor distinguished professor of computer science at UCSD where he directs the National Technology Center for Computational Mass Spectrometry. He holds a Ph.D. (1988) from the Moscow Institute of Physics and Technology, Russia. Pevzner was named Howard Hughes Medical Institute Professor in 2006 and was elected as an Association for Computing Machinery Fellow in 2010 for "contribution to algorithms for genome rearrangements, DNA sequencing, and proteomics.” He is also a Fellow of the International Society for Computational Biology Fellow (2012), and in 2011 Pevzner was awarded an honorary degree from Simon Fraser University in Vancouver. He is the author of multiple textbooks, including Computational Molecular Biology: An Algorithmic Approach (2000), Introduction to Bioinformatics Algorithms (2004 with Neal Jones), and Bioinformatics Algorithms: An Active Learning Approach (2014 with Phillip Compeau). In 2013 he offered Coursera’s first MOOC on bioinformatics, which was turned into a bioinformatics specialization in 2015.