Chaining with Overlaps Revisited

Show simple item record

dc.contributor.author Mäkinen, Veli
dc.contributor.author Sahlin, Kristoffer
dc.contributor.editor Gortz, Inge Li
dc.contributor.editor Weimann, Oren
dc.date.accessioned 2022-02-21T17:45:02Z
dc.date.available 2022-02-21T17:45:02Z
dc.date.issued 2020-06-01
dc.identifier.citation Mäkinen , V & Sahlin , K 2020 , Chaining with Overlaps Revisited . in I L Gortz & O Weimann (eds) , 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020 . , 25 , Leibniz International Proceedings in Informatics, LIPIcs , vol. 161 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , Dagstuhl , Annual Symposium on Combinatorial Pattern Matching , Copenhagen , Denmark , 17/06/2020 . https://doi.org/10.4230/LIPIcs.CPM.2020.25
dc.identifier.citation conference
dc.identifier.other PURE: 174382848
dc.identifier.other PURE UUID: d1fe5748-c13d-44b6-b786-0e00bdb24637
dc.identifier.other Scopus: 85088396190
dc.identifier.other ORCID: /0000-0003-4454-1493/work/108864464
dc.identifier.uri http://hdl.handle.net/10138/340722
dc.description.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 log2 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. 2012 ACM Subject Classification Theory of computation ! Pattern matching; Theory of computation ! Dynamic programming; Applied computing ! Genomics. en
dc.format.extent 12
dc.language.iso eng
dc.publisher Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.relation.ispartof 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020
dc.relation.ispartofseries Leibniz International Proceedings in Informatics, LIPIcs
dc.relation.isversionof 978-3-95977-149-8
dc.rights cc_by
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject Chaining
dc.subject Longest common subsequence
dc.subject Maximal exact matches
dc.subject Sparse dynamic programming
dc.subject 113 Computer and information sciences
dc.title Chaining with Overlaps Revisited en
dc.type Conference contribution
dc.contributor.organization Department of Computer Science
dc.contributor.organization Genome-scale Algorithmics research group / Veli Mäkinen
dc.contributor.organization Helsinki Institute for Information Technology
dc.contributor.organization Algorithmic Bioinformatics
dc.contributor.organization Bioinformatics
dc.description.reviewstatus Peer reviewed
dc.relation.doi https://doi.org/10.4230/LIPIcs.CPM.2020.25
dc.relation.issn 1868-8969
dc.rights.accesslevel openAccess
dc.type.version publishedVersion

Files in this item

Total number of downloads: Loading...

Files Size Format View
LIPIcs_CPM_2020_25.pdf 491.8Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record