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

Autor(es)

Arruda, Thiago da Silva ^[1] ; Dias, Ulisses ^[2] ; Dias, Zanoni ^[1]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil

^[2] Univ Estadual Campinas, Fac Technol, BR-13484332 Limeira, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS; v. 15, n. 2, p. 352-363, MAR-APR 2018.
• Citações Web of Science: 0

Resumo

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. (AU)

• Processo FAPESP: 14/19401-8 - Algoritmos para rearranjos de genomas
• Beneficiário: Zanoni Dias
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 12/01584-3 - Problemas de Distâncias de Rearranjos de Genomas
• Beneficiário: Ulisses Martins Dias
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais
• Beneficiário: Munir Salomao Skaf
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs