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.

Work in Progress

Published Papers

  • 2024:
    • L. A. da Silveira, T. A. de Lima, and M. Ayala-Rincón On Reconfiguring Heterogeneous Parallel Island Models, (Preliminary version 2023, Source and Data) Swarm and Evolutionary Computation, vol. 89, paper 101624, 2024 (DOI).
  • 2023:
    • da Silveira, L. A. & de Lima, T. A. & de Barros, J. B. & Soncco-Álvarez, J. L. & Llanos, C. H. & Ayala-Rincón, M. On The Behaviour of Parallel Island Model Genetic Algorithms [Source and Data]. In press, J. Applied Soft Computing 148:110880, 2023 (DOI).
  • 2022:
    • da Silveira, L. A. & de Lima, T. A. & Ayala-Rincón, M. Reconfigurable Heterogeneous Parallel Island Models. In Proc. IEEE Symposium Series on Computational Intelligence (SSCI), 2022, (DOI)
  • 2021:
    • da Silveira, L. A. & de Lima, T. A. & Soncco-Álvarez, J. L. & Ayala-Rincón, M. Heterogeneous Parallel Island Models (pdf author version, Source and Data). 2021 IEEE Symposium Series on Computational Intelligence (SSCI). (DOI).
  • 2020:
    • da Silveira, L. A., Soncco-Álvarez, J. L., de Lima, T. A., & Ayala-Rincón, M.Behaviour of Bioinspired Algorithms in Parallel Island Models. 2020 IEEE Congress on Evolutionary Computation CEC 2020 Extended Version, [Source Code and Data]. (DOI).
  • 2019:
    • Soncco-Álvarez, J. L., Muñoz, D. M., & Ayala-Rincón, M. Opposition-Based Memetic Algorithm and Hybrid Approach for Sorting Permutations by Reversals.[Source Code][Data+Experiments]. Evolutionary Computation Vol. 27(2):229-265, 2019. (DOI)
    • da Silveira, L. A., Soncco-Álvarez, J. L., de Lima, T. A., & Ayala-Rincón, M. (2019) Parallel Island models Genetic Algorithms applied in NP-Hard problems. 2019 IEEE Congress on Evolutionary Computation CEC 2019 Extended version, [Source Code, Data and Experiments]. (DOI)
  • 2018:
    • de Lima, T. A., & Ayala-Rincón, M. (2018). On the average number of reversals needed to sort signed permutations. Discrete Applied Mathematics 235: 59-80 (2018) (DOI).
    • da Silveira, L. A., Soncco-Álvarez, J. L., de Lima, T. A., & Ayala-Rincón, M. (2018) Parallel Multi-Island Genetic Algorithms for Sorting Unsigned Genomes by Reversals. In Evolutionary Computation (CEC), 2018 IEEE Congress on (8 pages). IEEE. (DOI) and (Extended version) and [Data+Experiments]
  • 2017:
    • Soncco-Álvarez, J. L., & Ayala-Rincón, M. (2017). Variable Neighborhood Search for the Large Phylogeny Problem using Gene Order Data. In Evolutionary Computation (CEC), 2017 IEEE Congress on (pp. 59-66). IEEE. (DOI) and [Code].
    • da Silveira, L. Â., Soncco-Álvarez, J. L., & Ayala-Rincón, M. (2017, June). Parallel genetic algorithms with sharing of individuals for sorting unsigned genomes by reversals. In Evolutionary Computation (CEC), 2017 IEEE Congress on (pp. 741-748). IEEE. (DOI) and [Code].
  • 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 nk">(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:
    • T.A. de Lima and M. Ayala-Rincón Complexity of Reversal Distance and other General Metrics on Permutation Groups. In Computing Congress (CCC), 2012 7th Colombian. IEEE. (DOI).
    • 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. IEEE (DOI) and [Code].

Contact

The main authors are Soncco-Álvarez, J. L., da Silveira, L. A., de Lima, T. A., and Ayala-Rincón, M.