Efficient Construction of Hierarchical Overlap Graphs

Sung Gwan Park; Bastien Cazaux; Kunsoo Park; Eric Rivals

doi:10.1007/978-3-030-59212-7_20

Efficient Construction of Hierarchical Overlap Graphs

Sung Gwan Park, Bastien Cazaux, Kunsoo Park, Eric Rivals

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

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 time and space, where is the sum of lengths of the n strings in P. We present a new algorithm of time and space to compute the HOG, which exploits the segment tree data structure. We also propose an alternative algorithm using time and space in the word RAM model of computation.

Original language	English
Title of host publication	String Processing and Information Retrieval : 27th International Symposium, SPIRE 2020 Orlando, FL, USA, October 13–15, 2020, Proceedings
Editors	Christina Boucher, Sharma V. Thankachan
Number of pages	14
Place of Publication	Cham
Publisher	Springer Nature Switzerland AG
Publication date	2020
Pages	277-290
ISBN (Print)	978-3-030-59211-0
ISBN (Electronic)	978-3-030-59212-7
DOIs	https://doi.org/10.1007/978-3-030-59212-7_20
Publication status	Published - 2020
MoE publication type	A4 Article in conference proceedings
Event	International Symposium on String Processing and Information Retrieval - Orlando, United States Duration: 13 Oct 2020 → 15 Oct 2020 Conference number: 27 https://www.cs.ucf.edu/spire2020/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12303 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Fields of Science

Hierarchical overlap graph
Segment tree
Word RAM model
113 Computer and information sciences

Access to Document

10.1007/978-3-030-59212-7_20

Cite this

Park, S. G., Cazaux, B., Park, K., & Rivals, E. (2020). Efficient Construction of Hierarchical Overlap Graphs. In C. Boucher, & S. V. Thankachan (Eds.), String Processing and Information Retrieval : 27th International Symposium, SPIRE 2020 Orlando, FL, USA, October 13–15, 2020, Proceedings (pp. 277-290). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12303 LNCS). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-030-59212-7_20

Park, Sung Gwan ; Cazaux, Bastien ; Park, Kunsoo et al. / Efficient Construction of Hierarchical Overlap Graphs. String Processing and Information Retrieval : 27th International Symposium, SPIRE 2020 Orlando, FL, USA, October 13–15, 2020, Proceedings. editor / Christina Boucher ; Sharma V. Thankachan. Cham : Springer Nature Switzerland AG, 2020. pp. 277-290 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{bf4861227a094008817414f813b9a629,

title = "Efficient Construction of Hierarchical Overlap Graphs",

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 time and space, where is the sum of lengths of the n strings in P. We present a new algorithm of time and space to compute the HOG, which exploits the segment tree data structure. We also propose an alternative algorithm using time and space in the word RAM model of computation.",

keywords = "Hierarchical overlap graph, Segment tree, Word RAM model, 113 Computer and information sciences",

author = "Park, \{Sung Gwan\} and Bastien Cazaux and Kunsoo Park and Eric Rivals",

year = "2020",

doi = "10.1007/978-3-030-59212-7\_20",

language = "English",

isbn = "978-3-030-59211-0",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature Switzerland AG",

pages = "277--290",

editor = "Christina Boucher and Thankachan, \{Sharma V.\}",

booktitle = "String Processing and Information Retrieval",

address = "Switzerland",

note = "International Symposium on String Processing and Information Retrieval ; Conference date: 13-10-2020 Through 15-10-2020",

url = "https://www.cs.ucf.edu/spire2020/",

}

Park, SG, Cazaux, B, Park, K & Rivals, E 2020, Efficient Construction of Hierarchical Overlap Graphs. in C Boucher & SV Thankachan (eds), String Processing and Information Retrieval : 27th International Symposium, SPIRE 2020 Orlando, FL, USA, October 13–15, 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12303 LNCS, Springer Nature Switzerland AG, Cham, pp. 277-290, International Symposium on String Processing and Information Retrieval, Orlando, Florida, United States, 13/10/2020. https://doi.org/10.1007/978-3-030-59212-7_20

Efficient Construction of Hierarchical Overlap Graphs. / Park, Sung Gwan; Cazaux, Bastien; Park, Kunsoo et al.
String Processing and Information Retrieval : 27th International Symposium, SPIRE 2020 Orlando, FL, USA, October 13–15, 2020, Proceedings. ed. / Christina Boucher; Sharma V. Thankachan. Cham: Springer Nature Switzerland AG, 2020. p. 277-290 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12303 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Efficient Construction of Hierarchical Overlap Graphs

AU - Park, Sung Gwan

AU - Cazaux, Bastien

AU - Park, Kunsoo

AU - Rivals, Eric

N1 - Conference code: 27

PY - 2020

Y1 - 2020

N2 - 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 time and space, where is the sum of lengths of the n strings in P. We present a new algorithm of time and space to compute the HOG, which exploits the segment tree data structure. We also propose an alternative algorithm using time and space in the word RAM model of computation.

AB - 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 time and space, where is the sum of lengths of the n strings in P. We present a new algorithm of time and space to compute the HOG, which exploits the segment tree data structure. We also propose an alternative algorithm using time and space in the word RAM model of computation.

KW - Hierarchical overlap graph

KW - Segment tree

KW - Word RAM model

KW - 113 Computer and information sciences

UR - https://www.scopus.com/pages/publications/85092094970

U2 - 10.1007/978-3-030-59212-7_20

DO - 10.1007/978-3-030-59212-7_20

M3 - Conference contribution

AN - SCOPUS:85092094970

SN - 978-3-030-59211-0

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 277

EP - 290

BT - String Processing and Information Retrieval

A2 - Boucher, Christina

A2 - Thankachan, Sharma V.

PB - Springer Nature Switzerland AG

CY - Cham

T2 - International Symposium on String Processing and Information Retrieval

Y2 - 13 October 2020 through 15 October 2020

ER -

Park SG, Cazaux B, Park K, Rivals E. Efficient Construction of Hierarchical Overlap Graphs. In Boucher C, Thankachan SV, editors, String Processing and Information Retrieval : 27th International Symposium, SPIRE 2020 Orlando, FL, USA, October 13–15, 2020, Proceedings. Cham: Springer Nature Switzerland AG. 2020. p. 277-290. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-59212-7_20

Efficient Construction of Hierarchical Overlap Graphs

Abstract

Publication series

Fields of Science

Access to Document

Other files and links

Cite this