License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.14
URN: urn:nbn:de:0030-drops-76174
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7617/
Go to the corresponding LIPIcs Volume Portal

Lim, Jihyuk ; Park, Kunsoo

Algorithm Engineering for All-Pairs Suffix-Prefix Matching

pdf-format:
LIPIcs-SEA-2017-14.pdf (0.7 MB)

Abstract

All-pairs suffix-prefix matching is an important part of DNA sequence assembly where it is the most time-consuming part of the whole assembly. Although there are algorithms for all-pairs suffix-prefix matching which are optimal in the asymptotic time complexity, they are slower than SOF and Readjoiner which are state-of-the-art algorithms used in practice. In this paper we present an algorithm for all-pairs suffix-prefix matching that uses a simple data structure for storing input strings and advanced algorithmic techniques for matching, which together lead to fast running time in practice. Our algorithm is 14 times faster than SOF and 18 times faster than Readjoiner on average in real datasets and random datasets.

BibTeX - Entry

@InProceedings{lim_et_al:LIPIcs:2017:7617,
  author =	{Jihyuk Lim and Kunsoo Park},
  title =	{{Algorithm Engineering for All-Pairs Suffix-Prefix Matching}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7617},
  URN =		{urn:nbn:de:0030-drops-76174},
  doi =		{10.4230/LIPIcs.SEA.2017.14},
  annote =	{Keywords: all-pairs suffix-prefix matching, algorithm engineering, DNA sequence assembly}
}

Keywords: all-pairs suffix-prefix matching, algorithm engineering, DNA sequence assembly
Collection: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 07.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI