Pattern matching on weighted sequences

Prelegent(ci)

Jakub Radoszewski

Afiliacja

University of Warsaw

Termin

13 października 2016 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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.

---