Heuristics for Breakpoint Graph Decomposition with Applications in Genome Rearrangement Problems

• Pedro Olímpio Pinheiro UNICAMP http://orcid.org/0000-0002-8993-7451
• Alexsandro Oliveira Alexandrino UNICAMP http://orcid.org/0000-0002-6320-9747
• Andre Rodrigues Oliveira UNICAMP http://orcid.org/0000-0002-0568-1859
• Cid Carvalho de Souza UNICAMP http://orcid.org/0000-0002-5945-0845
• Zanoni Dias UNICAMP http://orcid.org/0000-0003-3333-6822

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.

Palavras-chave: Breakpoint graph, Genome rearrangements, Maximum cycle decomposition