Sorting permutations by prefix reversals and suffix reversals

• Grant number: 14/20738-7
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate (Direct)
• Start date: February 16, 2015
• End date: August 15, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Zanoni Dias
• Grantee: Carla Negri Lintzmayer
• Supervisor: Guillaume Fertin
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: Université de Nantes, France
• Associated to the scholarship: 13/01172-0 - The sorting permutations problem using prefix and suffix operations, BP.DD

Abstract

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 by prefix and suffix rearrangements. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 15, n. 1, FEB 2017. (13/08293-7, 14/20738-7, 15/11937-9, 14/19401-8, 16/14132-4, 13/01172-0)

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. (14/20738-7, 14/19401-8, 13/01172-0, 15/11937-9, 13/08293-7)

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. (13/08293-7, 14/20738-7, 14/19401-8, 13/01172-0)