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

Approximation Algorithms for Sorting ?-Permutations by ?-Operations

Guilherme Henrique Santos Miranda    
Alexsandro Oliveira Alexandrino    
Carla Negri Lintzmayer and Zanoni Dias    

Resumen

Understanding how different two organisms are is one question addressed by the comparative genomics field. A well-accepted way to estimate the evolutionary distance between genomes of two organisms is finding the rearrangement distance, which is the smallest number of rearrangements needed to transform one genome into another. By representing genomes as permutations, one of them can be represented as the identity permutation, and, so, we reduce the problem of transforming one permutation into another to the problem of sorting a permutation using the minimum number of rearrangements. This work investigates the problems of sorting permutations using reversals and/or transpositions, with some additional restrictions of biological relevance. Given a value ?? ? , the problem now is how to sort a ?? ? -permutation, which is a permutation whose elements are less than ?? ? positions away from their correct places (regarding the identity), by applying the minimum number of rearrangements. Each ?? ? -rearrangement must have size, at most, ?? ? , and, when applied to a ?? ? -permutation, the result should also be a ?? ? -permutation. We present algorithms with approximation factors of ??(??2) O ( ? 2 ) , ??(??) O ( ? ) , and ??(1) O ( 1 ) for the problems of Sorting ?? ? -Permutations by ?? ? -Reversals, by ?? ? -Transpositions, and by both operations.

 Artículos similares

       
 
Ferenc Izsák and Taki Eddine Djebbar    
We propose neural-network-based algorithms for the numerical solution of boundary-value problems for the Laplace equation. Such a numerical solution is inherently mesh-free, and in the approximation process, stochastic algorithms are employed. The chief ... ver más
Revista: Algorithms

 
Levente Fazekas, Boldizsár Tüu-Szabó, László T. Kóczy, Olivér Hornyák and Károly Nehéz    
Flow-shop scheduling problems are classic examples of multi-resource and multi-operation scheduling problems where the objective is to minimize the makespan. Because of the high complexity and intractability of the problem, apart from some exceptional ca... ver más
Revista: Algorithms

 
João V. R. de Andrade, Bruno J. T. Fernandes, André R. L. C. Izídio, Nilson M. da Silva Filho and Francisco Cruz    
The opportunities for leveraging technology to enhance the efficiency of vessel port activities are vast. Applying video analytics to model and optimize certain processes offers a remarkable way to improve overall operations. Within the realm of vessel p... ver más
Revista: Algorithms

 
Liang Zhou, Weiqiang Xu, Chengqun Wang and Hsiao-Hwa Chen    
Due to its flexible deployment and high mobility of unmanned aerial vehicles (UAVs), the UAV-assisted cognitive radio (CR) network has attracted a lot of attention as one of the most promising techniques to address spectrum congestion issues in futuristi... ver más
Revista: Information

 
Bardia Rafieian, Pedro Hermosilla and Pere-Pau Vázquez    
In data science and visualization, dimensionality reduction techniques have been extensively employed for exploring large datasets. These techniques involve the transformation of high-dimensional data into reduced versions, typically in 2D, with the aim ... ver más
Revista: Applied Sciences