Problemas de Distâncias de Rearranjos de Genomas

• Processo: 12/01584-3
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de julho de 2012
• Data de Término da vigência: 28 de fevereiro de 2015
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Zanoni Dias
• Beneficiário: Ulisses Martins Dias
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos de aproximação Biologia computacional
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Distância de Reversão e Transposição | Distância de Reversão-Simétrica | Distância de Transposição | Distância de Transposição de Prefixos | Problemas NP-Completos | Biologia Computacional

Resumo

Um modo de comparar dois genomas é computar uma distância entre eles. Idealmente, essa distância deve refletir as divergências evolucionárias entre ambos. Os fenômenos responsáveis pelas diferenciações entre os seres-vivos são as mutações ocorridas no material genético. Os eventos de mutação mais comuns afetam pontualmente o genoma, inserindo, removendo ou substituindo nucleotídeos. Entretanto, eventos de mutações globais, os chamados rearranjos de genomas, afetam grandes trechos do genoma e são um desafio para a teoria da computação, pois, na maioria dos casos, computar uma distância entre genomas na presença de operações globais resulta em problemas NP-Completos. Este projeto de pesquisa foca em heurísticas, algoritmos e provas formais para problemas NP-Completos ou com complexidade indefinida em rearranjo de genomas. Alguns tópicos de pesquisa serão específicos para certas classes de operações como, por exemplo, reversões ou transposições. Outros tópicos focam na distância entre os genomas usando mais de uma operação de rearranjo como, por exemplo, distância entre genomas quando reversões e transposições são permitidas. Uma distância precisa e calculável rapidamente possui diversas aplicações. Por exemplo, dado um grupo de genomas, é possível calcular a distância para cada par de genomas e armazenar os valores em uma matriz de distâncias. Essa matriz de distância pode ser usada como entrada para a geração de uma árvore filogenética.

Publicações científicas

(7)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

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)