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

Sorting permutations and binary strings by length-weighted rearrangements

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, Campinas, SP - Brazil
[2] Univ Nantes, UMR CNRS 6004, LS2N, Nantes - France
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: THEORETICAL COMPUTER SCIENCE; v. 715, p. 35-59, MAR 8 2018.
Citações Web of Science: 0
Resumo

Comparative genomics is a line of study which aims at determining dis/similarities between genomes. One way of doing this is to infer the large scale mutations (also called genome rearrangements) that are responsible for transforming one genome into another, under the parsimony principle. Numerous efforts have been made over the past years regarding the traditional approach, in which all genome rearrangements have the same unit cost. However, since long rearrangements are more likely to disturb the organism, some works considered the length-weighted approach, in which the cost of each rearrangement is a function of its length. The problem is thus modeled as follows: given two genomes G(1) and G(2) and a set beta of allowed genome rearrangements, each with a given cost, determine their distance, i.e., the total cost of a minimum-cost sequence of rearrangements from beta that transforms G(1) into G(2). In this paper, we study length-weighted reversals and transpositions, mainly considering their prefix variants (in which the leftmost part of the genome must always be included). We present approximation algorithms and bounds on the distances and diameters (i.e., maximum possible distance over any two genomes of same length) for eight problems when genomes are represented as permutations, and another eight problems when genomes are represented as binary strings, in each case considering two different cost functions. (C) 2018 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: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Temático
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