Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

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

Texto completo
Autor(es):
Arruda, Thiago da Silva [1] ; Dias, Ulisses [2] ; Dias, Zanoni [1]
Número total de Autores: 3
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
Número total de Afiliações: 2
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
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 12/01584-3 - Problemas de distâncias de rearranjos de genomas
Beneficiário:Ulisses Martins Dias
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais
Beneficiário:Munir Salomao Skaf
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs