On the Complexity of Sorting by Reversals and Transpositions Problems

Autor(es)

Oliveira, Andre Rodrigues ^[1] ; Brito, Klairton Lima ^[1] ; Dias, Ulisses ^[2] ; Dias, Zanoni ^[1]

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

• 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: 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais
• Beneficiário: Munir Salomao Skaf
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 17/16246-0 - Análise de mídias sensíveis usando arquiteturas de aprendizado profundo
• Beneficiário: Sandra Eliza Fontes de Avila
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• 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
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• 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
• Modalidade de apoio: Auxílio à Pesquisa - Temático