The calculation of the evolutionary distance between organism is an important task for the construction of phylogeny's based on the order of the genes. Maybe one of the most used evolutionary distance is the reversal distance in which reversals are used for transforming one genome into another. Other interesting metric is the translocation distance in which we must consider genomes with multiples chromosomes, unlike reversals which are applied more commonly in single-chromosome genomes.
The complexity of calculating the reversal distance and the translocation distance depends on how we represent the genes of a genome, when the genes are abstracted as signed numbers, the complexity of the problems are in P; however, when the genes are abstracted as unsigned numbers, their complexities were proven to be NP-Hard.
We implemented many evolutionary algorithms for treating these NP-Hard problems, with promising results most of which improved even approximation algorithms results. As part of this work it also was necessary to implement these approximation algorithms which was not a trivial task.