The sorting permutations problem using prefix and suffix operations
Problems of Sorting Permutations by Fragmentation-Weighted Operations
| Grant number: | 14/20738-7 |
| Support type: | Scholarships abroad - Research Internship - Doctorate (Direct) |
| Effective date (Start): | February 16, 2015 |
| Effective date (End): | August 15, 2015 |
| Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |
| Principal Investigator: | Zanoni Dias |
| Grantee: | Carla Negri Lintzmayer |
| Supervisor abroad: | Guillaume Fertin |
| Home Institution: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil |
| Local de pesquisa : | Université de Nantes, France |
| Associated to the scholarship: | 13/01172-0 - The sorting permutations problem using prefix and suffix operations, BP.DD |
Abstract One way of comparing two genomes is to compute a distance between them. One approach to do this is finding the minimum number of large scale mutations, the genome rearrangements, that occurred to transform one genome into the other. When we represent the genomes as permutations, the goal is to sort a given permutation with the minimum number of rearrangements. Reversals and transpositions are the most studied types of genome rearrangements and when they affect segments from the beginning or from the end of the genome (permutation), they are called prefix orsuffix rearrangements, respectively. In this proposal, we describe the known results regarding some problems of sorting permutations by genome rearrangements and describe our goals towards the sandwich doctorate, which are further studying thesorting problem of permutations by prefix reversals and suffix reversals. (AU) | |