Busca avançada
Ano de início
(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 general heuristic for genome rearrangement problems

Texto completo
Dias, Ulisses [1] ; Galvao, Gustavo Rodrigues [1] ; Lintzmayer, Carla Negri [1] ; Dias, Zanoni [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Citações Web of Science: 2

In this paper, we present a general heuristic for several problems in the genome rearrangement field. Our heuristic does not solve any problem directly, it is rather used to improve the solutions provided by any non-optimal algorithm that solve them. Therefore, we have implemented several algorithms described in the literature and several algorithms developed by ourselves. As a whole, we implemented 23 algorithms for 9 well known problems in the genome rearrangement field. A total of 13 algorithms were implemented for problems that use the notions of prefix and suffix operations. In addition, we worked on 5 algorithms for the classic problem of sorting by transposition and we conclude the experiments by presenting results for 3 approximation algorithms for the sorting by reversals and transpositions problem and 2 approximation algorithms for the sorting by reversals problem. Another algorithm with better approximation ratio can be found for the last genome rearrangement problem, but it is purely theoretical with no practical implementation. The algorithms we implemented in addition to our heuristic lead to the best practical results in each case. In particular, we were able to improve results on the sorting by transpositions problem, which is a very special case because many efforts have been made to generate algorithms with good results in practice and some of these algorithms provide results that equal the optimum solutions in many cases. Our source codes and benchmarks are freely available upon request from the authors so that it will be easier to compare new approaches against our results. (AU)

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/01172-0 - O problema da ordenação de permutações usando operações de prefixo e sufixo
Beneficiário:Carla Negri Lintzmayer
Linha de fomento: Bolsas no Brasil - Doutorado Direto