A GRASP-Based Heuristic for the Sorting by Length-Weighted Inversions Problem

作者：Arruda Thiago da Silva^*; Dias Ulisses; Dias Zanoni

来源：IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2018, 15(2): 352-363.

DOI：10.1109/TCBB.2015.2474400

• Genome rearrangements
• length-weighted inversions
• GRASP

Genome Rearrangements are large-scale mutational events that affect genomes during the evolutionary process. Therefore, these mutations differ from punctual mutations. They can move genes from one place to the other, change the orientation of some genes, or even change the number of chromosomes. In this work, we deal with inversion events which occur when a segment of DNA sequence in the genome is reversed. In our model, each inversion costs the number of elements in the reversed segment. We present a new algorithm for this problem based on the metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP) that has been routinely used to find solutions for combinatorial optimization problems. In essence, we implemented an iterative process in which each iteration receives a feasible solution whose neighborhood is investigated. Our analysis shows that we outperform any other approach by significant margin. We also use our algorithm to build phylogenetic trees for a subset of species in the Yersinia genus and we compared our trees to other results in the literature.

• 出版日期2018-4