The sorting permutations problem using prefix and suffix operations

• Grant number: 13/01172-0
• Support Opportunities: Scholarships in Brazil - Doctorate (Direct)
• Start date: July 01, 2013
• End date: December 31, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Zanoni Dias
• Grantee: Carla Negri Lintzmayer
• Host 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

Abstract

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

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)

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. (13/01172-0, 12/01584-3)

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 (UNICAMP). Instituto de Computação Campinas, SP.