Improved filters for the approximate suffix-prefix overlap problem

Gregory Kucherov, Dekel Tsur

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Citations (Scopus)

Abstract

Computing suffix-prefix overlaps for a large collection of strings is a fundamental building block for the analysis of genomic nextgeneration sequencing data. The approximate suffix-prefix overlap problem is to find all pairs of strings from a given set such that a prefix of one string is similar to a suffix of the other. Välimäki et al. (Information and Computation, 2012) gave a solution to this problem based on suffix filters. In this work, we propose two improvements to the method of Välimäki et al. that reduce the running time of the computation.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Proceedings
EditorsEdleno Moura, Maxime Crochemore
PublisherSpringer Verlag
Pages139-148
Number of pages10
ISBN (Electronic)9783319119175
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event21st International Symposium on String Processing and Information Retrieval, SPIRE 2014 - Ouro Preto, Brazil
Duration: 20 Oct 201422 Oct 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8799
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Symposium on String Processing and Information Retrieval, SPIRE 2014
Country/TerritoryBrazil
CityOuro Preto
Period20/10/1422/10/14

Fingerprint

Dive into the research topics of 'Improved filters for the approximate suffix-prefix overlap problem'. Together they form a unique fingerprint.

Cite this