1 Search Results for "Sahlin, Kristoffer"

Document
DOI: 10.4230/LIPIcs.CPM.2020.25
Chaining with Overlaps Revisited

Authors: Veli Mäkinen and Kristoffer Sahlin

Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)

Abstract
Chaining algorithms aim to form a semi-global alignment of two sequences based on a set of anchoring local alignments as input. Depending on the optimization criteria and the exact definition of a chain, there are several O(n log n) time algorithms to solve this problem optimally, where n is the number of input anchors. In this paper, we focus on a formulation allowing the anchors to overlap in a chain. This formulation was studied by Shibuya and Kurochkin (WABI 2003), but their algorithm comes with no proof of correctness. We revisit and modify their algorithm to consider a strict definition of precedence relation on anchors, adding the required derivation to convince on the correctness of the resulting algorithm that runs in O(n log² n) time on anchors formed by exact matches. With the more relaxed definition of precedence relation considered by Shibuya and Kurochkin or when anchors are non-nested such as matches of uniform length (k-mers), the algorithm takes O(n log n) time. We also establish a connection between chaining with overlaps and the widely studied longest common subsequence problem.
Cite as

Veli Mäkinen and Kristoffer Sahlin. Chaining with Overlaps Revisited. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{makinen_et_al:LIPIcs.CPM.2020.25,
  author =	{M\"{a}kinen, Veli and Sahlin, Kristoffer},
  title =	{{Chaining with Overlaps Revisited}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{25:1--25:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{G{\o}rtz, Inge Li and Weimann, Oren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.25},
  URN =		{urn:nbn:de:0030-drops-121500},
  doi =		{10.4230/LIPIcs.CPM.2020.25},
  annote =	{Keywords: Sparse Dynamic Programming, Chaining, Maximal Exact Matches, Longest Common Subsequence}
}
  • Refine by Author
  • 1 Mäkinen, Veli
  • 1 Sahlin, Kristoffer

  • Refine by Classification
  • 1 Applied computing → Genomics
  • 1 Theory of computation → Dynamic programming
  • 1 Theory of computation → Pattern matching

  • Refine by Keyword
  • 1 Chaining
  • 1 Longest Common Subsequence
  • 1 Maximal Exact Matches
  • 1 Sparse Dynamic Programming

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact