| Full text | |
| Author(s): |
Brito, Klairton Lima
;
Jean, Geraldine
;
Fertin, Guillaume
;
Oliveira, Andre Rodrigues
;
Dias, Ulisses
;
Dias, Zanoni
;
Cai, Z
;
Skums, P
;
Li, M
Total Authors: 9
|
| Document type: | Journal article |
| Source: | BIOINFORMATICS RESEARCH AND APPLICATIONS, ISBRA 2019; v. 11490, p. 12-pg., 2019-01-01. |
| Abstract | |
During the evolutionary process, the genome is affected by various genome rearrangements, which are events that modify large stretches of the genetic material. In the literature, several models were designed to estimate the number of events that occurred during the evolution, but these models represent genomes as a sequence of genes, overlooking the genetic material between consecutive genes. However, recent studies show that taking into account the genetic material present between consecutive genes can be more realistic. Reversal and transposition are genome rearrangements widely studied in the literature. A reversal inverts a segment of the genome while a transposition swaps the positions of two consecutive segments. Genomes also undergo non-conservative events (events that alter the amount of genetic material) such as insertion and deletion, which insert and remove genetic material from intergenic regions of the genome, respectively. We study problems considering both gene order and intergenic regions size. We investigate the reversal distance between two genomes in two scenarios: with and without non-conservative events. For both problems, we show that they belong to NP-hard problems class and we present a 4-approximation algorithm. We also study the reversal and transposition distance between two genomes (and the variation with non-conservative events) and we present a 6-approximation algorithm. (AU) | |
| 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/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 |