Parameterized complexity analysis for the closest string with wildcards problem

DOI10.1016/J.TCS.2015.06.043MaRDI QIDQ495996zbMATH OpenOpenAlexFDO

Authors Danny Hermelin, Liat Rozenberg

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 algorithmsclosest string problemparameterized complexity

Mathematics Subject Classification ID

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

Recommendations

• Parameterized Complexity Analysis for the Closest String with Wildcards Problem
• Randomized and Parameterized Algorithms for the Closest String Problem
• Randomized fixed-parameter algorithms for the closest string problem
• scientific article; zbMATH DE number 2086391
• On the kernelization complexity of string problems

Cites work

• scientific article; zbMATH DE number 1305456 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1945152 (Why is no real title available?)
• scientific article; zbMATH DE number 1877046 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A closer look at the closest string and closest substring problem
• A dynamic programming algorithm for the \(k\)-haplotyping problem
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A linear-time algorithm for the 1-mismatch problem
• A three-string approach to the closest string problem
• An improved (and practical) parameterized algorithm for the individual haplotyping problem MFR with mate-pairs
• Closest Substring Problems with Small Distances
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Haplotype assembly from aligned weighted SNP fragments
• Integer Programming with a Fixed Number of Variables
• More efficient algorithms for closest string and substring problems
• On covering problems of codes
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the closest string and substring problems
• On the parameterized intractability of motif search problems
• Parametrized complexity theory.
• Polynomial and APX-hard cases of the individual haplotyping problem
• Reducibility among combinatorial problems

Cited in

(8)

• Combinatorial \(n\)-fold integer programming and applications
• Randomized and Parameterized Algorithms for the Closest String Problem
• Parameterized Complexity Analysis for the Closest String with Wildcards Problem
• On the parameterized complexity of clustering problems for incomplete data
• Separating sets of strings by finding matching patterns is almost always hard
• The complexity of binary matrix completion under diameter constraints
• Parameterized lower bound and inapproximability of polylogarithmic string barcoding
• Combinatorial \(n\)-fold integer programming and applications

Describes a project that uses

Uses Software

• HapCUT

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

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