Approximation algorithms for sorting by k-cuts on signed permutations

Andre Rodrigues Oliveira (), Alexsandro Oliveira Alexandrino (), Géraldine Jean (), Guillaume Fertin (), Ulisses Dias () and Zanoni Dias ()
Additional contact information
Andre Rodrigues Oliveira: University of Campinas
Alexsandro Oliveira Alexandrino: University of Campinas
Géraldine Jean: LS2N, UMR CNRS, Nantes University
Guillaume Fertin: LS2N, UMR CNRS, Nantes University
Ulisses Dias: University of Campinas
Zanoni Dias: University of Campinas

Journal of Combinatorial Optimization, 2023, vol. 45, issue 1, No 11, 30 pages

Abstract: 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 \ge 2$$ 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$$ k = 4 , as well as a generic approximation algorithm applicable for any $$k\ge 5$$ 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.

Keywords: Genome rearrangements; Sorting permutations; Approximation algorithms; Algorithmic complexity (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00937-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:1:d:10.1007_s10878-022-00937-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00937-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().