Skip to Main content Skip to Navigation
Journal articles

Hierarchical Overlap Graph

Bastien Cazaux 1, 2 Eric Rivals 1, 2
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Given a set of finite words, the Overlap Graph (OG) is a complete weighted digraph where each word is a node and where the weight of an arc equals the length of the longest overlap of one word onto the other (Overlap is an asymmetric notion). The OG serves to assemble DNA fragments or to compute shortest superstrings, which are a compressed representation of the input. The OG requires space that is quadratic in the number of words, which limits its scalability. The Hierarchical Overlap Graph (HOG) is an alternative graph that also encodes all maximal overlaps, but uses space that is linear in the sum of the lengths of the input words. We propose the first algorithm to build the HOG in linear space for words of equal length.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01674319
Contributor : Eric Rivals <>
Submitted on : Monday, January 29, 2018 - 10:22:28 AM
Last modification on : Tuesday, March 17, 2020 - 3:27:44 AM
Long-term archiving on: : Friday, May 25, 2018 - 10:02:30 AM

File

hog-art.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Bastien Cazaux, Eric Rivals. Hierarchical Overlap Graph. Information Processing Letters, Elsevier, 2020, 155, pp.#105862. ⟨10.1016/j.ipl.2019.105862⟩. ⟨lirmm-01674319v2⟩

Share

Metrics

Record views

260

Files downloads

371