TY  -  
T1  - Chaining with Overlaps Revisited 
SN  -  /  
UR  - http://hdl.handle.net/10138/340722 
T3  - Leibniz International Proceedings in Informatics, LIPIcs 
A1  - Mäkinen, Veli; Sahlin, Kristoffer 
A2  - Gortz, Inge Li; Weimann, Oren 
PB  - Schloss Dagstuhl - Leibniz-Zentrum für Informatik 
Y1  - 2020 
LA  - eng 
AB  - 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 ... 
VO  -  
IS  -  
SP  -  
OP  -  
KW  - Chaining; Longest common subsequence; Maximal exact matches; Sparse dynamic programming; 113 Computer and information sciences 
N1  -   
PP  -  
ER  -