Efficient Construction of Hierarchical Overlap Graphs
Résumé
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.
Domaines
Bio-informatique [q-bio.QM]
Fichier principal
Efficient_Construction_of_Hierarchical_Overlap_Graphs(1).pdf (591 Ko)
Télécharger le fichier
Origine | Fichiers produits par l'(les) auteur(s) |
---|
Loading...