Seminár z teoretickej informatiky
Thu 12 Feb. 2015, 10:00
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.