Search

Your search keyword '"Oliveira, Andre Rodrigues"' showing total 102 results
Start Over Author "Oliveira, Andre Rodrigues"
102 results on '"Oliveira, Andre Rodrigues"'

2. Maximum Alternating Balanced Cycle Decomposition and Applications in Sorting by Intergenic Operations Problems

Author

Brito, Klairton Lima, Alexandrino, Alexsandro Oliveira, Siqueira, Gabriel, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Scornavacca, Celine, editor, and Hernández-Rosales, Maribel, editor

Published
2024
Full Text
View/download PDF

4. On the Complexity of Some Variations of Sorting by Transpositions

Author

Alexandrino, Alexsandro Oliveira, Oliveira, Andre Rodrigues, Dias, Ulisses, and Dias, Zanoni

Subjects
Computer Science - Computational Complexity, F.2.0, G.2.1
Abstract

One of the main challenges in Computational Biology is to find the evolutionary distance between two organisms. In the field of comparative genomics, one way to estimate such distance is to find a minimum cost sequence of rearrangements (large scale mutations) needed to transform one genome into another, which is called the rearrangement distance. In the past decades, these problems were studied considering many types of rearrangements (such as reversals, transpositions, transreversals, and revrevs) and considering the same weight for all rearrangements, or different weights depending on the types of rearrangements. The complexity of the problems involving reversals, transpositions, and both rearrangements is known, even though the hardness proof for the problem combining reversals and transpositions was recently given. In this paper, we enhance the knowledge for these problems by proving that models involving transpositions alongside reversals, transreversals, and revrevs are NP-hard, considering weights w1 for reversals and w2 for the other rearrangements such that w2/w1 is less than or equal to 1.5. In addition, we address a cost function related to the number of fragmentations caused by a rearrangement, proving that the problem of finding a minimum cost sorting sequence, considering the fragmentation cost function with some restrictions, is NP-hard for transpositions and the combination of reversals and transpositions.

Published
2022
Full Text
View/download PDF

5. Block Interchange and Reversal Distance on Unbalanced Genomes

Author

Alexandrino, Alexsandro Oliveira, Siqueira, Gabriel, Brito, Klairton Lima, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Reis, Marcelo S., editor, and de Melo-Minardi, Raquel C., editor

Published
2023
Full Text
View/download PDF

7. A 1.375-Approximation Algorithm for Sorting by Transpositions with Faster Running Time

Author

Alexandrino, Alexsandro Oliveira, Brito, Klairton Lima, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Scherer, Nicole M., editor, and de Melo-Minardi, Raquel C., editor

Published
2022
Full Text
View/download PDF

9. Heuristics for Cycle Packing of Adjacency Graphs for Genomes with Repeated Genes

Author

Siqueira, Gabriel, Oliveira, Andre Rodrigues, Alexandrino, Alexsandro Oliveira, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Stadler, Peter F., editor, Walter, Maria Emilia M. T., editor, Hernandez-Rosales, Maribel, editor, and Brigido, Marcelo M., editor

Published
2021
Full Text
View/download PDF

10. Reversal Distance on Genomes with Different Gene Content and Intergenic Regions Information

Author

Alexandrino, Alexsandro Oliveira, Brito, Klairton Lima, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Martín-Vide, Carlos, editor, Vega-Rodríguez, Miguel A., editor, and Wheeler, Travis, editor

Published
2021
Full Text
View/download PDF

11. Reversals Distance Considering Flexible Intergenic Regions Sizes

Author

Brito, Klairton Lima, Alexandrino, Alexsandro Oliveira, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Martín-Vide, Carlos, editor, Vega-Rodríguez, Miguel A., editor, and Wheeler, Travis, editor

Published
2021
Full Text
View/download PDF

14. Sorting by Reversals and Transpositions with Proportion Restriction

Author

Brito, Klairton Lima, Alexandrino, Alexsandro Oliveira, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Setubal, João C., editor, and Silva, Waldeyr Mendes, editor

Published
2020
Full Text
View/download PDF

15. Heuristics for Breakpoint Graph Decomposition with Applications in Genome Rearrangement Problems

Author

Pinheiro, Pedro Olímpio, Alexandrino, Alexsandro Oliveira, Oliveira, Andre Rodrigues, de Souza, Cid Carvalho, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Setubal, João C., editor, and Silva, Waldeyr Mendes, editor

Published
2020
Full Text
View/download PDF

16. Block-Interchange Distance Considering Intergenic Regions

Author

Dias, Ulisses, Oliveira, Andre Rodrigues, Brito, Klairton Lima, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Kowada, Luis, editor, and de Oliveira, Daniel, editor

Published
2020
Full Text
View/download PDF

17. A 3.5-Approximation Algorithm for Sorting by Intergenic Transpositions

Author

Oliveira, Andre Rodrigues, Jean, Géraldine, Fertin, Guillaume, Brito, Klairton Lima, Dias, Ulisses, Dias, Zanoni, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Martín-Vide, Carlos, editor, Vega-Rodríguez, Miguel A., editor, and Wheeler, Travis, editor

Published
2020
Full Text
View/download PDF

19. Sorting by Reversals, Transpositions, and Indels on Both Gene Order and Intergenic Sizes

Author

Brito, Klairton Lima, Jean, Géraldine, Fertin, Guillaume, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Cai, Zhipeng, editor, Skums, Pavel, editor, and Li, Min, editor

Published
2019
Full Text
View/download PDF

24. Heuristics for the Sorting Signed Permutations by Reversals and Transpositions Problem

Author

Brito, Klairton Lima, Oliveira, Andre Rodrigues, Dias, Ulisses, Dias, Zanoni, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Jansson, Jesper, editor, Martín-Vide, Carlos, editor, and Vega-Rodríguez, Miguel A., editor

