Advanced search
Start date

Genome rearrangement algorithms

Grant number: 14/19401-8
Support type:Regular Research Grants
Duration: May 01, 2015 - April 30, 2017
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Zanoni Dias
Grantee:Zanoni Dias
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Assoc. researchers:Ulisses Martins Dias


Genome Rearrangements is a field of study motivated, in biology, by the comparison of genomes. In particular, it aims at determining how similar two genomes (and thus two species) are. This is useful, among others, for building phylogenetic trees, annotating genomes or correcting already existing annotations. Species differentiation takes place via one or several modifications of its genome. The most common mutational events occur at one nucleotide. However, genomes also undergo large scale mutations during the evolutionary process. These mutations present a challenge to the Computational Theory Field, since most of the distance problems are NP-Complete. This research will focus on heuristics, comparative genomic algorithms, and formal proofs that take into consideration the presence of global mutations. The term Genome Rearrangements covers all problems of the following type: given two genomes G1 and G2, and a set of rearrangements, what is the least possible number of such rearrangements that are necessary to obtain G2 starting from G1? This type of algorithmic question has been introduced in the mid-nineties, and has been since studied for many different variants. Our goal with this project is to study several Genome Rearrangement Problems involving reversals and transpositions events. (AU)

Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications (9)
(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.
ARRUDA, THIAGO DA SILVA; DIAS, ULISSES; DIAS, ZANONI. A GRASP-Based Heuristic for the Sorting by Length-Weighted Inversions Problem. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, v. 15, n. 2, p. 352-363, MAR-APR 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.
OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI. On the Sorting by Reversals and Transpositions Problem. JOURNAL OF UNIVERSAL COMPUTER SCIENCE, v. 23, n. 9, p. 868-906, 2017. Web of Science Citations: 1.
MARMEROLA, GUILHERME D.; OIKAWA, MARINA A.; DIAS, ZANONI; GOLDENSTEIN, SIOME; ROCHA, ANDERSON. On the Reconstruction of Text Phylogeny Trees: Evaluation and Analysis of Textual Relationships. PLoS One, v. 11, n. 12 DEC 19 2016. Web of Science Citations: 4.
OIKAWA, MARINA A.; DIAS, ZANONI; ROCHA, ANDERSON; GOLDENSTEIN, SIOME. Distances in multimedia phylogeny. International Transactions in Operational Research, v. 23, n. 5, SI, p. 921-946, SEP 2016. Web of Science Citations: 0.
OIKAWA, MARINA A.; DIAS, ZANONI; ROCHA, ANDERSON DE REZENDE; GOLDENSTEIN, SIOME. Manifold Learning and Spectral Clustering for Image Phylogeny Forests. IEEE Transactions on Information Forensics and Security, v. 11, n. 1, p. 5-18, JAN 2016. Web of Science Citations: 16.
BAUDET, CHRISTIAN; DIAS, ULISSES; DIAS, ZANONI. Sorting by weighted inversions considering length and symmetry. BMC Bioinformatics, v. 16, n. 19 DEC 16 2015. 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: