A New Approach for the Reversal Distance with Indels and Moves in Intergenic Regions

Autor(es)

Brito, Klairton Lima ; Oliveira, Andre Rodrigues ; Alexandrino, Alexsandro Oliveira ; Dias, Ulisses ; Dias, Zanoni ; Jin, L ; Durand, D

• Tipo de documento: Artigo Científico
• Fonte: COMPARATIVE GENOMICS (RECOMB-CG 2022); v. 13234, p. 16-pg., 2022-01-01.

Resumo

Genome rearrangement events are widely used to estimate a minimum-size sequence of mutations capable of transforming a genome into another. The length of this sequence is called distance, and determining it is the main goal in genome rearrangement distance problems. Problems in the genome rearrangement field differ regarding the set of rearrangement events allowed and the genome representation. In this work, we consider the scenario where the genomes share the same set of genes, gene orientation is known, and intergenic regions (structures between a pair of genes and at the extremities of the genome) are taken into account. We use two models, the first model allows only conservative events (reversals and moves), and the second model includes non-conservative events (insertions and deletions) in the intergenic regions. We show that both models result in NP-hard problems and we present algorithms with an approximation factor of 2. (AU)

• Processo FAPESP: 19/27331-3 - Problemas de ordenação por rearranjos de genomas
• Beneficiário: André Rodrigues Oliveira
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• 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: 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