Busca avançada
Ano de início
Entree

Problemas de ordenação de permutações por operações ponderadas pelo número de fragmentações

Processo: 17/16871-1
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de dezembro de 2017
Vigência (Término): 28 de fevereiro de 2019
Á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:Alexsandro Oliveira Alexandrino
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Biologia computacional   Rearranjo gênico   Algoritmos de aproximação   Permutações   Fragmentação

Resumo

Calcular a distância evolucionária entre espécies é um problema importante da área de Biologia Computacional, sendo que para isso consideramos conjuntos de mutações que alteram grandes trechos do genoma, os quais chamamos de rearranjos de genoma. Representa-se um genoma como uma permutação de inteiros, em que cada elemento corresponde a um bloco conservado (região de alta similaridade entre os genomas a serem comparados). Devido a propriedades algébricas das permutações, o problema de transformar um genoma em outro é equivalente ao da ordenação de permutações por operações de rearranjo. A abordagem mais comum considera que todos os rearranjos tem o mesmo custo, assim o objetivo é encontrar uma sequência mínima de rearranjos que ordenem a permutação. Porém, estudos indicam que algumas operações de rearranjo tem maior probabilidade de acontecer do que outras, fazendo com que abordagens em que operações possuem custos diferentes sejam mais realistas. Nessa abordagem ponderada, o objetivo é encontrar a sequência que ordena a permutação, tal que a soma dos custos dos rearranjos dessa sequência seja mínimo. Esta proposta apresenta uma nova versão para o problema da ordenação de permutações por operações ponderadas, em que a função de custo de uma operação corresponde a quantidade de fragmentações que a operação causa na permutação. (AU)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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)
ALEXANDRINO, ALEXSANDRO OLIVEIRA; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. Sorting permutations by fragmentation-weighted operations. JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, v. 18, n. 2, . (17/12646-3, 17/16871-1, 17/16246-0, 15/11937-9)
RODRIGUES, CAROLINE MAZINI; SORIANO-VARGAS, AUREA; LAVI, BAHRAM; ROCHA, ANDERSON; DIAS, ZANONI. Manifold Learning for Real-World Event Understanding. IEEE Transactions on Information Forensics and Security, v. 16, p. 2957-2972, . (18/16548-9, 18/16214-3, 17/16246-0, 15/11937-9, 18/05668-3, 13/08293-7, 17/12646-3, 17/16871-1)
MIRANDA, GUILHERME HENRIQUE SANTOS; ALEXANDRINO, ALEXSANDRO OLIVEIRA; LINTZMAYER, CARLA NEGRI; DIAS, ZANONI. Approximation Algorithms for Sorting lambda-Permutations by lambda-Operations. ALGORITHMS, v. 14, n. 6, . (13/08293-7, 15/11937-9, 17/16871-1, 17/12646-3, 17/16246-0)
Publicações acadêmicas
(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)
ALEXANDRINO, Alexsandro Oliveira. Problemas de ordenação de permutações por operações ponderadas. 2019. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.