Genome Rearrangement Distance Problems

• Grant number: 12/01584-3
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: July 01, 2012
• End date: February 28, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Zanoni Dias
• Grantee: Ulisses Martins Dias
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

One way to compare two genomes is to compute a distance between them. Ideally this distance should accurately reflect the evolutionary divergence between the two genomes. Mutations are the main mechanism by which living organisms differentiate into new species. 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. Some of those algorithms will deal with clearly defined kinds of mutations, such as inversions or transpositions. Other algorithms will provide genome distance by allowing more than one class such as inversions and transpositions. A quick and accurate genome distance method has several applications. For example, given a set of genomes, one could easily obtain the distance for each pair of genomes in order to create a distance matrix. This matrix could be used to generate a philogenetic tree.

Scientific publications

(7)

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

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)

DIAS, ULISSES; DIAS, ZANONI. HEURISTICS FOR THE TRANSPOSITION DISTANCE PROBLEM. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 11, n. 5, OCT 2013. (12/01584-3)

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)

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)

BAUDET, CHRISTIAN; DIAS, ULISSES; DIAS, ZANONI; CAMPOS, S. Length and Symmetry on the Sorting by Weighted Inversions Problem. ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2014, v. 8826, p. 8-pg., 2014-01-01. (13/08293-7, 12/01584-3)

DIAS, ZANONI; DIAS, ULISSES. Sorting by Prefix Reversals and Prefix Transpositions. DISCRETE APPLIED MATHEMATICS, v. 181, p. 78-89, JAN 30 2015. (12/01584-3)