DOI: 10.1145/3653295 ISSN: 0360-0300

Rearrangement Distance Problems: An updated survey

Andre Rodrigues Oliveira, Klairton Lima Brito, Alexsandro Oliveira Alexandrino, Gabriel Siqueira, Ulisses Dias, Zanoni Dias
  • General Computer Science
  • Theoretical Computer Science

One of the challenges in the Comparative Genomics field is to infer how close two organisms are based on the similarities and differences between their genetic materials. Recent advances in DNA sequencing have made complete genomes increasingly available. That said, several new algorithms trying to infer the distance between two organisms based on genome rearrangements have been proposed in the literature. However, given the diversity of approaches, the diversity of genome rearrangement events, or even how each work models the genomes and what assumptions are made by each of them, finding the ideal algorithm for each situation or simply knowing the range of applicable approaches can be challenging. In this work, we review these approaches having the algorithmic and combinatorial advances since 2010 as our main focus. This survey aims to organize the recently published papers using a concise notation and to indicate the gaps filled by each of them in the literature. This makes it easier to understand what still needs to be done and what has room for enhancement.

More from our Archive