| Texto completo | |
| Autor(es): |
Alexandrino, Alexsandro Oliveira
[1]
;
Oliveira, Andre Rodrigues
[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, 1251 Albert Einstein Ave, BR-13083852 Campinas - 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; NOV 2021. |
| Citações Web of Science: | 0 |
| Resumo | |
In the comparative genomics field, one way to infer the evolutionary distance between two organisms of related species is by finding the minimum number of large-scale mutations, called genome rearrangements, that transform one genome into the other. This number is referred to as the rearrangement distance. Since problems in this area emerged in the mid-1990s, several genome rearrangements have been proposed. Rearrangements that do not alter the genome content are called conservative, and in this group we have the following: the reversal, which inverts a segment of the genome; the transposition, which exchanges two consecutive segments; and the double cut and join, which cuts two different pairs of adjacent blocks and joins them differently. Seminal works compared genomes sharing the same set of conserved blocks, but nowadays, researchers started looking at genomes with unequal gene content, by allowing the use of nonconservative rearrangements such as insertion and deletion (jointly called indel). The transposition distance and the transposition and indel distance are both NP-hard. We investigate the transposition and indel distance and present a structure called labeled cycle graph, representing an instance of rearrangement distance problems for genomes with unequal gene content. This structure is used to devise a lower bound and a 2-approximation algorithm for the transposition and indel distance.</p> (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 |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| 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 |
| 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 |