### Abstract

Original language | English |
---|---|

Title of host publication | String Processing and Information Retrieval : 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings |

Editors | Gabriele Fici, Marinella Sciortino, Rosssano Venturini |

Number of pages | 13 |

Place of Publication | Cham |

Publisher | Springer International Publishing AG |

Publication date | 6 Sep 2017 |

Pages | 1-13 |

ISBN (Print) | 978-3-319-67427-8 |

ISBN (Electronic) | 978-3-319-67428-5 |

DOIs | |

Publication status | Published - 6 Sep 2017 |

MoE publication type | A4 Article in conference proceedings |

Event | International Symposium on String Processing and Information Retrieval - Palermo, Italy Duration: 26 Sep 2017 → 29 Sep 2017 Conference number: 24 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer International Publishing AG |

Volume | 10508 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1161-3349 |

### Fields of Science

- 113 Computer and information sciences
- BWT
- shortest common superstring
- greedy
- approximation
- compact

### Cite this

*String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings*(pp. 1-13). (Lecture Notes in Computer Science; Vol. 10508). Cham: Springer International Publishing AG. https://doi.org/10.1007/978-3-319-67428-5_1

}

*String Processing and Information Retrieval: 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings.*Lecture Notes in Computer Science, vol. 10508, Springer International Publishing AG, Cham, pp. 1-13, International Symposium on String Processing and Information Retrieval, Palermo, Italy, 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.

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

TY - GEN

T1 - Greedy Shortest Common Superstring Approximation in Compact Space

AU - Alanko, Jarno

AU - Norri, Tuukka

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

ER -