Greedy Shortest Common Superstring Approximation in Compact Space

Jarno Alanko; Tuukka Norri

doi:10.1007/978-3-319-67428-5_1

Greedy Shortest Common Superstring Approximation in Compact Space

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

Abstrakti

Given a set of strings, the shortest common superstring problem is to find the shortest possible string that contains all the input strings. The problem is NP-hard, but a lot of work has gone into designing approximation algorithms for solving the problem. We present the first time and space efficient implementation of the classic greedy heuristic which merges strings in decreasing order of overlap length. Our implementation works in O(n log σ) time and bits of space, where n is the total length of the input strings in characters, and σσ is the size of the alphabet. After index construction, a practical implementation of our algorithm uses roughly 5n log σ bits of space and reasonable time for a real dataset that consists of DNA fragments.

Alkuperäiskieli	englanti
Otsikko	String Processing and Information Retrieval : 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings
Toimittajat	Gabriele Fici, Marinella Sciortino, Rosssano Venturini
Sivumäärä	13
Julkaisupaikka	Cham
Kustantaja	Springer International Publishing AG
Julkaisupäivä	6 syysk. 2017
Sivut	1-13
ISBN (painettu)	978-3-319-67427-8
ISBN (elektroninen)	978-3-319-67428-5
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-319-67428-5_1
Tila	Julkaistu - 6 syysk. 2017
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	International Symposium on String Processing and Information Retrieval - Palermo, Italia Kesto: 26 syysk. 2017 → 29 syysk. 2017 Konferenssinumero: 24

Julkaisusarja

Nimi	Lecture Notes in Computer Science
Kustantaja	Springer International Publishing AG
Vuosikerta	10508
ISSN (painettu)	0302-9743
ISSN (elektroninen)	1161-3349

Tieteenalat

113 Tietojenkäsittely- ja informaatiotieteet

Pääsy asiakirjaan

10.1007/978-3-319-67428-5_1

1707.07727Hyväksytty kirjoittajan käsikirjoitus, 732 KBLisenssi: CC BY

Siteeraa tätä

Alanko, J., & Norri, T. (2017). Greedy Shortest Common Superstring Approximation in Compact Space. teoksessa G. Fici, M. Sciortino, & R. Venturini (Toimittajat), String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings (Sivut 1-13). (Lecture Notes in Computer Science; Vuosikerta 10508). Springer International Publishing AG. https://doi.org/10.1007/978-3-319-67428-5_1

Alanko, Jarno ; Norri, Tuukka. / Greedy Shortest Common Superstring Approximation in Compact Space. String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings. Toimittaja / Gabriele Fici ; Marinella Sciortino ; Rosssano Venturini. Cham : Springer International Publishing AG, 2017. Sivut 1-13 (Lecture Notes in Computer Science).

@inproceedings{6590e12b29b546c4ac9be25d1ff5e8da,

title = "Greedy Shortest Common Superstring Approximation in Compact Space",

abstract = "Given a set of strings, the shortest common superstring problem is to find the shortest possible string that contains all the input strings. The problem is NP-hard, but a lot of work has gone into designing approximation algorithms for solving the problem. We present the first time and space efficient implementation of the classic greedy heuristic which merges strings in decreasing order of overlap length. Our implementation works in O(n log σ) time and bits of space, where n is the total length of the input strings in characters, and σσ is the size of the alphabet. After index construction, a practical implementation of our algorithm uses roughly 5n log σ bits of space and reasonable time for a real dataset that consists of DNA fragments.",

keywords = "113 Computer and information sciences, BWT, shortest common superstring, greedy, approximation, compact",

author = "Jarno Alanko and Tuukka Norri",

year = "2017",

month = sep,

day = "6",

doi = "10.1007/978-3-319-67428-5_1",

language = "English",

isbn = "978-3-319-67427-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer International Publishing AG",

pages = "1--13",

editor = "Gabriele Fici and Marinella Sciortino and Rosssano Venturini",

booktitle = "String Processing and Information Retrieval",

address = "Switzerland",

note = "International Symposium on String Processing and Information Retrieval, SPIRE ; Conference date: 26-09-2017 Through 29-09-2017",

}

Alanko, J & Norri, T 2017, Greedy Shortest Common Superstring Approximation in Compact Space. julkaisussa G Fici, M Sciortino & R Venturini (toim), String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings. Lecture Notes in Computer Science, Vuosikerta 10508, Springer International Publishing AG, Cham, Sivut 1-13, International Symposium on String Processing and Information Retrieval, Palermo, Italia, 26/09/2017. https://doi.org/10.1007/978-3-319-67428-5_1

Greedy Shortest Common Superstring Approximation in Compact Space. / Alanko, Jarno ; Norri, Tuukka.
String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings. toim. / Gabriele Fici; Marinella Sciortino; Rosssano Venturini. Cham: Springer International Publishing AG, 2017. s. 1-13 (Lecture Notes in Computer Science; Vuosikerta 10508).

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

TY - GEN

T1 - Greedy Shortest Common Superstring Approximation in Compact Space

AU - Alanko, Jarno

AU - Norri, Tuukka

N1 - Conference code: 24

PY - 2017/9/6

Y1 - 2017/9/6

N2 - Given a set of strings, the shortest common superstring problem is to find the shortest possible string that contains all the input strings. The problem is NP-hard, but a lot of work has gone into designing approximation algorithms for solving the problem. We present the first time and space efficient implementation of the classic greedy heuristic which merges strings in decreasing order of overlap length. Our implementation works in O(n log σ) time and bits of space, where n is the total length of the input strings in characters, and σσ is the size of the alphabet. After index construction, a practical implementation of our algorithm uses roughly 5n log σ bits of space and reasonable time for a real dataset that consists of DNA fragments.

AB - Given a set of strings, the shortest common superstring problem is to find the shortest possible string that contains all the input strings. The problem is NP-hard, but a lot of work has gone into designing approximation algorithms for solving the problem. We present the first time and space efficient implementation of the classic greedy heuristic which merges strings in decreasing order of overlap length. Our implementation works in O(n log σ) time and bits of space, where n is the total length of the input strings in characters, and σσ is the size of the alphabet. After index construction, a practical implementation of our algorithm uses roughly 5n log σ bits of space and reasonable time for a real dataset that consists of DNA fragments.

KW - 113 Computer and information sciences

KW - BWT

KW - shortest common superstring

KW - greedy

KW - approximation

KW - compact

U2 - 10.1007/978-3-319-67428-5_1

DO - 10.1007/978-3-319-67428-5_1

M3 - Conference contribution

SN - 978-3-319-67427-8

T3 - Lecture Notes in Computer Science

SP - 1

EP - 13

BT - String Processing and Information Retrieval

A2 - Fici, Gabriele

A2 - Sciortino, Marinella

A2 - Venturini, Rosssano

PB - Springer International Publishing AG

CY - Cham

T2 - International Symposium on String Processing and Information Retrieval

Y2 - 26 September 2017 through 29 September 2017

ER -

Alanko J , Norri T. Greedy Shortest Common Superstring Approximation in Compact Space. julkaisussa Fici G, Sciortino M, Venturini R, toimittajat, String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings. Cham: Springer International Publishing AG. 2017. s. 1-13. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-67428-5_1