Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

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

Full text
Author(s):
Arruda, Thiago da Silva [1] ; Dias, Ulisses [2] ; Dias, Zanoni [1]
Total Authors: 3
Affiliation:
[1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil
[2] Univ Estadual Campinas, Fac Technol, BR-13484332 Limeira, SP - Brazil
Total Affiliations: 2
Document type: Journal article
Source: IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS; v. 15, n. 2, p. 352-363, MAR-APR 2018.
Web of Science Citations: 0
Abstract

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)

FAPESP's process: 14/19401-8 - Genome rearrangement algorithms
Grantee:Zanoni Dias
Support type: Regular Research Grants
FAPESP's process: 12/01584-3 - Genome rearrangement distance problems
Grantee:Ulisses Martins Dias
Support type: Scholarships in Brazil - Post-Doctorate
FAPESP's process: 13/08293-7 - CCES - Center for Computational Engineering and Sciences
Grantee:Munir Salomao Skaf
Support type: Research Grants - Research, Innovation and Dissemination Centers - RIDC