Approximation algorithms for sorting by k-cuts on signed permutations

Author(s)

Oliveira, Andre Rodrigues ; Alexandrino, Alexsandro Oliveira ; Jean, Geraldine ; Fertin, Guillaume ; Dias, Ulisses ; Dias, Zanoni

• Document type: Journal article
• Source: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 45, n. 1, p. 30-pg., 2023-01-01.

Abstract

Sorting by Genome Rearrangements is a classic problem in Computational Biology. Several models have been considered so far, each of them defines how a genome is modeled (for example, permutations when assuming no duplicated genes, strings if duplicated genes are allowed, and/or use of signs on each element when gene orientation is known), and which rearrangements are allowed. Recently, a new problem, called Sorting by Multi-Cut Rearrangements, was proposed. It uses the k-cut rearrangement which cuts a permutation (or a string) at k >= 2 places and rearranges the generated blocks to obtain a new permutation (or string) of same size. This new rearrangement may model chromoanagenesis, a phenomenon consisting of massive simultaneous rearrangements. Similarly as the Double-Cut-and-Join, this new rearrangement also generalizes several genome rearrangements such as reversals, transpositions, revrevs, transreversals, and block-interchanges. In this paper, we extend a previous work based on unsigned permutations and strings to signed permutations. We show the complexity of this problem for different values of k, and that the approximation algorithm proposed for unsigned permutations with any value of k can be adapted to signed permutations. We also show a 1.5-approximation algorithm for the specific case k = 4, as well as a generic approximation algorithm applicable for any k >= 5, that always reaches constant ratio. The latter makes use of the cycle graph, a well-known structure in genome rearrangements. We implemented and tested the proposed algorithms on simulated data. (AU)

• FAPESP's process: 19/27331-3 - Sorting by genome rearrangements problems
• Grantee: André Rodrigues Oliveira
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• 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