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

Tietojenkäsittelytieteen osasto

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

Abstrakti

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.

Alkuperäiskieli	englanti
Otsikko	String Processing and Information Retrieval : 27th International Symposium, SPIRE 2020 Orlando, FL, USA, October 13–15, 2020, Proceedings
Toimittajat	Christina Boucher, Sharma V. Thankachan
Sivumäärä	14
Julkaisupaikka	Cham
Kustantaja	Springer Nature Switzerland AG
Julkaisupäivä	2020
Sivut	277-290
ISBN (painettu)	978-3-030-59211-0
ISBN (elektroninen)	978-3-030-59212-7
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-030-59212-7_20
Tila	Julkaistu - 2020
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	International Symposium on String Processing and Information Retrieval - Orlando, Yhdysvallat (USA) Kesto: 13 lokak. 2020 → 15 lokak. 2020 Konferenssinumero: 27 https://www.cs.ucf.edu/spire2020/

Julkaisusarja

Nimi	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta	12303 LNCS
ISSN (painettu)	0302-9743
ISSN (elektroninen)	1611-3349

Tieteenalat

113 Tietojenkäsittely- ja informaatiotieteet

Pääsy asiakirjaan

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

Siteeraa tätä

Park, S. G., Cazaux, B., Park, K., & Rivals, E. (2020). Efficient Construction of Hierarchical Overlap Graphs. teoksessa C. Boucher, & S. V. Thankachan (Toimittajat), String Processing and Information Retrieval : 27th International Symposium, SPIRE 2020 Orlando, FL, USA, October 13–15, 2020, Proceedings (Sivut 277-290). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 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. Toimittaja / Christina Boucher ; Sharma V. Thankachan. Cham : Springer Nature Switzerland AG, 2020. Sivut 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. julkaisussa C Boucher & SV Thankachan (toim), 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), Vuosikerta 12303 LNCS, Springer Nature Switzerland AG, Cham, Sivut 277-290, International Symposium on String Processing and Information Retrieval, Orlando, Florida, Yhdysvallat (USA), 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. toim. / Christina Boucher; Sharma V. Thankachan. Cham: Springer Nature Switzerland AG, 2020. s. 277-290 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 12303 LNCS).

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

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

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. julkaisussa Boucher C, Thankachan SV, toimittajat, String Processing and Information Retrieval : 27th International Symposium, SPIRE 2020 Orlando, FL, USA, October 13–15, 2020, Proceedings. Cham: Springer Nature Switzerland AG. 2020. s. 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