| Texto completo | |
| Autor(es): |
Oliveira, Andre Rodrigues
[1]
;
Jean, Geraldine
[2]
;
Fertin, Guillaume
[2]
;
Brito, Klairton Lima
[1]
;
Bulteau, Laurent
[3]
;
Dias, Ulisses
[4]
;
Dias, Zanoni
[1]
Número total de Autores: 7
|
| Afiliação do(s) autor(es): | [1] Univ Estadual Campinas, Inst Comp, 1251 Albert Einstein Ave, BR-13083852 Campinas - Brazil
[2] Univ Nantes, LS2N CNRS UMR 6004, 2 Rue Houssiniere, F-44322 Nantes 3 - France
[3] Univ Paris Est Marne La Vallee, LIGM CNRS UMR 8049, 5 Bd Descartes, F-77454 Marne La Vallee - France
[4] Univ Estadual Campinas, Sch Technol, 1888 Paschoal Marmo St, BR-13484332 Limeira - Brazil
Número total de Afiliações: 4
|
| Tipo de documento: | Artigo Científico |
| Fonte: | IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS; v. 18, n. 6, p. 2870-2876, NOV 1 2021. |
| Citações Web of Science: | 3 |
| Resumo | |
Genome rearrangements are mutations affecting large portions of a genome, and a reversal is one of the most studied genome rearrangements in the literature through the Sorting by Reversals (SbR) problem. SbR is solvable in polynomial time on signed permutations (i.e., the gene orientation is known), and it is NP-hard on unsigned permutations. This problem (and many others considering genome rearrangements) models genome as a list of its genes in the order they appear, ignoring all other information present in the genome. Recent works claimed that the incorporation of the size of intergenic regions, i.e., sequences of nucleotides between genes, may result in better estimators for the real distance between genomes. Here we introduce the Sorting Signed Permutations by Intergenic Reversals problem, that sorts a signed permutation using reversals both on gene order and intergenic sizes. We show that this problem is NP-hard by a reduction from the 3-partition problem. Then, we propose a 2-approximation algorithm for it. Finally, we also incorporate intergenic indels (i.e., insertions or deletions of intergenic regions) to overcome a limitation of sorting by conservative events (such as reversals) and propose two approximation algorithms. (AU) | |
| Processo FAPESP: | 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais |
| Beneficiário: | Munir Salomao Skaf |
| Modalidade de apoio: | Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs |
| Processo FAPESP: | 19/27331-3 - Problemas de ordenação por rearranjos de genomas |
| Beneficiário: | André Rodrigues Oliveira |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| 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 |
| 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 |