Rearrangement Distance Problems: An Updated Survey

Author(s)

Oliveira, Andre Rodrigues ; Brito, Klairton Lima ; Alexandrino, Alexsandro Oliveira ; Siqueira, Gabriel ; Dias, Ulisses ; Dias, Zanoni

• Document type: Journal article
• Source: ACM COMPUTING SURVEYS; v. 56, n. 8, p. 27-pg., 2024-08-01.

Abstract

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. (AU)

• FAPESP's process: 13/08293-7 - CCES - Center for Computational Engineering and Sciences
• Grantee: Munir Salomao Skaf
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
• FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
• Grantee: Flávio Keidi Miyazawa
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 19/27331-3 - Sorting by genome rearrangements problems
• Grantee: André Rodrigues Oliveira
• Support Opportunities: Scholarships in Brazil - Post-Doctoral