Advanced search
Start date

Algorithms for rearrangement sorting problem

Grant number: 14/04718-6
Support type:Scholarships in Brazil - Doctorate
Effective date (Start): September 01, 2014
Effective date (End): September 30, 2015
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Cooperation agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
Principal researcher:Zanoni Dias
Grantee:Gustavo Rodrigues Galvão
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil


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:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
GALVAO, GUSTAVO RODRIGUES; BAUDET, CHRISTIAN; DIAS, ZANONI. Sorting Circular Permutations by Super Short Reversals. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, v. 14, n. 3, p. 620-633, MAY-JUN 2017. Web of Science Citations: 2.
GALVAO, GUSTAVO RODRIGUES; LEE, ORLANDO; DIAS, ZANONI. Sorting signed permutations by short operations. Algorithms for Molecular Biology, v. 10, MAR 25 2015. Web of Science Citations: 6.
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
GALVÃO, Gustavo Rodrigues. Algoritmos para problemas de ordenação por reversões ou transposições, com aplicações em rearranjo de genomas. 2015. 163 f. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.

Please report errors in scientific publications list by writing to: