Sorting by Transpositions Is Difficult

DOI10.1007/978-3-642-22006-7_55zbMath1334.68085arXiv1011.1157MaRDI QIDQ3012840

Irena Rusu, Guillaume Fertin, Laurent Bulteau

Publication date: 6 July 2011

Published in: SIAM Journal on Discrete Mathematics, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.1157

zbMATH Keywords

computational complexity; NP-hard; comparative genomics; sorting permutations; evolutionary distance; transposition distance; theoretical aspects of computational biology; sorting by transpositions problem

Mathematics Subject Classification ID

68P10: Searching and sorting

92D15: Problems related to evolution

68R05: Combinatorics in computer science

05A05: Permutations, words, matrices

92C40: Biochemistry, molecular biology

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

92D10: Genetics and epigenetics