| Texto completo | |
| Autor(es): |
Pinheiro, Pedro Olimpio
;
Alexandrino, Alexsandro Oliveira
;
Oliveira, Andre Rodrigues
;
de Souza, Cid Carvalho
;
Dias, Zanoni
;
Setubal, JC
;
Silva, WM
Número total de Autores: 7
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2020; v. 12558, p. 12-pg., 2020-01-01. |
| Resumo | |
The breakpoint graph of a permutation is a well-known structure used in genome rearrangement problems. Most studies use the decomposition of such graph into edge-colored disjoint alternating cycles to develop algorithms for these problems. The goal of the Breakpoint Graph Decomposition (BGD) problem is to find a decomposition of the breakpoint graph with maximum number of cycles. For unsigned permutations, which model genomes without information about gene orientation, the BGD problem is NP-hard. In this work, we developed a greedy and a Tabu Search algorithm which are compared experimentally with the approximation algorithm presented by Lin and Jiang [10]. The experiments revealed that our algorithms find significantly better solutions. Finally, we used our algorithms as part of algorithms for genome rearrangement problems and the distances calculated in this way have largely improved. (AU) | |
| Processo FAPESP: | 19/25410-3 - Partição de grafos eulerianos em circuitos |
| Beneficiário: | Pedro Olímpio Nogueira de Oliveira Pinheiro |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |
| 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 |
| 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 |