| Full text | |
| Author(s): |
Pinheiro, Pedro Olimpio
;
Alexandrino, Alexsandro Oliveira
;
Oliveira, Andre Rodrigues
;
de Souza, Cid Carvalho
;
Dias, Zanoni
;
Setubal, JC
;
Silva, WM
Total Authors: 7
|
| Document type: | Journal article |
| Source: | ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2020; v. 12558, p. 12-pg., 2020-01-01. |
| Abstract | |
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) | |
| FAPESP's process: | 19/25410-3 - Partition of Eulerian graphs in circuits |
| Grantee: | Pedro Olímpio Nogueira de Oliveira Pinheiro |
| Support Opportunities: | Scholarships in Brazil - Master |
| FAPESP's process: | 13/08293-7 - CCES - Center for Computational Engineering and Sciences |
| Grantee: | Munir Salomao Skaf |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |
| FAPESP's process: | 19/27331-3 - Sorting by genome rearrangements problems |
| Grantee: | André Rodrigues Oliveira |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 17/12646-3 - Déjà vu: feature-space-time coherence from heterogeneous data for media integrity analytics and interpretation of events |
| Grantee: | Anderson de Rezende Rocha |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |