| Full text | |
| Author(s): |
Oliveira, Andre Rodrigues
;
Jean, Geraldine
;
Fertin, Guillaume
;
Dias, Ulisses
;
Dias, Zanoni
;
Alves, R
Total Authors: 6
|
| Document type: | Journal article |
| Source: | ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2018; v. 11228, p. 12-pg., 2018-01-01. |
| Abstract | |
The evolutionary distance between two genomes can be estimated by computing the minimum length sequence of operations, called genome rearrangements, that transform one genome into another. Usually, a genome is modeled as an ordered sequence of (possibly signed) genes, and almost all the studies that have been undertaken in the genome rearrangement literature consist in shaping biological scenarios into mathematical models: for instance, allowing different genome rearrangements operations at the same time, adding constraints to these rearrangements (e.g., each rearrangement can affect at most a given number k of genes), considering that a rearrangement implies a cost depending on its length rather than a unit cost, etc. However, most of the works in the field have overlooked some important features inside genomes, such as the presence of sequences of nucleotides between genes, called intergenic regions. In this work, we investigate the problem of computing the distance between two genomes, taking into account both gene order and intergenic sizes; the genome rearrangement operation we consider here is a constrained type of reversals, called super short reversals, which affect up to two (consecutive) genes. We propose here three algorithms to solve the problem: a 3-approximation algorithm that applies to any instance, and two additional algorithms that apply only on specific types of genomes with respect to their gene order: the first one is an exact algorithm, while the second is a 2-approximation algorithm. (AU) | |
| FAPESP's process: | 17/12646-3 - Déjà vu: feature-space-time coherence from heterogeneous data for media integrity analytics and interpretation of events |
| Grantee: | Anderson de Rezende Rocha |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 13/08293-7 - CCES - Center for Computational Engineering and Sciences |
| Grantee: | Munir Salomao Skaf |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |
| FAPESP's process: | 17/16246-0 - Sensitive media analysis through deep learning architectures |
| Grantee: | Sandra Eliza Fontes de Avila |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 17/16871-1 - Problems of sorting permutations by fragmentation-weighted operations |
| Grantee: | Alexsandro Oliveira Alexandrino |
| Support Opportunities: | Scholarships in Brazil - Master |