Approximate Pattern Matching with Index Structures
Johannes Krugel · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2016
Approximate pattern matching (APM) deals with searching a pattern in a text or biological sequence tolerating some errors (e.g. spelling mistakes or genetic mutations). We provide efficient implementations of data structures and algorithms for APM in a software library. Furthermore, we propose a new efficient algorithm for APM using suffix trees in external memory. We perform extensive experimental evaluations using real-world and synthetic test instances and give recommendations for appropriate choices of the methods.