Modelos de Programação Linear Inteira para o Problema de Rearranjo de Genomas por Transposição

Abstract

The biological evolution is the set of changes in the heritable characteristics in a population over time. A problem in computational biology is to calculate the evolutionary distance among species, being that the evolutionary distance considers only sets of mutations that updates pieces of the genome, which we call genome rearrangements (SETUBAL; MEIDANIS, 1997). In the studied literature, the two most observed kinds of genome rearrangements are reversal and transposition. This study aims to create a new integer linear programming model for the genome rearrangement problem, and to compare it with the current models in literature. It is also proposed the addition of valid inequalities to improve the efficiency of the models, and it is applied the lagrangian relaxation to improve the lower bounds. We conclude that the model defined by Lancia, Rinaldi and Serafini (2015) has better practical results. The proposed improvements do not bring significant improvements to the models.