| Texto completo | |
| Autor(es): |
Dias, Ulisses
;
Oliveira, Andre Rodrigues
;
Brito, Klairton Lima
;
Dias, Zanoni
;
Kowada, L
;
DeOliveira, D
Número total de Autores: 6
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2019; v. 11347, p. 12-pg., 2020-01-01. |
| Resumo | |
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) | |
| Processo FAPESP: | 17/12646-3 - Déjà vu: coerência temporal, espacial e de caracterização de dados heterogêneos para análise e interpretação de integridade |
| Beneficiário: | Anderson de Rezende Rocha |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 17/16246-0 - Análise de mídias sensíveis usando arquiteturas de aprendizado profundo |
| Beneficiário: | Sandra Eliza Fontes de Avila |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |