Hardness and approximation of multiple sequence alignment with column score

DOI10.1016/j.tcs.2022.12.033OpenAlexW4313478283MaRDI QIDQ2682925

Andrea Caucchiolo, Ferdinando Cicalese

Publication date: 1 February 2023

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

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

zbMATH Keywords

NP-completenessmultiple sequence alignmentcolumn score

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Algorithms for computing variants of the longest common subsequence problem
• On the longest common parameterized subsequence
• Finding similar regions in many sequences
• Compositional properties of alignments
• MSAID: multiple sequence alignment based on a measure of information discrepancy
• Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Algorithms for Computing the Longest Parameterized Common Subsequence
• The Multiple Sequence Alignment Problem in Biology
• The Complexity of Some Problems on Subsequences and Supersequences

This page was built for publication: Hardness and approximation of multiple sequence alignment with column score