Comparing incomplete sequences via longest common subsequence

DOI10.1016/J.TCS.2019.09.022MaRDI QIDQ2333802zbMATHOpenAlexFDO

Authors Mauro Castelli, Riccardo Dondi, Italo Zoppis, Giancarlo Mauri

Publication date 13 November 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.09.022

zbMATH Keywords

computational complexityapproximation algorithmsfixed-parameter algorithmslongest common subsequencestring algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• The longest filled common subsequence problem
• Fixed-parameter algorithms for scaffold filling
• Fixed-parameter algorithms for scaffold filling
• An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies
• Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 7203332 (Why is no real title available?)
• A branch-and-cut approach to the repetition-free longest common subsequence problem
• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Color-coding
• Constrained LCS: Hardness and Approximation
• Fixed-parameter algorithms for scaffold filling
• Genomic Scaffold Filling: A Progress Report
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• On the parameterized complexity of the repetition free longest common subsequence problem
• Repetition-free longest common subsequence
• Some APX-completeness results for cubic graphs
• The constrained longest common subsequence problem
• The longest filled common subsequence problem
• Variants of constrained longest common subsequence

Cited in

(3)

• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Polynomial-time equivalences and refined algorithms for longest common subsequence variants
• The longest run subsequence problem

This page was built for publication: Comparing incomplete sequences via longest common subsequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2333802)