You are not logged in |
Pattern matching on weighted sequences
- Speaker(s)
- Jakub Radoszewski
- Affiliation
- University of Warsaw
- Date
- Oct. 13, 2016, 12:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Algorithms
Abstract:
In a weighted sequence, for every position of the sequence and every
letter of the alphabet, a probability of occurrence of this letter at
this position is specified. Sequences of this type, also called position
weight matrices (PWM), are commonly used to represent imprecise or
uncertain data, especially in molecular biology. During the talk I will present efficient algorithms for the pattern matching problem on weighted sequences. We
will consider the variants when the pattern, the text, and both the
pattern and the text are weighted and also an indexing variant of the
problem, all under a specified probability threshold 1/z. We will also
explore connections between pattern matching on weighted sequences and
the problems of profile matching and multichoice knapsack.
