Evolutionary Algorithms for Sorting Genomes


Introduction

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.

Fitness Function Source Code

  • Sorting Unigned Permutations by Reversals (SUPBR) Problem:
    • (Fixed) 1.5 Approximation Algorithm for SUPBR. [Code].

Published Papers

  • 2016:
    • da Silveira, L. A., Soncco-Álvarez, J. L., de Lima, T. A., & Ayala-Rincón, M. (2016). Memetic and Opposition-Based Learning Genetic Algorithms for Sorting Unsigned Genomes by Translocations. In Advances in Nature and Biologically Inspired Computing (pp. 73-85). Springer International Publishing (DOI) and [Code].
    • da Silveira, L. A., Soncco-Álvarez, J. L., & Ayala-Rincón, M. (2016, July). Parallel memetic genetic algorithms for sorting unsigned genomes by translocations. In Evolutionary Computation (CEC), 2016 IEEE Congress on (pp. 185-192). IEEE (DOI) and [Code].
  • 2015:
    • da Silveira, L. A., Soncco-Álvarez, J. L., de Lima, T. A., & Ayala-Rincón, M. (2015, October). Computing translocation distance by a genetic algorithm. In Computing Conference (CLEI), 2015 Latin American (pp. 1-12). IEEE (DOI) and [Code].
    • Soncco-Álvarez, J. L., Almeida, G. M., Becker, J., & Ayala-Rincón, M. (2015). Parallelization of genetic algorithms for sorting permutations by reversals over biological data. International Journal of Hybrid Intelligent Systems, 12(1), 53-64.(DOI) and [Code].
  • 2014:
    • Soncco-Álvarez, J. L., & Ayala-Rincon, M. (2014, July). Memetic algorithm for sorting unsigned permutations by reversals. In Evolutionary Computation (CEC), 2014 IEEE Congress on (pp. 2770-2777). IEEE (DOI) and [Code].
  • 2013:
    • Soncco-Álvarez, J. L., Marchesan Almeida, G., Becker, J., & Ayala-Rincon, M. (2013, August). Parallelization and virtualization of genetic algorithms for sorting permutations by reversals. In Nature and Biologically Inspired Computing (NaBIC), 2013 World Congress on (pp. 29-35). IEEE (DOI) and [Code].
    • Soncco-Álvarez, J. L., & Ayala-Rincón, M. (2013). Sorting permutations by reversals through a hybrid genetic algorithm based on breakpoint elimination and exact solutions for signed permutations. Electronic Notes in Theoretical Computer Science, 292, 119-133. (DOI) and [Code].
  • 2012:
    • Soncco-Álvarez, J. L., & Ayala-Rincón, M. (2012, October). A genetic approach with a simple fitness function for sorting unsigned permutations by reversals. In Computing Congress (CCC), 2012 7th Colombian (pp. 1-6). IEEE (DOI).

Reports

  • 2017:
    • da Silveira, L. A., Soncco-Álvarez, J. L., & Ayala-Rincón, M. Parallel Genetic Algorithms with Sharing of Individuals for Sorting Unsigned Genomes by Reversals.[paper] and [Code].
    • Soncco-Álvarez, J. L., & Ayala-Rincón, M. Variable Neighborhood Search for the Large Phylogeny Problem using Gene Order Data.[paper].