Published
2018
Full Text
View/download PDF

25. Sorting by Weighted Reversals and Transpositions

Author

Oliveira, Andre Rodrigues, Brito, Klairton Lima, Dias, Zanoni, Dias, Ulisses, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, and Alves, Ronnie, editor

Published
2018
Full Text
View/download PDF

26. Super Short Reversals on Both Gene Order and Intergenic Sizes

Author

Oliveira, Andre Rodrigues, Jean, Géraldine, Fertin, Guillaume, Dias, Ulisses, Dias, Zanoni, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, and Alves, Ronnie, editor

Published
2018
Full Text
View/download PDF

46. O problema da ordenação de permutações por reversões e transposições

Author

Oliveira, Andre Rodrigues, 1990, Dias, Zanoni, 1975, Walter, Maria Emilia Machado Telles, Telles, Guilherme Pimentel, Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação, and UNIVERSIDADE ESTADUAL DE CAMPINAS

Subjects
Computational biology, Permutations, Permutações (Matemática), Genomes, Algoritmos de aproximação, Biologia computacional, Approximation algorithms, Genomas
Abstract

Orientador: Zanoni Dias Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Rearranjos de Genomas, diferentemente das mutações mais comuns que afetam pontualmente o genoma, são eventos de mutação globais que agem sobre grandes trechos do genoma, e são um desafio para a Teoria da Computação, uma vez que, na maioria dos casos, computar a distância entre dois genomas considerando operações globais resultam em problemas NP-Difíceis. De forma similar, podemos definir o Problema da Ordenação de Genomas, em que buscamos calcular o número mínimo de eventos de rearranjos necessários para ordenar blocos conservados de genomas, onde os genomas são representados por permutações. Um modelo de rearranjo determina quais eventos de rearranjo são permitidos para ordenar uma permutação ou transformar uma permutação em outra. Dentre os eventos de rearranjo mais comuns, podemos citar as reversões e as transposições. Modelos considerando os dois eventos, separadamente, já possuem vasta bibliografia. Entretanto, modelos considerando os dois eventos em conjunto ainda são pouco explorados. Nesta dissertação, apresentamos diversas heurísticas para ordenação de permutações por reversões e transposições considerando permutações com sinais e permutações sem sinais. Para tanto, diversas métricas compatíveis com o problema foram utilizadas em heurísticas, que mais tarde foram testadas com um grande conjunto de permutações aleatórias. As métricas que obtiveram os melhores resultados foram utilizadas em uma heurística denominada Heurística de Grafo de Ciclos. Além disso, foram criados bancos de configurações que auxiliam esta heurística no processo de ordenação de uma permutação. Os resultados obtidos pela Heurística de Grafo de Ciclos foram comparados com algoritmos já existentes na literatura, tanto os que permitem reversões e transposições, bem como os que consideram apenas um dos eventos, evidenciando que a Heurística de Grafo de Ciclos produz os melhores resultados para todos os conjuntos de permutações com sinais, e em grande parte dos conjuntos de permutações sem sinais Abstract: Genome rearrangements, unlike most common mutations that affects only one nucleotide, are global mutation events that affect large fragments of genomes and present a challenge to the Computational Theory Field, since in most cases, computing the distance between genomes considering global operations results in NP-Hard problems. Moreover, the Sorting Permutations by Genome Rearrangements problem seeks to compute the smallest number of rearrangement events needed to sort conserved blocks of genomes, with genomes represented by permutations. A rearrangement model determines which rearrangement events are allowed to sort a permutation or to transform a permutation into another. The two most common rearrangement events are reversals and transpositions. Rearrangement models considering reversals and transpositions separately have an extensive bibliography. However, models considering both events are still little explored. In this dissertation, we present some heuristics that sort permutations by reversals and transpositions considering signed and unsigned permutations. To do this, various metrics that are compatible with the problem were used. These heuristics were later tested with a large set of random permutations. Metrics that have achieved the best results were used in a heuristic named Cycle Graph Heuristic. In addition, cycle configurations were created and stored in a database in order to help our heuristic in the sorting process. The results obtained from Cycle Graph Heuristic were compared with existing algorithms in the literature, showing that our heuristic produces the best results for all sets of signed permutations and in many of the sets of unsigned permutations Mestrado Ciência da Computação Mestre em Ciência da Computação CNPQ 147337/2013-5

Published
2021

49. Reversal and Indel Distance With Intergenic Region Information

Author

Alexandrino, Alexsandro Oliveira, Brito, Klairton Lima, Oliveira, Andre Rodrigues, Dias, Ulisses, and Dias, Zanoni

Abstract

Recent works on genome rearrangements have shown that incorporating intergenic region information along with gene order in models provides better estimations for the rearrangement distance than using gene order alone. The reversal distance is one of the main problems in genome rearrangements. It has a polynomial time algorithm when only gene order is used to model genomes, assuming that repeated genes do not exist and that gene orientation is known, even when the genomes have distinct gene sets. The reversal distance is NP-hard and has a 2-approximation algorithm when incorporating intergenic regions. However, the problem has only been studied assuming genomes with the same set of genes. In this work, we consider the variation that incorporates intergenic regions and that allows genomes to have distinct sets of genes, a scenario that leads us to include indels operations (insertions and deletions). We present a 2.5-approximation algorithm using the labeled intergenic breakpoint graph, which is based on the well-known breakpoint graph structure. We also present an experimental analysis of the proposed algorithm using simulated data, which showed that the practical approximation factor is considerably less than 2.5. Furthermore, we used the algorithm in real genomes to construct a phylogenetic tree.

Published
2023
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results