Dynamic programming algorithms for the mosaic longest common subsequence problem

DOI10.1016/j.ipl.2006.11.006zbMath1187.90233OpenAlexW2144884743MaRDI QIDQ845973

Hsing-Yen Ann, Chang-Biau Yang, Kuo-Tsung Tseng, Yung-Hsing Peng, Kuo-Si Huang

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.11.006

zbMATH Keywords

design of algorithmsbioinformaticsmosaic sequence

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items

Efficient algorithms for finding interleaving relationship between sequences ⋮ The generalized definitions of the two-dimensional largest common substructure problems ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Finding the gapped longest common subsequence by incremental suffix maximum queries ⋮ BIT-PARALLEL ALGORITHMS FOR THE MERGED LONGEST COMMON SUBSEQUENCE PROBLEM ⋮ Efficient algorithms for the block edit problems ⋮ AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS ⋮ Resequencing a set of strings based on a target string

Cites Work

• Sparse LCS common substring alignment
• Geometric applications of a matrix-searching algorithm
• On the Common Substring Alignment Problem
• A linear space algorithm for computing maximal common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms on Strings, Trees and Sequences