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

On the Sorting by Reversals and Transpositions Problem

Autor(es):
Oliveira, Andre Rodrigues [1] ; Dias, Ulisses [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 Estadual Campinas, Sch Technol, Limeira - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF UNIVERSAL COMPUTER SCIENCE; v. 23, n. 9, p. 868-906, 2017.
Citações Web of Science: 1
Resumo

Reversals and transpositions are two classic genome rearrangement operations. Reversals occur when a chromosome breaks at two locations called breakpoints and the DNA between the breakpoints is reversed. Transpositions occur when two adjacent blocks of elements exchange position. This paper presents a polynomial-time approximation algorithm for the Sorting by Reversals and Transpositions Problem. Our algorithm applies to both signed and unsigned versions of the problem, and it treats both cases in a unified manner. We prove an approximation factor of 2 for signed permutations and 2k for the unsigned case, where k is the approximation factor of the algorithm used for cycle decomposition, but in our practical experiments our algorithm found results with approximation ratio better than 1.5 in more than 99% of the signed permutations and better than 1.8 in more than 97% of the unsigned permutations. Our analysis also shows that our algorithm outperforms any other approach known to date. (AU)

Processo FAPESP: 14/19401-8 - Algoritmos para rearranjos de genomas
Beneficiário:Zanoni Dias
Linha de fomento: Auxílio à Pesquisa - Regular
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