Busca avançada
Ano de início
Entree


Heuristics for Cycle Packing of Adjacency Graphs for Genomes with Repeated Genes

Texto completo
Autor(es):
Siqueira, Gabriel ; Oliveira, Andre Rodrigues ; Alexandrino, Alexsandro Oliveira ; Dias, Zanoni ; Stadler, PF ; Walter, MEMT ; Hernandez-Rosales, M ; Brigido, MM
Número total de Autores: 8
Tipo de documento: Artigo Científico
Fonte: ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2021; v. 13063, p. 13-pg., 2021-01-01.
Resumo

The Adjacency Graph is a structure used to model genomes in several rearrangement distance problems. In particular, most studies use properties of a maximum cycle packing of this graph to develop bounds and algorithms for rearrangement distance problems, such as the reversal distance and the Double Cut and Join (DCJ) distance. When each genome has no repeated genes, there exists only one cycle packing for the graph. However, when each genome may have repeated genes, the problem of finding a maximum cycle packing for the adjacency graph (Adjacency Graph Packing) is NP-hard. In this work, we developed a greedy random heuristic and a genetic algorithm heuristic for the Adjacency Graph Packing problem for genomes with repeated genes. We present experimental results and compare these heuristics with the SOAR framework. Furthermore, we show how the solutions from our algorithms can improve the estimation for the reversal distance when compared to the SOAR framework. Lastly, we applied our genetic algorithm heuristic in real genomic data to validate its practical use. (AU)

Processo FAPESP: 19/27331-3 - Problemas de ordenação por rearranjos de genomas
Beneficiário:André Rodrigues Oliveira
Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 17/12646-3 - Déjà vu: coerência temporal, espacial e de caracterização de dados heterogêneos para análise e interpretação de integridade
Beneficiário:Anderson de Rezende Rocha
Modalidade de apoio: Auxílio à Pesquisa - Temático
Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Modalidade de apoio: Auxílio à Pesquisa - Temático
Processo FAPESP: 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais
Beneficiário:Munir Salomao Skaf
Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs