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 signed circular permutations by super short operations

Texto completo
Autor(es):
Oliveira, Andre R. [1] ; Fertin, Guillaume [2] ; Dias, Ulisses [3] ; Dias, Zanoni [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
[2] Univ Nantes, CNRS, UMR 6004, LS2N, Nantes - France
[3] Univ Estadual Campinas, Sch Technol, Limeira - Brazil
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: Algorithms for Molecular Biology; v. 13, JUL 26 2018.
Citações Web of Science: 0
Resumo

Background: One way to estimate the evolutionary distance between two given genomes is to determine the minimum number of large-scale mutations, or genome rearrangements, that are necessary to transform one into the other. In this context, genomes can be represented as ordered sequences of genes, each gene being represented by a signed integer. If no gene is repeated, genomes are thus modeled as signed permutations of the form pi = (pi(1)pi(2) ... pi(n)), and in that case we can consider without loss of generality that one of them is the identity permutation iota(n) = (12 ... n), and that we just need to sort the other (i.e., transform it into iota(n)). The most studied genome rearrangement events are reversals, where a segment of the genome is reversed and reincorporated at the same location; and transpositions, where two consecutive segments are exchanged. Many variants, e.g., combining different types of (possibly constrained) rearrangements, have been proposed in the literature. One of them considers that the number of genes involved, in a reversal or a transposition, is never greater than two, which is known as the problem of sorting by super short operations (or SSOs). Results and conclusions: All problems considering SSOs in permutations have been shown to be in P, except for one, namely sorting signed circular permutations by super short reversals and super short transpositions. Here we fill this gap by introducing a new graph structure called cyclic permutation graph and providing a series of intermediate results, which allows us to design a polynomial algorithm for sorting signed circular permutations by super short reversals and super short transpositions. (AU)

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