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 Complexity of Sorting by Reversals and Transpositions Problems

Texto completo
Autor(es):
Oliveira, Andre Rodrigues [1] ; Brito, Klairton Lima [1] ; Dias, Ulisses [2] ; Dias, Zanoni [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Ave Albert Einstein 1251, BR-13083852 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 COMPUTATIONAL BIOLOGY; v. 26, n. 11, p. 1223-1229, NOV 1 2019.
Citações Web of Science: 1
Resumo

In comparative genomics, rearrangements are mutations that affect a stretch of DNA sequences. Reversals and transpositions are well-known rearrangements, and each has a vast literature. The reversal and transposition distance, that is, the minimum number of reversals and transpositions needed to transform one genome into another is a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations was proposed >20 years ago and received the name of sorting by reversals and transpositions problem. It has been the focus of a number of studies, but the computational complexity has remained open until now. We hereby solve this question and prove that it is NP-hard no matter whether genomes are represented by signed or unsigned permutations. In addition, we prove that a usual generalization of this problem, which assigns weights w(rho) for reversals and w(tau) for transpositions, is also NP-hard as long as w(tau)/w(rho) <= 1.5 for both signed and unsigned permutations. (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: 17/16246-0 - Análise de mídias sensíveis usando arquiteturas de aprendizado profundo
Beneficiário:Sandra Eliza Fontes de Avila
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