On the computational complexity of closest genome problems

DOI10.1016/J.DAM.2019.04.002MaRDI QIDQ2295622zbMATH OpenOpenAlexFDO

Authors Luís Felipe Ignácio Cunha, Pedro Feijão, Vinícius F. dos Santos, Luis Antonio B. Kowada, Celina M. H. de Figueiredo

Publication date 14 February 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2019.04.002

zbMATH Keywords

block-interchangebreakpointclosest problemsingle-cut-or-join

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Genetics and epigenetics (92D10) Problems related to evolution (92D15) Protein sequences, DNA sequences (92D20)

Recommendations

• The transposition median problem is NP-complete
• On the complexity and approximation of syntenic distance
• Multiple genome rearrangement by swaps and by element duplications
• On the complexity of unsigned translocation distance
• The complexity of calculating exemplar distances

Cites work

• Advancing the transposition distance and diameter through lonely permutations
• Combinatorics of genome rearrangements.
• Distinguishing string selection problems.
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• scientific article; zbMATH DE number 16300 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• Medians of an odd number of permutations
• Multiple genome rearrangement by swaps and by element duplications
• On shortest disjoint paths in planar graphs
• Sorting by Transpositions
• Sorting permutations by block-interchanges
• The reversal median problem
• The transposition median problem is NP-complete

Cited in

(7)

• The computational complexity of calculating partition functions of optimal medians with Hamming distance
• Multiple genome rearrangement by swaps and by element duplications
• Bacterial phylogeny in the Cayley graph
• scientific article; zbMATH DE number 7651113 (Why is no real title available?)
• Short block-move-CPP is \textsf{NP}-complete
• On the complexity of the median and closest permutation problems
• On the complexity of finding central configurations of the graph-generalized ( n^2 - 1 )-puzzle

This page was built for publication: On the computational complexity of closest genome problems

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