O problema da ordenação de permutações usando operações de prefixo e sufixo

• Processo: 13/01172-0
• Modalidade de apoio: Bolsas no Brasil - Doutorado Direto
• Data de Início da vigência: 01 de julho de 2013
• Data de Término da vigência: 31 de dezembro de 2016
• Á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: Carla Negri Lintzmayer
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Bolsa(s) vinculada(s): 14/20738-7 - Ordenação de permutações por reversões de prefixo e reversões de sufixo, BE.EP.DD
• Assunto(s): Algoritmos genéticos Biologia computacional Rearranjo gênico
• Palavra(s)-Chave do Pesquisador: Algoritmos | Biologia Computacional | Rearranjo de Genomas | Biologia Computacional

Resumo

Reversões e transposições são os tipos mais comuns de rearranjos de genomas, que são operações que afetam grandes porções dos genomas. Por meio dos rearranjos é possível estabelecer a divergência entre indivíduos ao longo da evolução. A distância mínima entre dois determinados genomas é assumida como sendo a distância evolutiva entre eles, e ela pode ser obtida por meio de cenários que envolvam os rearranjos. Assim, um problema de ordenação de genomas por meio de um ou mais tipos de rearranjos é o problema de encontrar a distância mínima entre dois genomas utilizando os rearranjos permitidos. Quando as operações de rearranjo afetam segmentos do início ou do fim do genoma, dizemos que são rearranjos de prefixo ou de sufixo, respectivamente. Esta proposta apresenta alguns conceitos iniciais e resultados já existentes sobre alguns problemas relacionados, bem como especifica o objetivo do nosso trabalho, que visa lidar com problemas de ordenação usando operações de reversão e transposição nas suas versões de prefixo e sufixo. (AU)

Publicações científicas

(4)

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

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)

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)

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)

Publicações acadêmicas

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

LINTZMAYER, Carla Negri. The problem of sorting permutations by prefix and suffix rearrangements. 2016. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.