| Full text | |
| Author(s): |
Biller, Priscila
;
Pereira Zanetti, Joao Paulo
;
Meidanis, Joao
;
Setubal, JC
;
Silva, WM
Total Authors: 5
|
| Document type: | Journal article |
| Source: | ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2020; v. 12558, p. 9-pg., 2020-01-01. |
| Abstract | |
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) | |
| FAPESP's process: | 12/13865-7 - Algebraic Model for Genome Rearrangements |
| Grantee: | João Paulo Pereira Zanetti |
| Support Opportunities: | Scholarships in Brazil - Doctorate |
| FAPESP's process: | 12/14104-0 - Genome Rearrangement Problems Viewed Through Permutations, Matrices and Other Algebraic Concepts |
| Grantee: | Priscila Do Nascimento Biller |
| Support Opportunities: | Scholarships in Brazil - Doctorate |
| FAPESP's process: | 18/00031-7 - Studies on genome comparison |
| Grantee: | João Meidanis |
| Support Opportunities: | Regular Research Grants |