קולקוויום מחלקתי 29.2.24

Professor Paul Medvedev

 Pennsylvania State University

WILL LECTUTE ON

Title: The theoretical analysis of sequencing bioinformatic algorithms

Abstract:

The theoretical analysis of algorithm performance has been an important tool in the engineering of algorithms in many application domains. Its goals are to predict the empirical performance of an algorithm and to be a yardstick that drives the design of novel algorithms that perform well in practice. However, when it comes to sequencing bioinformatics, an application area concerned with algorithms for biological sequencing data, theoretically analyzing algorithms has been challenging and has had a mixed record in achieving its goals. In this talk, I will make an attempt at the first systematic and critical survey of the application of theoretical analysis of algorithm techniques to sequencing bioinformatics. I explore some of the techniques that have been applied and the extent to which they have been successful. I use the edit distance computation problem as a case study but also explore the problems of genome assembly, structural variation detection, and compact data structures. I conclude by discussing steps that can be taken to help improve the impact and applicability of the theoretical analysis of algorithms in sequencing bioinformatics. This work will cover two recent papers that have been published/accepted in Communications of the ACM:

https://cacm.acm.org/magazines/2023/7/274044-theoretical-analysis-of-sequencing-bioinformatics-algorithms-and-beyond/fulltext

https://arxiv.org/abs/2204.09535

Short Bio:

Paul Medvedev is Professor in the Department of Computer Science and Engineering and the Department of Biochemistry and Molecular Biology and the Director of the Center for Computational Biology and Bioinformatics at the Pennsylvania State University. His research focus is on developing computer science techniques for analysis of biological data and on answering fundamental biological questions using such methods. Prior to joining Penn State in 2012, he was a postdoc at the University of California, San Diego and a visiting scholar at the Oregon Health & Sciences University and the University of Bielefeld. He received his Ph.D. from the University of Toronto in 2010, his M.Sc. from the University of Southern Denmark in 2004, and his B.S. from the University of California, Los Angeles in 2002.