| Full text | |
| Author(s): |
Dias, Ulisses
;
Oliveira, Andre Rodrigues
;
Brito, Klairton Lima
;
Dias, Zanoni
;
Kowada, L
;
DeOliveira, D
Total Authors: 6
|
| Document type: | Journal article |
| Source: | ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2019; v. 11347, p. 12-pg., 2020-01-01. |
| Abstract | |
Genome Rearrangement (GR) is a field of computational biology that uses conserved regions within two genomes as a source of information for comparison purposes. This branch of genomics uses the order in which these regions appear to infer evolutive scenarios and to compute distances between species, while usually neglecting nonconserved DNA sequence. This paper sheds light on this matter and proposes models that use both conserved and non-conserved sequences as a source of information. The questions that arise are how classic GR algorithms should be adapted and how much would we pay in terms of complexity to have this feature. Advances on these questions aid in measuring advantages of including such approach in GR algorithms. We propose to represent non-conserved regions by their lengths and apply this idea in a genome rearrangement problem called "Sorting by BlockInterchanges". The problem is an interesting choice on the theory of computation viewpoint because it is one of the few problems that are solvable in polynomial time and whose algorithm has a small number of steps. That said, we present a 2-approximation algorithm to this problem along with data structures and formal definitions that may be generalized to other problems in GR field considering intergenic regions. (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: | 17/16246-0 - Sensitive media analysis through deep learning architectures |
| Grantee: | Sandra Eliza Fontes de Avila |
| Support Opportunities: | Regular Research Grants |