On the computational complexity of closest genome problems

DOI10.1016/j.dam.2019.04.002zbMath1434.68195MaRDI QIDQ2295622

Vinícius Fernandes dos Santos, Celina M. Herrera de Figueiredo, Pedro Feijão, Luís Cunha, Luis Antonio B. Kowada

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

breakpoint; block-interchange; closest problem; single-cut-or-join

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

92D15: Problems related to evolution

92D20: Protein sequences, DNA sequences

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

92D10: Genetics and epigenetics