Advanced search
Start date
Betweenand

Sorting permutations by prefix and suffix operations

Grant number: 14/07301-9
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): July 01, 2014
Effective date (End): December 31, 2014
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Zanoni Dias
Grantee:Carolina de Senne Garcia
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

Rearrangements are evolutionary events which change large parts of the genome without removing or inserting new genes. Among rearrangements, reversals and transpositions are the most studied. The importance of this study lies in the fact that we can compare two genomes considering scenarios that involve the transformation of one into the other by a series of rearrangements. This comparison is related to the evolutionary distance between genomes since, by the principle of parsimony, it is reasonable to assume that this distance is given by the minimal sequence of rearrangements required to perform this transformation. In Computational Biology, permutations are commonly used to represent gene sequences and, when comparing two permutations, if we consider that one of them is the identity, the problem turns out to be sorting the other. In this research project, we intend to study the sorting of permutations by reversals and transpositions in their versions of prefix and suffix, that is, by operations which involve segments of the beginning and of the end of the permutation. Such problems are relatively new and there are few known results regarding them. This proposal presents the main necessary concepts and definitions for the study of genome rearrangements, as well as the objectives of our work, which includes researching classes of permutations for which it is possible to determine the exact sorting distance.