Genome rearrangement algorithms

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

Abstract

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)

Scientific publications

(12)

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

BAUDET, CHRISTIAN; DIAS, ULISSES; DIAS, ZANONI. Sorting by weighted inversions considering length and symmetry. BMC Bioinformatics, v. 16, n. 19, DEC 16 2015. (13/08293-7, 14/19401-8, 12/01584-3)

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. (14/19401-8, 14/03535-5, 13/08293-7)

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. (14/03535-5, 14/19401-8)

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)

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. (14/19401-8, 12/01584-3, 13/08293-7)

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. (14/19401-8, 15/19222-9, 14/13433-5, 13/08293-7, 14/03535-5)

BAUDET, CHRISTIAN; DIAS, ULISSES; DIAS, ZANONI. Sorting by weighted inversions considering length and symmetry. BMC Bioinformatics, v. 16, p. 11-pg., 2015-12-16. (14/19401-8, 13/08293-7, 12/01584-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. (13/08293-7, 15/11937-9, 14/19401-8)

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)

OIKAWA, MARINA A.; DIAS, ZANONI; ROCHA, ANDERSON; GOLDENSTEIN, SIOME. Distances in multimedia phylogeny. International Transactions in Operational Research, v. 23, n. 5, p. 26-pg., 2016-09-01. (14/19401-8, 13/08293-7, 14/03535-5)

BRITO, KLAIRTON LIMA; OLIVEIRA, ANDRE RODRIGUES; DIAS, ULISSES; DIAS, ZANONI; JANSSON, J; MARTINVIDE, C; VEGARODRIGUEZ, MA. Heuristics for the Sorting Signed Permutations by Reversals and Transpositions Problem. ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018), v. 10849, p. 11-pg., 2018-01-01. (14/19401-8, 13/08293-7, 15/11937-9)