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 by lambda-Operations

Autor(es):
Santos Miranda, Guilherme Henrique [1] ; Lintzmayer, Carla Negri [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] Fed Univ ABC, Ctr Math Computat & Cognit, Santo Andre - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF UNIVERSAL COMPUTER SCIENCE; v. 25, n. 2, p. 98-121, 2019.
Citações Web of Science: 0
Resumo

For estimating the evolutionary distance between genomes of two different organisms, many sorting permutation problems have emerged. A well accepted way to do this is considering the smallest sequence of rearrangement events - mutations which affect large portions of the genomes - that transform one genome into the other. In these problems, both genomes are represented as permutations of integer numbers, but one of them can be represented as the identity permutation, so that the problem is reduced to sort a permutation. Moreover, rearrangement models define which type of operations (rearrangement events) can be applied over a permutation in order to modify it. Reversals, which are operations that revert a genome segment, and transpositions, which are operations that swap two adjacent genome segments, are two of the most studied types of rearrangements in the literature. In this paper, we consider rearrangement models that allow reversals, transpositions, and both operations together. Since there exist evidences that large mutations rarely occur, we add a restriction with biological relevance: any operation can affect at most lambda elements of a permutation. For this variation of sorting permutation problem, we present approximation algorithms with approximation factors based on the size of the permutation and/or on lambda, for both signed and unsigned permutations (which represent known and unknown gene orientations, respectively). (AU)

Processo FAPESP: 17/12646-3 - Déjà vu: coerência temporal, espacial e de caracterização de dados heterogêneos para análise e interpretação de integridade
Beneficiário:Anderson de Rezende Rocha
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
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: 16/14132-4 - Empacotamentos uni e bidimensionais com restrições de conflitos e remoções
Beneficiário:Carla Negri Lintzmayer
Linha de fomento: Bolsas no Brasil - Pós-Doutorado