Hardness results for the center and median string problems under the weighted and unweighted edit distances

DOI10.1016/j.jda.2004.08.015zbMath1101.68709OpenAlexW2084313588MaRDI QIDQ2569417

François Nicolas, Eric Rivals

Publication date: 27 October 2005

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2004.08.015

zbMATH Keywords

NP-completemultiple alignmentparameterized complexityLCStree alignmentconcensus string

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Pattern recognition, speech recognition (68T10) Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

On the role of metaheuristic optimization in bioinformatics ⋮ Matching patterns with variables under edit distance ⋮ Learning the Language of Biological Sequences ⋮ Exact mean computation in dynamic time warping spaces ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Listing Center Strings Under the Edit Distance Metric ⋮ An efficient approach for the rank aggregation problem ⋮ Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The consensus string problem for a metric is NP-complete
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Distinguishing string selection problems.
• Finding similar regions in many sequences
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Approximation algorithms for tree alignment with a given phylogeny
• Topology of strings: median string is NP-complete
• Finding similar regions in many strings
• On the closest string and substring problems
• Complexities of the Centre and Median String Problems
• Minimal Mutation Trees of Sequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms on Strings, Trees and Sequences
• Improved Approximation Algorithms for Tree Alignment
• The String-to-String Correction Problem

This page was built for publication: Hardness results for the center and median string problems under the weighted and unweighted edit distances