2024-08-01

# Approximate suffix-prefix dictionary queries

## Publication

### Publication

*Presented at the 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024 (August 2024), Bratislava, Slovakia*

In the all-pairs suffix-prefix (APSP) problem [Gusfield et al., Inf. Process. Lett. 1992], we are given a dictionary R of r strings, S1, . . ., Sr, of total length n, and we are asked to find the length SPLi,j of the longest string that is both a suffix of Si and a prefix of Sj, for all i, j ∈ [1 . . r]. APSP is a classic problem in string algorithms with applications in bioinformatics, especially in sequence assembly. Since r = |R| is typically very large in real-world applications, considering all r2 pairs of strings explicitly is prohibitive. This is when the data structure variant of APSP makes sense; in the same spirit as distance oracles computing shortest paths between any two vertices given online. We show how to quickly locate k-approximate matches (under the Hamming or the edit distance) in R using a version of the k-errata tree [Cole et al., STOC 2004] that we introduce. Let SPLki,j be the length of the longest suffix of Si that is at distance at most k from a prefix of Sj. In particular, for any k = O(1), we show an O(nlogk n)-sized data structure to support the following queries: One-to-Onek(i, j): output SPLki,j in O(logk nlog log n) time. Reportk(i, d): output all j ∈ [1 . . r], such that SPLki,j ≥ d, in O(logk n(log n/log log n + output)) time, where output denotes the size of the output. In fact, our algorithms work for any value of k not just for k = O(1), but the formulas bounding the complexities get much more complicated for larger values of k.

Additional Metadata | |
---|---|

, , , | |

doi.org/10.4230/LIPIcs.MFCS.2024.85 | |

Leibniz International Proceedings in Informatics (LIPIcs) | |

Pan-genome Graph Algorithms and Data Integration , Algorithms for PAngenome Computational Analysis | |

49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024 | |

, | |

Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |

Zuba, W., Loukides, G., Pissis, S., & Thankachan, S. (2024). Approximate suffix-prefix dictionary queries. In Proceedings of the 49th International Symposium on the Mathematical Foundations of Computer Science, MFCS 2024 (pp. 85:1–85:18). doi:10.4230/LIPIcs.MFCS.2024.85 |