Gabriel Bathie (M2F department, LX & Synthèse team) was awarded the prize for best paper at the 35th Annual Symposium on Combinatorial Pattern Matching, held last June in Fukuoka (Japan).
This article was co-written with Panagiotis Charalampopoulos (Birkbeck, University of London) and Tatiana Starikovskaya (DI ENS Ulm).
In this article, we focus on the task of internal pattern matching (IPM) in strings.
In this context, we are given a sequence of letters, for example a sequence of A, C, G or T representing a DNA strand, and we must answer questions of the form “does this sub-part of the DNA strand appear somewhere else in the strand, and if so, where?” as efficiently as possible.
IPM is a basic building block for solving many string problems, such as longest common substring or circular pattern matching.
Efficient algorithms for solving IPM are memory-intensive on large strings such as whole genomes.
In this article, our main contribution is an algorithm for solving IPM whose memory consumption can be adapted to the available resources while maintaining the highest possible efficiency.