Busca avançada
Ano de início
Entree


Block Interchange and Reversal Distance on Unbalanced Genomes

Texto completo
Autor(es):
Alexandrino, Alexsandro Oliveira ; Siqueira, Gabriel ; Brito, Klairton Lima ; Oliveira, Andre Rodrigues ; Dias, Ulisses ; Dias, Zanoni
Número total de Autores: 6
Tipo de documento: Artigo Científico
Fonte: ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2023; v. 13954, p. 13-pg., 2023-01-01.
Resumo

One method for inferring the evolutionary distance between two organisms is to find the rearrangement distance, which is defined as the minimum number of genome rearrangements required to transform one genome into the other. Rearrangements that do not alter the genome content are known as conservative. Examples of such rearrangements include: reversal, which reverts a segment of the genome; transposition, which exchanges two consecutive blocks; block interchange (BI), which exchanges two blocks at any position in the genome; and double cut and join (DCJ), which cuts two different pairs of adjacent blocks and joins them in a different manner. Initially, works in this area involved comparing genomes that shared the same set of conserved blocks. Nowadays, researchers are investigating unbalanced genomes (genomes with a distinct set of genes), which requires the use of non-conservative rearrangements such as insertions and deletions (indels). In cases where there are no repeated blocks and the genomes have the same set of blocks, the BI Distance and the Reversal Distance have polynomial-time algorithms, while the complexity of the BI and Reversal Distance problem remains unknown. In this study, we investigate the BI and Indel Distance and the BI, Reversal, and Indel Distance on genomes with different gene content and no repeated genes. We present 2-approximation algorithms for each problem using a variant of the breakpoint graph structure. (AU)

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: 21/13824-8 - Generalizações de problemas envolvendo partição de strings
Beneficiário:Gabriel Henriques Siqueira
Modalidade de apoio: Bolsas no Brasil - 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: 22/13555-0 - Distância de rearranjo em genomas não balanceados considerando regiões intergênicas
Beneficiário:Gabriel Henriques Siqueira
Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
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