Advanced search
Start date

Sorting permutations by prefix reversals and suffix reversals

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


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)

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)
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.

Please report errors in scientific publications list by writing to: