Advanced search
Start date
Betweenand

Genome rearrangement distance problems

Grant number: 12/01584-3
Support type:Scholarships in Brazil - Post-Doctorate
Effective date (Start): July 01, 2012
Effective date (End): February 28, 2015
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Zanoni Dias
Grantee:Ulisses Martins Dias
Home 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 (5)
(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)
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.
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.
DIAS, ZANONI; DIAS, ULISSES. Sorting by Prefix Reversals and Prefix Transpositions. DISCRETE APPLIED MATHEMATICS, v. 181, p. 78-89, JAN 30 2015. Web of Science Citations: 4.
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. Web of Science Citations: 2.
DIAS, ULISSES; DIAS, ZANONI. HEURISTICS FOR THE TRANSPOSITION DISTANCE PROBLEM. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 11, n. 5 OCT 2013. Web of Science Citations: 4.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.