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

Approximation algorithms for sorting by length-weighted prefix and suffix operations

Texto completo
Autor(es):
Lintzmayer, Carla Negri [1] ; Fertin, Guillaume [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 Nantes, UMR CNRS 6241, Lab Informat Nantes Atlantique, F-44322 Nantes 3 - France
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: THEORETICAL COMPUTER SCIENCE; v. 593, p. 26-41, AUG 16 2015.
Citações Web of Science: 2
Resumo

The traditional approach for the problems of sorting permutations by rearrangements is to consider that all operations have the same unitary cost. In this case, the goal is to find the minimum number of allowed rearrangements that are needed to sort a given permutation, and numerous efforts have been made over the past years regarding these problems. On the other hand, a long rearrangement (which is in fact a mutation) is more likely to disturb the organism. Therefore, weights based on the length of the segment involved may have an important role in the evolutionary process. In this paper we present the first results regarding problems of sorting permutations by length-weighted operations that consider rearrangement models with prefix and suffix variations of reversals and transpositions, which are the two most common types of genome rearrangements. Our main results are O (lg(2) n)-approximation algorithms for 10 such problems. (C) 2015 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 14/20738-7 - Ordenação de permutações por reversões de prefixo e reversões de sufixo
Beneficiário:Carla Negri Lintzmayer
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Doutorado Direto
Processo FAPESP: 14/19401-8 - Algoritmos para rearranjos de genomas
Beneficiário:Zanoni Dias
Linha de fomento: Auxílio à Pesquisa - Regular
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
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