Parameterized complexity analysis for the closest string with wildcards problem

DOI10.1016/j.tcs.2015.06.043zbMath1329.68143OpenAlexW2180648128MaRDI QIDQ495996

Liat Rozenberg, Danny Hermelin

Publication date: 16 September 2015

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

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

zbMATH Keywords

computational biologyfixed-parameter algorithmsparameterized complexityclosest string problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items (5)

The complexity of binary matrix completion under diameter constraints ⋮ On the parameterized complexity of clustering problems for incomplete data ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Separating sets of strings by finding matching patterns is almost always hard ⋮ Unnamed Item

Uses Software

• HapCUT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A three-string approach to the closest string problem
• On covering problems of codes
• On the parameterized intractability of motif search problems
• An improved (and practical) parameterized algorithm for the individual haplotyping problem MFR with mate-pairs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Polynomial and APX-hard cases of the individual haplotyping problem
• A dynamic programming algorithm for the \(k\)-haplotyping problem
• Parametrized complexity theory.
• Haplotype assembly from aligned weighted SNP fragments
• Integer Programming with a Fixed Number of Variables
• On the closest string and substring problems
• Closest Substring Problems with Small Distances
• More Efficient Algorithms for Closest String and Substring Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Reducibility among Combinatorial Problems
• A linear-time algorithm for the 1-mismatch problem
• A Closer Look at the Closest String and Closest Substring Problem
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems

This page was built for publication: Parameterized complexity analysis for the closest string with wildcards problem