1 Search Results for "Lim, Jihyuk"


Document
Algorithm Engineering for All-Pairs Suffix-Prefix Matching

Authors: Jihyuk Lim and Kunsoo Park

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)


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.

Cite as

Jihyuk Lim and Kunsoo Park. Algorithm Engineering for All-Pairs Suffix-Prefix Matching. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{lim_et_al:LIPIcs.SEA.2017.14,
  author =	{Lim, Jihyuk and Park, Kunsoo},
  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 =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.14},
  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}
}
  • Refine by Author
  • 1 Lim, Jihyuk
  • 1 Park, Kunsoo

  • Refine by Classification

  • Refine by Keyword
  • 1 DNA sequence assembly
  • 1 algorithm engineering
  • 1 all-pairs suffix-prefix matching

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail