Comparing incomplete sequences via longest common subsequence

DOI10.1016/J.TCS.2019.09.022zbMATH Open1435.68396OpenAlexW2974309155MaRDI QIDQ2333802FDOQ2333802

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

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

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)

Cites Work

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

Cited In (3)

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

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)