Get-Together for String Algorithms Researchers in Helsinki

Event type: 
Event time: 
22.03.2012 - 16:15 - 18:00
Exactum B119

The program consists of a talk by Veli Mäkinen:

Title: Multi-pattern matching with bidirectional indexes


We study multi-pattern matching in a scenario where the pattern set is to be matched to several texts and hence indexing the pattern set is affordable. This kind of scenarious arise e.g. in metagenomics, where pattern set represents DNA of several species and the goal is to find out which species are represented in the sample and in which quantity. We develop a generic search method that exploits bidirectional indexes both for the pattern set and texts, and analyze the best and worst case running time of the method on worst case text. We show that finding the instance of the search method with minimum best case running time on worst case text is NP-hard. The positive result is that an instance with logarithm-factor approximation to minimum best case running time can be found in polynomial time using a bidirectional index called affix tree. We further show that affix trees can be simulated space-efficiently using bidirectional variant of compressed suffix trees.

Joint work with Simon Gog, Kalle Karhu, Juha Kärkkäinen, and Niko Välimäki


16.03.2012 - 18:08 Leena Salmela
16.03.2012 - 18:08 Leena Salmela