Advanced search
Start date
Betweenand

Problems of sorting permutations by Fragmentation-Weighted operations

Grant number: 17/16871-1
Support type:Scholarships in Brazil - Master
Effective date (Start): December 01, 2017
Effective date (End): February 28, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Zanoni Dias
Grantee:Alexsandro Oliveira Alexandrino
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

Calculating the evolutionary distance between species is an important problem in Computational Biology, and for this we consider sets of mutations that alter large stretches of the genome, which we call genome rearrangements. A genome is represented as a permutation of integers, where each element corresponds to a conserved block (region of high similarity between the genomes to be compared). Due to algebraic properties of permutations, the problem of transforming one genome into another is equivalent to the problem of sorting permutations by rearrangement operations. The most common approach considers that all rearrangements have the same cost, so the goal is to find a minimal sequence of rearrangements that sorts the permutation. However, studies indicate that some rearrangement operations are more likely to occur than others, making approaches in which operations have different costs more realistic. In this weighted approach, the goal is to find a sequence that sorts the permutation, such that the sum of the rearrangements' costs of this sequence is minimal. This project presents a new version for the problem of sorting permutations by weighted operations, where the cost of an operation corresponds to the amount of fragmentation that the operation causes in the permutation.

Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
ALEXANDRINO, Alexsandro Oliveira. Sorting permutations by weighted operations. 2019. Master's Dissertation.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.