Problems of sorting permutations by fragmentation-weighted operations
The sorting permutations problem using prefix and suffix operations
Sorting permutations by prefix reversals and suffix reversals
Grant number: | 14/04718-6 |
Support Opportunities: | Scholarships in Brazil - Doctorate |
Start date: | September 01, 2014 |
End date: | September 30, 2015 |
Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |
Agreement: | Coordination of Improvement of Higher Education Personnel (CAPES) |
Principal Investigator: | Zanoni Dias |
Grantee: | Gustavo Rodrigues Galvão |
Host Institution: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil |
Abstract During evolution, global mutations may modify the gene order in a genome and such mutations are called rearrangement events. In Genome Rearrangements, we estimate the evolutionary distance between two genomes by computing the rearrangement distance between them, which is the length of the shortest sequence of rearrangement events that transforms one genome into the other. Representing genomes as permutations, in which genes appear as elements, the rearrangement distance can be obtained by solving the combinatorial problem of sorting a permutation using a minimum number of rearrangement events. This problem is referred to as Rearrangement Sorting Problem and varies accordingly to the types of rearrangement events considered. In this doctorate, we focus on two types of rearrangement events: reversals and transpositions. Variants of Rearrangement Sorting Problem involving these events have been shown to be difficult to solve optimally, therefore most of the proposed algorithms are approximations. Our proposal is to study some of these variants, trying to develop approximate or heuristic algorithms that outperform the existing ones. (AU) | |
News published in Agência FAPESP Newsletter about the scholarship: | |
More itemsLess items | |
TITULO | |
Articles published in other media outlets ( ): | |
More itemsLess items | |
VEICULO: TITULO (DATA) | |
VEICULO: TITULO (DATA) | |