Algoritmos para o problema da ordenação por rearranjo

• Processo: 14/04718-6
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de setembro de 2014
• Data de Término da vigência: 30 de setembro de 2015
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Acordo de Cooperação: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
• Pesquisador responsável: Zanoni Dias
• Beneficiário: Gustavo Rodrigues Galvão
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Biologia computacional Algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos Aproximados | Biologia Computacional | Rearranjo de Genomas | Biologia Computacional

Resumo

Ao longo da evolução, mutações globais podem alterar a ordem dos genes de um genoma. Tais mutações são chamadas de eventos de rearranjo. Em Rearranjo de Genomas, estimamos a distância evolutiva entre dois genomas calculando-se a distância de rearranjo entre eles, que é o tamanho da menor sequência de eventos de rearranjo que transforma um genoma no outro. Representando genomas como permutações, nas quais os genes aparecem como elementos, a distância de rearranjo pode ser obtida resolvendo-se o problema combinatório de ordenar uma permutação utilizando o menor número de eventos de rearranjo. Este problema, que é referido como Problema da Ordenação por Rearranjo, varia de acordo com os tipos de eventos de rearranjo considerados. Neste doutorado, focaremos nosso estudo em dois tipos de eventos: reversões e transposições. Variações do Problema da Ordenação por Rearranjo que consideram esses eventos têm se mostrado difíceis de serem resolvidas otimamente, por isso a maior parte dos algoritmos propostos são aproximados. Nossa proposta é estudar algumas dessas variações, buscando desenvolver algoritmos aproximados ou heurísticos que superem os existentes. (AU)

Publicações científicas

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

GALVAO, GUSTAVO RODRIGUES; BAUDET, CHRISTIAN; DIAS, ZANONI. Sorting Circular Permutations by Super Short Reversals. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, v. 14, n. 3, p. 620-633, MAY-JUN 2017. (13/08293-7, 14/04718-6)

GALVAO, GUSTAVO RODRIGUES; LEE, ORLANDO; DIAS, ZANONI. Sorting signed permutations by short operations. Algorithms for Molecular Biology, v. 10, MAR 25 2015. (13/08293-7, 14/04718-6)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

GALVÃO, Gustavo Rodrigues. Algorithms for sorting by reversals or transpositions, with application to genome rearrangement. 2015. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.