Chaining with Overlaps Revisited

Näytä kaikki kuvailutiedot



Pysyväisosoite

http://hdl.handle.net/10138/340722

Lähdeviite

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

Julkaisun nimi: Chaining with Overlaps Revisited
Tekijä: Mäkinen, Veli; Sahlin, Kristoffer
Muu tekijä: Gortz, Inge Li
Weimann, Oren
Tekijän organisaatio: Department of Computer Science
Genome-scale Algorithmics research group / Veli Mäkinen
Helsinki Institute for Information Technology
Algorithmic Bioinformatics
Bioinformatics
Julkaisija: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Päiväys: 2020-06-01
Kieli: eng
Sivumäärä: 12
Kuuluu julkaisusarjaan: 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020
Kuuluu julkaisusarjaan: Leibniz International Proceedings in Informatics, LIPIcs
ISBN: 978-3-95977-149-8
ISSN: 1868-8969
DOI-tunniste: https://doi.org/10.4230/LIPIcs.CPM.2020.25
URI: http://hdl.handle.net/10138/340722
Tiivistelmä: 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.
Avainsanat: Chaining
Longest common subsequence
Maximal exact matches
Sparse dynamic programming
113 Computer and information sciences
Vertaisarvioitu: Kyllä
Tekijänoikeustiedot: cc_by
Pääsyrajoitteet: openAccess
Rinnakkaistallennettu versio: publishedVersion


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
LIPIcs_CPM_2020_25.pdf 491.8KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot