Ordenação de permutações por reversões de prefixo e reversões de sufixo

• Processo: 14/20738-7
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado Direto
• Data de Início da vigência: 16 de fevereiro de 2015
• Data de Término da vigência: 15 de agosto 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: Carla Negri Lintzmayer
• Supervisor: Guillaume Fertin
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: Université de Nantes, França
• Vinculado à bolsa: 13/01172-0 - O problema da ordenação de permutações usando operações de prefixo e sufixo, BP.DD
• Assunto(s): Biologia computacional Algoritmos Rearranjo gênico
• Palavra(s)-Chave do Pesquisador: Algorithms | Computational biology | Genome Rearrangements | Sorting Permutations | Biologia Computacional

Resumo

Uma forma de comparar dois genomas é computar uma distância entre eles. Uma abordagem para fazer isso é encontrar o menor número de mutações em larga escala, os rearranjos de genomas, que ocorreram para transformar um genoma no outro. Quando representamos os genomas como permutações, o objetivo é ordenar uma dada permutação com o menor número de rearranjos. Reversões e transposições são os tipos mais estudados de rearranjos de genomas e quando eles afetam segmentos do começo ou do fim do genoma (permutação), eles são chamados de rearranjos de prefixo ou de sufixo, respectivamente. Nessa proposta, descrevemos os resultados conhecidos considerando alguns problemas de ordenação de permutações por rearranjos de genomas e descrevemos nossos objetivos com relação ao doutorado sanduíche, que consideram estudar mais profundamente o problema de ordenação de permutações por reversões de prefixo e reversões de sufixo. (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)

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)