Efficient algorithms for the longest common subsequence problem with sequential substring constraints

DOI10.1016/j.jco.2012.08.002zbMath1255.90107OpenAlexW2109822297MaRDI QIDQ1931428

Hsing-Yen Ann, Chiou-Ting Tseng, Chang-Biau Yang

Publication date: 14 January 2013

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2012.08.002

zbMATH Keywords

bioinformaticslongest common subsequenceconstrained LCSalgorithm designsequential substring

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorics on words (68R15) Combinatorial optimization (90C27) Pattern recognition, speech recognition (68T10)

Related Items (6)

Efficient merged longest common subsequence algorithms for similar sequences ⋮ Linear-space S-table algorithms for the longest common subsequence problem ⋮ An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint ⋮ Constrained sequence analysis algorithms in computational biology

This page was built for publication: Efficient algorithms for the longest common subsequence problem with sequential substring constraints