Advanced search
Start date
Betweenand


Approximation algorithms for sorting by k-cuts on signed permutations

Full text
Author(s):
Oliveira, Andre Rodrigues ; Alexandrino, Alexsandro Oliveira ; Jean, Geraldine ; Fertin, Guillaume ; Dias, Ulisses ; Dias, Zanoni
Total Authors: 6
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