Constrained Longest Common Subsequence Computing Algorithms in Practice
Sebastian Deorowicz ; Joanna Obstój
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
The problem of finding a constrained longest common subsequence (CLCS) for the sequences A and B with respect to sequence P was introduced recently. Its goal is to find a longest subsequence C of A and B such that P is a subsequence of C. There are several algorithms solving the CLCS problem, but there is no real experimental comparison of them. The paper has two aims. Firstly, we propose an improvement to the algorithms by Chin et al. and Deorowicz based on an entry-exit points technique by He and Arslan. Secondly, we compare experimentally the existing algorithms for solving the CLCS problem.
Publié le : 2012-01-26
Classification:  Longerst common subsequence; constrained longest common subsdequence; sparse dynamic programming; string matching; sequence alignment 
@article{cai92,
     author = {Sebastian Deorowicz and Joanna Obst\'oj},
     title = {Constrained Longest Common Subsequence Computing Algorithms in Practice},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai92}
}

Sebastian Deorowicz; Joanna Obstój. Constrained Longest Common Subsequence Computing Algorithms in Practice. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai92/