Seminár z teoretickej informatiky

Thu 12 Feb. 2015, 10:00
M 213

Title: Efficient index-based filtering for NGS read mapping and suffix/prefix overlap computation
Speaker: Gregory Kucherov, CNRS/LIGM Marne-la-Vallée, France

We present two related algorithms for two different problems. The
first problem is the classical read mapping problem where we
assume a constant number of errors is allowed in each read
alignment. The second problem is the one of efficiently
retrieving reads overlapping with a given query sequence. For
both problems, we assume that the reads are stored in a
space-efficient indexing structure such as FM-index, and we
propose an efficient search strategy based on partitioning the
query read.

The results are joint with D.Tsur (Ben-Gurion University) and
K.Salkhov (LIGM/Moscow State University) and have been presented
to CPM2014 and SPIRE2014 conferences.