| Texto completo | |
| Autor(es): |
Biller, Priscila
;
Pereira Zanetti, Joao Paulo
;
Meidanis, Joao
;
Setubal, JC
;
Silva, WM
Número total de Autores: 5
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2020; v. 12558, p. 9-pg., 2020-01-01. |
| Resumo | |
The rank distance between matrices has been applied to genome evolution, specifically in the area of genome rearrangements. It corresponds to looking for the optimal way of transforming one genome into another by cuts and joins with weight 1 and double-swaps with weight 2. In this context, the genome median problem, which takes three genomes A, B, and C and aims to find a genome M such that d(A, M) + d(B, M) + d(C, M) is minimized, is relevant. This problem can be stated for any genomic distance, not just the rank distance. In many cases, the genome median problem is NP-hard, but a number of approximate methods have been developed. Here we examine a related problem, the so-called center genome problem, where we aim to minimize the maximum (instead of the sum) of pairwise distances between the center genome and the inputs. We show that, for the rank distance, and for two genomic inputs A and B, it is not possible to always attain the well-known lower bound [d(A, B)/2]. The issue arises when A and B are co-tailed genomes (i.e., genomes with the same telomeres) with d(A, B) equal to twice an odd number, when the optimal attainable score is 1 unit larger than the lower bound. In all other cases, we show that the lower bound is attained. (AU) | |
| Processo FAPESP: | 12/13865-7 - Modelo Algébrico de Rearranjo de Genomas |
| Beneficiário: | João Paulo Pereira Zanetti |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |
| Processo FAPESP: | 12/14104-0 - Problemas de Rearranjo de Genomas Vistos Através de Permutações, Matrizes e Outros Conceitos de Álgebra |
| Beneficiário: | Priscila Do Nascimento Biller |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |
| Processo FAPESP: | 18/00031-7 - Estudos sobre comparação de genomas |
| Beneficiário: | João Meidanis |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |