Advanced search
Start date

The sorting permutations problem using prefix and suffix operations

Grant number: 13/01172-0
Support type:Scholarships in Brazil - Doctorate (Direct)
Effective date (Start): July 01, 2013
Effective date (End): December 31, 2016
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Zanoni Dias
Grantee:Carla Negri Lintzmayer
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Associated scholarship(s):14/20738-7 - Sorting permutations by prefix reversals and suffix reversals, BE.EP.DD


Reversals and transpositions are the most common kind of genome rearrangements, which are operations that affect large fragments of genomes. With rearrangements is possible to establish the divergence between individuals along evolution. The minimum distance between two certain genomes is assumed as being the evolutionary distance between them and it can be calculated by using scenarios involving rearrangements. Therefore, a sorting problem of genomes by using one or more kinds of rearrangements is the problem of finding the minimum distance between two genomes by using the allowed rearrangements. When the rearrangement operations affect segments of the beginning or of the end of the genome, we say that they are prefix or suffix rearrangements, respectively. This proposal presents some initial concepts and results already existent about related problems, as well as specifies the goal of our thesis, which aims to deal with sorting problems by using reversal and transposition operations in their versions of suffix and prefix. (AU)

Scientific publications (4)
(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)
LINTZMAYER, CARLA NEGRI; FERTIN, GUILLAUME; DIAS, ZANONI. Sorting permutations and binary strings by length-weighted rearrangements. THEORETICAL COMPUTER SCIENCE, v. 715, p. 35-59, MAR 8 2018. Web of Science Citations: 0.
LINTZMAYER, CARLA NEGRI; FERTIN, GUILLAUME; DIAS, ZANONI. Sorting permutations by prefix and suffix rearrangements. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 15, n. 1 FEB 2017. Web of Science Citations: 3.
LINTZMAYER, CARLA NEGRI; FERTIN, GUILLAUME; DIAS, ZANONI. Approximation algorithms for sorting by length-weighted prefix and suffix operations. THEORETICAL COMPUTER SCIENCE, v. 593, p. 26-41, AUG 16 2015. Web of Science Citations: 2.
DIAS, ULISSES; GALVAO, GUSTAVO RODRIGUES; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. A general heuristic for genome rearrangement problems. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 12, n. 3 JUN 2014. Web of Science Citations: 2.
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
LINTZMAYER, Carla Negri. O problema da ordenação de permutações usando rearranjos de prefixos e sufixos. 2016. Doctoral Thesis - Universidade Estadual de Campinas, Instituto de Computação.

Please report errors in scientific publications list by writing to: