Recent Advancements in Approximate Pattern Matching

Abstract

Pattern matching is an action most of us perform daily when we search for a term on the web or a word in a document.  In most applications, finding the exact occurrences of a pattern in a text is not enough: Think of human spelling mistakes or DNA sequencing errors, for example. In this talk, we will review recent structural and algorithmic results on approximate pattern matching (APM) under the most fundamental distance metrics: the Hamming distance and the (weighted) edit distance. Specifically, we will discuss the "few occurrences or almost periodicity" paradigm and how it yields efficient APM algorithms; a conceptually simple new algorithm for APM under weighted edit distance that nearly-matches the state-of-the-art for the unweighted variant [Landau, Vishkin; J. Algorithms’89] using very different techniques.

Speaker

Panagiotis Charalampopoulos is a Lecturer in Computer Science at King's College London. He works in theoretical computer science and is broadly interested in algorithms and data structures, with a particular focus on strings and planar graphs. Before joining King's, Panagiotis was a Lecturer at Birkbeck, University of London. Prior to that, he was a postdoctoral fellow at Reichman University. Panagiotis obtained his PhD from King's College London.