Inicio  /  Algorithms  /  Vol: 14 Par: 6 (2021)  /  Artículo
ARTÍCULO
TITULO

Sorting by Multi-Cut Rearrangements

Laurent Bulteau    
Guillaume Fertin    
Géraldine Jean and Christian Komusiewicz    

Resumen

A multi-cut rearrangement of a string S is a string ??' S ' obtained from S by an operation called k-cut rearrangement, that consists of (1) cutting S at a given number k of places in S, making S the concatenated string ??1·??2·??3·?·????·????+1 X 1 · X 2 · X 3 · ? · X k · X k + 1 , where ??1 X 1 and ????+1 X k + 1 are possibly empty, and (2) rearranging the ???? X i s so as to obtain ??'=????(1)·????(2)·????(3)·?·????(??+1) S ' = X p ( 1 ) · X p ( 2 ) · X p ( 3 ) · ? · X p ( k + 1 ) , ?? p being a permutation on 1,2,?,??+1 1 , 2 , ? , k + 1 satisfying ??(1)=1 p ( 1 ) = 1 and ??(??+1)=??+1 p ( k + 1 ) = k + 1 . Given two strings S and T built on the same multiset of characters from an alphabet S S , the Sorting by Multi-Cut Rearrangements (SMCR) problem asks whether a given number l of k-cut rearrangements suffices to transform S into T. The SMCR problem generalizes several classical genomic rearrangements problems, such as Sorting by Transpositions and Sorting by Block Interchanges. It may also model chromoanagenesis, a recently discovered phenomenon consisting of massive simultaneous rearrangements. In this paper, we study the SMCR problem from an algorithmic complexity viewpoint. More precisely, we investigate its classical and parameterized complexity, as well as its approximability, in the general case or when S and T are permutations.

 Artículos similares

       
 
Amir Mohammad and Mesfin Belayneh    
The axial movement of pipe in and out of the well generates positive (surge) and negative (swab) pressures that will impact the well pressure. When the swab and surge effects cause well pressures outside the allowable operational limits, wellbore instabi... ver más
Revista: Applied Sciences

 
Cristian Minoccheri, Olivia Alge, Jonathan Gryak, Kayvan Najarian and Harm Derksen    
Over the past decades, there has been an increase of attention to adapting machine learning methods to fully exploit the higher order structure of tensorial data. One problem of great interest is tensor classification, and in particular the extension of ... ver más
Revista: Algorithms

 
Valery Bondur, Vladimir Dulov, Vladimir Kozub, Alexander Murynin, Maria Yurovskaya and Yury Yurovsky    
A method for retrieving 2D spatial spectra of sea wave elevations and slopes from high resolution (about 1 m) satellite imagery has been developed that also allows for assessing sea wave angular distributions. A validation of the suggested method was car... ver más

 
Taylor Petty, Jan Hannig, Tunde I. Huszar and Hari Iyer    
String edit distances have been used for decades in applications ranging from spelling correction and web search suggestions to DNA analysis. Most string edit distances are variations of the Levenshtein distance and consider only single-character edits. ... ver más
Revista: Algorithms

 
Matko Gluncic, Ines Vlahovic, Leo Mr?ic and Vladimir Paar    
Tandem repeats (TRs) are important components of eukaryotic genomes; they have both structural and functional roles: (i) they form essential chromosome structures such as centromeres and telomeres; (ii) they modify chromatin structure and affect transcri... ver más
Revista: Algorithms