Algoritmos para rearranjos de genomas

• Processo: 14/19401-8
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Data de Início da vigência: 01 de maio de 2015
• Data de Término da vigência: 30 de abril de 2017
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Zanoni Dias
• Beneficiário: Zanoni Dias
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Pesquisadores associados: Ulisses Martins Dias
• Assunto(s): Biologia computacional Genomas Algoritmos de aproximação Ordenação
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Problemas de Ordenação | Rearranjo de Genomas | Biologia Computacional

Resumo

Rearranjo de Genomas é uma área de pesquisa motivada, na biologia, pela comparação de genomas. Em particular, objetiva-se estimar a similaridade entre dois genomas e, por conseguinte, entre duas espécies. Esse estudo é importante, por exemplo, para construção de árvores filogenéticas, anotação de genomas ou correção de anotações já existentes. 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. O termo "Rearranjo de Genomas" engloba todos os problemas enunciados da seguinte forma: dados dois genomas G1 e G2, e uma classe de rearranjos, qual é o número mínimo desses rearranjos que são necessários para transformar G1 em G2? Questões desse tipo foram introduzidas em meados da década de 1990 e tem sido estudadas em suas muitas variantes desde então. Nosso objetivo neste projeto é estudar várias versões do Problema de Rearranjo de Genomas, envolvendo eventos de reversão e transposição. (AU)

Publicações científicas

(12)

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

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)