Skip to Main content Skip to Navigation
Conference papers

Improved Filters for the Approximate Suffix-Prefix Overlap Problem

Abstract : Computing suffix-prefix overlaps for a large collection of strings is a fundamental building block for the analysis of genomic next-generation 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 Com-putation, 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01086208
Contributor : Admin Ligm Connect in order to contact the contributor
Submitted on : Sunday, November 23, 2014 - 9:52:20 AM
Last modification on : Tuesday, October 19, 2021 - 11:26:19 AM
Long-term archiving on: : Tuesday, February 24, 2015 - 10:24:35 AM

File

Kucherov-Tsur-overlaps.pdf
Files produced by the author(s)

Identifiers

`

Citation

Gregory Kucherov, Dekel Tsur. Improved Filters for the Approximate Suffix-Prefix Overlap Problem. SPIRE 2014, Oct 2014, Ouro Preto, Brazil. pp.139-148, ⟨10.1007/978-3-319-11918-2_14⟩. ⟨hal-01086208⟩

Share

Metrics

Record views

337

Files downloads

400