Efficient algorithms for finding interleaving relationship between sequences

DOI10.1016/j.ipl.2007.08.028zbMath1184.68603MaRDI QIDQ2380070

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

Publication date: 24 March 2010

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

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

zbMATH Keywords

dynamic programming; design of algorithms; bioinformatics; longest common subsequence; merged sequence

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

90C39: Dynamic programming

Related Items

BIT-PARALLEL ALGORITHMS FOR THE MERGED LONGEST COMMON SUBSEQUENCE PROBLEM, AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS, New tabulation and sparse dynamic programming based techniques for sequence similarity problems, Efficient algorithms for the block edit problems, Efficient merged longest common subsequence algorithms for similar sequences, Finding the gapped longest common subsequence by incremental suffix maximum queries

Cites Work

• A fast algorithm for computing a longest common increasing subsequence
• Dynamic programming algorithms for the mosaic longest common subsequence problem
• Sparse LCS common substring alignment
• Geometric applications of a matrix-searching algorithm
• A simple algorithm for the constrained sequence problems
• On the Common Substring Alignment Problem
• A linear space algorithm for computing maximal common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Algorithms on Strings, Trees and Sequences
• Sparse Dynamic Programming for Longest Common Subsequence from Fragments
• Combinatorial Pattern Matching