orting Permutations by Intergenic Operation

Autor(es)

Oliveira, Andre Rodrigues ^[1] ; Jean, Geraldine ^[2] ; Fertin, Guillaume ^[2] ; Brito, Klairton Lima ^[1] ; Dias, Ulisses ^[3] ; Dias, Zanoni ^[1]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Inst Comp, BR-13083970 Campinas - Brazil

^[2] Univ Nantes, LS2N, CNRS, UMR 6004, F-44035 Nantes - France

^[3] Univ Estadual Campinas, Sch Technol, BR-13484350 Limeira - Brazil

• Tipo de documento: Artigo Científico
• Fonte: IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS; v. 18, n. 6, p. 2080-2093, NOV 1 2021.
• Citações Web of Science: 0

Resumo

Genome Rearrangements are events that affect large stretches of genomes during evolution. Many mathematical models have been used to estimate the evolutionary distance between two genomes based on genome rearrangements. However, most of them focused on the (order of the) genes of a genome, disregarding other important elements in it. Recently, researchers have shown that considering regions between each pair of genes, called intergenic regions, can enhance distance estimation in realistic data. Two of the most studied genome rearrangements are the reversal, which inverts a sequence of genes, and the transposition, which occurs when two adjacent gene sequences swap their positions inside the genome. In this work, we study the transposition distance between two genomes, but we also consider intergenic regions, a problem we name Sorting by Intergenic Transpositions. We show that this problem is NP-hard and propose two approximation algorithms, with factors 3.5 and 2.5, considering two distinct definitions for the problem. We also investigate the signed reversal and transposition distance between two genomes considering their intergenic regions. This second problem is called Sorting by Signed Intergenic Reversals and Intergenic Transpositions. We show that this problem is NP-hard and develop two approximation algorithms, with factors 3 and 2.5. We check how these algorithms behave when assigning weights for genome rearrangements. Finally, we implemented all these algorithms and tested them on real and simulated data. (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: 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
• 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