Skip to Main content Skip to Navigation
Conference papers

Efficient Construction of Hierarchical Overlap Graphs

Sung Park 1 Bastien Cazaux 2, 3 Kunsoo Park 1 Eric Rivals 2
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The hierarchical overlap graph (HOG for short) is an overlap encoding graph that efficiently represents overlaps from a given set P of n strings. A previously known algorithm constructs the HOG in O(||P || + n 2) time and O(||P || + n × min(n, max{|s| : s ∈ P })) space, where ||P || is the sum of lengths of the n strings in P. We present a new algorithm of O(||P || log n) time and O(||P ||) space to compute the HOG, which exploits the segment tree data structure. We also propose an alternative algorithm using O(||P || log n log log n) time and O(||P ||) space in the word RAM model of computation.
Document type :
Conference papers
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03014336
Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Thursday, November 19, 2020 - 1:35:41 PM
Last modification on : Wednesday, November 3, 2021 - 6:11:25 AM
Long-term archiving on: : Saturday, February 20, 2021 - 7:17:19 PM

File

Efficient_Construction_of_Hier...
Files produced by the author(s)

Identifiers

Collections

Citation

Sung Park, Bastien Cazaux, Kunsoo Park, Eric Rivals. Efficient Construction of Hierarchical Overlap Graphs. 27th International Symposium on String Processing and Information Retrieval (SPIRE), Oct 2020, Orlando, FL, United States. pp.277-290, ⟨10.1007/978-3-030-59212-7_20⟩. ⟨lirmm-03014336⟩

Share

Metrics

Record views

91

Files downloads

148